On the Performance of the Subtour Elimination Constraints Approach for the p -Regions Problem: A Computational Study
| Autor: | Laura Catalina Echeverri, Mario C. Vélez-Gallego, Juan Carlos Duque |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
Iterative and incremental development 05 social sciences Geography Planning and Development 0211 other engineering and technologies 0507 social and economic geography 021107 urban & regional planning 02 engineering and technology Classification of discontinuities Contiguity (probability theory) Variable (computer science) Spatial ecology Cluster analysis 050703 geography Spatial analysis Integer programming Earth-Surface Processes Mathematics |
| Zdroj: | Geographical Analysis. 50:32-52 |
| ISSN: | 0016-7363 |
| DOI: | 10.1111/gean.12132 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|