The Max-p-Compact-Regions Problem

Abstract

The max-p-compact-regions problem involves the aggregation of a set of small areas into an unknown maximum number (p) of compact, homogeneous, and spatially contiguous regions such that a regional attribute value is higher than a predefined threshold. The max-p-compact-regions problem is an extension of the max-p-regions problem accounting for compactness. The max-p-regions model has been widely used to define study regions in many application cases since it allows users to specify criteria and then to identify a regionalization scheme. However, the max-p-regions model does not consider compactness even though compactness is usually a desirable goal in regionalization, implying ideal accessibility and apparent homogeneity. This article discusses how to integrate a compactness measure into the max-p regionalization process by constructing a multiobjective optimization model that maximizes the number of regions while optimizing the compactness of identified regions. An efficient heuristic algorithm is developed to address the computational intensity of the max-p-compact-regions problem so that it can be applied to large-scale practical regionalization problems. This new algorithm will be implemented in the open-source Python Spatial Analysis Library. One hypothetical and one practical application of the max-p-compact-regions problem are introduced to demonstrate the effectiveness and efficiency of the proposed algorithm.