Duque, J.C., Church, R.L. and Middleton, R.S. (2010), "The p-regions problem ", Geographical Analysis, Forthcoming.
Abstract: 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 paper is to explore possible avenues for formulating
this problem as a mixed integer programming problem (MIP).
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 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 of Cova and Church for the geographical site design problem;
and 3) the use of
ow constraints based upon an extension of Shirabe.
We test the e_cacy of each formulation as well as specify a strategy to reduce overall problem size.
