Sixty Years of Research on Districting Problems: Models, Algorithms, and Applications

Abstract: Districting consists of grouping small geographic areas or units into larger units, known as districts, territories, zones, or clusters, according to relevant planning criteria such as compactness, connectivity, and/or balance requirements, among others. This class of problems arises in many applications, such as political organization, sales territory design, school districting, commercial and distribution districting, service districting, and health care management, among others. In this paper, we provide a comprehensive state-of-the-art review of the districting literature over the last sixty years. First, a discussion of a general modeling structure is presented to identify the main components of the problem. Then, existing works are reviewed according to two distinct classifications: one by application area and another by modeling techniques and solution methodologies. Finally, we conclude with a discussion of the main challenges and future research lines in this exciting area of discrete optimization.