Premium
The p ‐Regions Problem. p‐区域问题
Author(s) -
Duque Juan C.,
Church Richard L.,
Middleton Richard S.
Publication year - 2011
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/j.1538-4632.2010.00810.x
Subject(s) - contiguity , integer programming , extension (predicate logic) , mathematics , travelling salesman problem , mathematical optimization , computer science , combinatorics , programming language , operating system
The p ‐regions problem involves the aggregation or clustering of n small areas into p spatially contiguous regions while optimizing some criteria. The main objective of this article is to explore possible avenues for formulating this problem as a mixed integer‐programming (MIP) problem. The critical issue in formulating this problem is to ensure that each region is a spatially contiguous cluster of small areas. We introduce three MIP models for solving the p regions problem. Each model minimizes the sum of dissimilarities between all pairs of areas within each region while guaranteeing contiguity. Three strategies designed to ensure contiguity are presented: (1) an adaptation of the Miller, Tucker, and Zemlin tour‐breaking constraints developed for the traveling salesman problem; (2) the use of ordered‐area assignment variables based upon an extension of an approach by Cova and Church for the geographical site design problem; and (3) the use of flow constraints based upon an extension of work by Shirabe. We test the efficacy of each formulation as well as specify a strategy to reduce overall problem size.