A Model of Contiguity for Spatial Unit Allocation

We consider a problem of allocating spatial units (SUs) to particular uses to form "regions" according to specified criteria, which is here called "spatial unit allocation." Contiguity—the quality of a single region being connected—is one of the most frequently required criteria for this problem. This is also one that is difficult to model in algebraic terms for algorithmic solution. The purpose of this article is to propose a new exact formulation of contiguity that can be incorporated into any mixed integer programming model for SU allocation. The resulting model guarantees to enforce contiguity regardless of other included criteria such as compactness. Computational results suggest that problems involving a single region and fewer than about 200 SUs are optimally solved in fairly reasonable time, but that larger problems must rely on heuristics for approximate solutions. It is also found that a problem of any size can be formulated in a more tractable form when a fixed number of SUs are to be selected or when a certain SU is selected in advance.