Academic journal article Geographical Analysis

A Model of Contiguity for Spatial Unit Allocation

Academic journal article Geographical Analysis

A Model of Contiguity for Spatial Unit Allocation

Article excerpt

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.

**********

Introduction

A spatial unit (SU) allocation problem can be cast as one of selecting subsets--here referred to as regions--of SUs such as census tracts, land parcels, and grid cells from a given set of SUs according to specified criteria. The problems encompass various applications ranging from political districting (Hess et al. 1965; Garfinkel and Nemhauser 1970; Hojati 1996; Mehrotra, Johnson, and Nemhauser 1998) and school districting (Yeates 1963; Belford and Ratliff 1972; Franklin and Koenigsberg 1973) to sales territory alignment (Hess and Samuels 1971; Shanker, Turner, and Zoltners 1975; Segal and Weinberger 1977; Marlin 1981; Zoltners and Sinha 1983; Fleischmann and Paraschis 1988) and timber harvest scheduling (Barahona, Weintraub, and Epstein 1992; Snyder and ReVelle 1996; Murray 1999; McDill, Rebain, and Braze 2002) to land allocation (Wright, ReVelle, and Cohon 1983; Gilbert, Holmes, and Rosenthal 1985; Diamond and Wright 1988; Tomlin and Johnston 1990; Benabdallah and Wright 1991, 1992; Crema 1996; Eastman, Jiang, and Toledano 1998; Cova and Church 2000; Aerts and Heuvelink 2002; Williams 2002, 2003; Aerts et al. 2003) and habitat reserve site selection (McDonnell et al. 2002; Onal and Briers 2002; Fischer and Church 2003; Nalle, Arthur, and Sessions 2003). Although required criteria highly vary from one application to another, they tend to relate to size, shape, or spatial relation (Shirabe and Tomlin 2002). For example, political districting has four essential criteria: equal population size, compact and contiguous shape, and mutually exclusive districts. While some regions, such as voting districts, are artificial and do not have any conspicuous physical existence, others may come to exist in the form of housing developments, airports, landfills, and so on. The latter type of region tends to have stricter shape requirements such as non-perforation, convexity, rectangularity, and similarity to a specific letter like "L" or "O."

Contiguity--the quality of a single region being connected--is one of the most frequently required SU allocation criteria, as fragmentation often affects the viability or influence of a region. It is also such a fundamental quality that many shapes can be realized only when a region is contiguous. Although an exact formulation of contiguity has repeatedly been called for in the literature (e.g., Wright, ReVelle, and Cohon 1983; Eastman, Jiang, and Toledano 1998; Cova and Church 2000), it has not been carried out until recently (Williams 2002) because of the complexity of articulating and operationalizing a statement of contiguity. Instead, contiguity has often been regarded as a property incidental to compactness--the quality of being circle-/square-like or consolidated rather than spread, because "the compactness driving force generally prevents noncontiguity" (Hess and Samuels 1971). Thus, many efforts have focused on generating a compact region, for example, by minimizing the total distance between each SU and the center of the region (e. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.