A Simulated Annealing-Based Multiobjective Optimization Algorithm for Political Districting

Redistricting consists in partitioning a set of basic units into a given number of larger groups for electoral purposes. These groups should be designed to fulfill federal and state requirements such as contiguity, population equality and compactness to promote democratic fairness. Political districting can be modeled as a multi-objective combinatorial optimization problem where the criteria are often difficult to optimize In fact, it has been proven to be computationally intractable (NP-hard). Due to these reasons the use of heuristics to provide good approximations in a reasonable amount of time is justified. In the literature, most approaches manage the problem through mono-objective optimization methods and the use of Pareto search techniques is limited. In this work, a multi-objective metaheuristic algorithm based on simulated annealing that uses Pareto dominance during the search process is proposed and applied to a bi-objective model to solve the problem. The current technique applied by the Mexican redistricting authority and two state-of-the-art multi-objective algorithms are used to compare the performance of the proposed algorithm on 12 real data sets. We conclude that the developed algorithm can generate better quality solutions than its counterparts.