An extendable heuristic framework to solve the p-compact-regions problem for urban economic modeling

• Propose an extendable heuristic framework for solving large, practical, and non-linear regionalization problems.
• Introduce NMI as a novel method and prove its effectiveness to compute compactness in a p-compact-regions problem.
• Demonstrate the good performance of MERGE heuristic in solving real-world large p-compact-regions problem.

The p-compact-regions problem, defined by Li, Church, and Goodchild (forthcoming) involves generating a fixed number (p) of regions from n atomic polygonal units with the objective of maximizing the compactness of each region. Compactness is a shape factor measuring how closely and firmly the polygonal units in a region are packed together. A compact polygonal region has the advantages of being homogeneous and maximizing the accessibility of all points within that region, therefore it is useful in a large number of real-world applications, such as in conservation planning, political district partitioning, and the proposed application in this paper concerning regionalization for urban economic modeling. This paper reports our efforts in designing an object-oriented heuristic framework that integrates semi-greedy growth and local search to solve a real-world applied p-compact-regions problem to optimality or near-optimality. We apply this model to support urban economic simulation, in which activities need to be aggregated from the 4109 Transportation Analysis Zones (TAZs) of six southern California counties into 100 regions to achieve desired computational feasibility of the economic simulation model. Spatial contiguity, physiography, political boundaries, the presence of local centers, and intra-zonal and inter-zonal traffic are considered, and efforts are made to ensure consistency of selected properties between the disaggregated and aggregated regions. This work makes an original contribution in the development of a highly extendable and effective solution framework to allow researchers to investigate large, real, non-linear regionalization problems and find practical solutions.