A Spatial Decision Support System (SDSS) for Electoral Districting

Algorithms and Data Structures

- Computational difficulties led to the development of
heuristic solution techniques which are invariably used for large problems.

- We use the GRIA heuristic (Densham and Rushton 1992a)

- This systematically exchanges the enumeration areas that
are the “centers” of new electoral districts

- During each iteration, the remaining enumeration areas
are allocated to the new “centers” to form approximately equal population
size districts.

- This is a substitution type heuristic with the property
that at its termination
*no*pair-wise substitution of any one enumeration area from one electoral district to another electoral district will improve the value of the objective function.

- The coefficients in the p-median location-allocation
model are modified with appropriate weights to find maps along the “solution
frontier”.

- That is, by modifying the definition of w
_{i}d_{ij}in the p-median model, different weights are given to each of the two objectives (see Hillsman, 1984).

- The results of such multiple runs using the same algorithm trace out different feasible solutions to the electoral district delimitation problem from solutions that are maximally spatially compact—but which often have considerable population inequality, to solutions that have more equal numbers of people, but have less spatial compactness.

These specialized approaches to location-allocation modeling that we use for the electoral districting problem are described in the following articles:

- For a description of the GRIA algorithm used in this
application: Densham and Rushton, 1992a.

- For a description of the spatial data structure and its
use in enforcing spatial constraints: Densham and Rushton, 1992b.

- For a description of the generalized unified linear model:
Hillsman, 1984.

- For a copy of the software (LADSS) click on the bottom of the following page: http://www.geog.ucl.ac.uk/~pdensham/SDSS/sdss.stm

Densham, Paul. J., and G. Rushton. (1992a). “A more efficient heuristic for solving large p-median problems.”

Papers in Regional Science:The Journal of the Regional Science Association International,71:307-329.Densham, Paul. J., and G. Rushton. (1992b). “Strategies for solving large location-allocation problems by heuristic methods.”

Environment and Planning A,24:289-304.Densham, Paul. J., and G. Rushton. (1996). “Providing spatial decision support for rural service facilities that require a minimum workload,”

Environment and Planning B,23:553-574.Hillsman, E. L. (1984). “The p-median structure as a unified linear model for location-allocation analysis.”

Environment and Planning A,16:305-318.Rushton, Gerard. (2001), "Spatial Decision Support Systems," Encyclopedia of the Social and Behaviorial Science, Elsevier Science Ltd.

Rushton, Gerard. (1972). “Map transformations of point patterns: central place patterns in areas of variable population density.”

Papers of the Regional Science Association,28:111-129.

Francis, R.L., and J.A. White (1974),

Facility Layout and Locations: An Analytical Approach, Prentice Hall, Englewood Cliffs, N.J.Goodchild, Michael F. and Valerian T. Noronha (1983),

Location-Allocation for Small Computers, Department of Geography, University of Iowa, Monograph No. 8,Ghosh, A. and G. Rushton (eds.), (1987),

Spatial Analysis and Location- AllocationModels, Van Nostrand Reinhold Co., New York.Handler, Gabriel Y. and Pitu B. Mirchandani (1979),

Location on Networks Theory and Algorithms, The MIT Press, Cambridge.Love, Robert, F., J.G.Morris and G. O. Wesolowsky, (1988),

Facilities Location: Models and Methods, North Holland Pub. Co. (Elsevier Science Pub. Co. Inc.) New York

National Center for Geographic Information and Analysis – www.geog.buffalo.edu/ncgia

University at Buffalo UCGIS – www.geog.buffalo.edu/ucgis/UTopic_redistrict.html

Copyright © 2001 by Joel D. Barkan, Paul Densham and Gerard Rushton