A Simulated Annealing-Based Multiobjective Optimization Algorithm for Political Districting

Redistricting consists of 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 multiobjective combinatorial optimization problem where the criteria are often difficult to optimize. In fact, it has been proven to be a computationally intractable (NP-hard) problem. 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 different objectives as mono-objective through weighted aggregation functions and the use of Pareto search techniques is limited. In this work, a multi-objective meta-heuristic 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 strategy applied by the Mexican national redistricting authorities is used to compare the performance of the algorithm on 12 real data sets. We conclude that the proposed algorithm can generate better quality solutions than its counterpart.