Premium
On the Performance of the Subtour Elimination Constraints Approach for the p ‐Regions Problem: A Computational Study
Author(s) -
Duque Juan Carlos,
VélezGallego Mario C.,
Echeverri Laura Catalina
Publication year - 2018
Publication title -
geographical analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.773
H-Index - 65
eISSN - 1538-4632
pISSN - 0016-7363
DOI - 10.1111/gean.12132
Subject(s) - classification of discontinuities , contiguity , spatial analysis , cluster analysis , computer science , integer programming , variable (mathematics) , autocorrelation , process (computing) , integer (computer science) , mathematical optimization , set (abstract data type) , iterative and incremental development , iterative method , algorithm , mathematics , statistics , artificial intelligence , mathematical analysis , software engineering , programming language , operating system
The p‐regions is a mixed integer programming (MIP) model for the exhaustive clustering of a set of n geographic areas into p spatially contiguous regions while minimizing measures of intraregional heterogeneity. This is an NP‐hard problem that requires a constant research of strategies to increase the size of instances that can be solved using exact optimization techniques. In this article, we explore the benefits of an iterative process that begins by solving the relaxed version of the p‐regions that removes the constraints that guarantee the spatial contiguity of the regions. Then, additional constraints are incorporated iteratively to solve spatial discontinuities in the regions. In particular we explore the relationship between the level of spatial autocorrelation of the aggregation variable and the benefits obtained from this iterative process. The results show that high levels of spatial autocorrelation reduce computational times because the spatial patterns tend to create spatially contiguous regions. However, we found that the greatest benefits are obtained in two situations: (1) when n / p ≥ 3 ; and (2) when the parameter p is close to the number of clusters in the spatial pattern of the aggregation variable.