Spatial optimization for regionalization problems with spatial interaction: a heuristic approach

Abstract

Spatial optimization techniques are commonly used for regionalization problems, often represented as p-regions problems. Although various spatial optimization approaches have been proposed for finding exact solutions to p-regions problems, these approaches are not practical when applied to large-size problems. Alternatively, various heuristics provide effective ways to find near-optimal solutions for p-regions problem. However, most heuristic approaches are specifically designed for particular geographic settings. This paper proposes a new heuristic approach named Automated Zoning Procedure-Center Interchange (AZP-CI) to solve the p-functional regions problem (PFRP), which constructs regions by combining small areas that share common characteristics with predefined functional centers and have tight connections among themselves through spatial interaction. The AZP-CI consists of two subprocesses. First, the dissolving/splitting process enhances diversification and thereby produces an extensive exploration of the solution space. Second, the standard AZP locally improves the objective value. The AZP-CI was tested using randomly simulated datasets and two empirical datasets with different sizes. These evaluations indicate that AZP-CI outperforms two established heuristic algorithms: the AZP and simulated annealing, in terms of both solution quality and consistency of producing reliable solutions regardless of initial conditions. It is also noted that AZP-CI, as a general heuristic method, can be easily extended to other regionalization problems. Furthermore, the AZP-CI could be a more scalable algorithm to solve computational intensive spatial optimization problems when it is combined with cyberinfrastructure.

Keywords:

• regionalization
• p-functional regions problem
• hybrid heuristic
• automated zoning procedure-center interchange (AZP-CI)
• spanning tree

Acknowledgements

This work was supported by the National Research Foundation of Korea Grant, funded by the Korean Government (NRF-2011-327-B00856).