Solution Techniques for Large Regional Partitioning Problems

Abstract

This paper presents procedures for use in electoral districting and related applications. A region is to be divided into a number of “territories” formed as aggregates of discrete spatial units, subject to constraints on territory size and on intraterritorial connectivity, so as to minimize the total length of territory perimeters. The procedures are based on a hill‐climbing principle, with progressively rigorous application of the connectivity and territory‐size constraints. Computational tests indicate that the best of the procedures provide an effective trade‐off between solution quality and computational efficiency.