Dispersion-based Models and Algorithms for Districting Problems

Abstract

The work presented in this thesis focuses on districting problems. These problems are studied in the area of operations research as a class of location problems. In this context, the aim is to aid district planners in the task of dividing a geographical area into districts according to specific planning criteria. An essential contribution of this work is the development of two new exact methods of solution for districting problems. Each of the proposed methods is tailored for a specific districting model. The districting models used are characterized by having as objective the minimization of a dispersion measure and have been well studied in the literature of districting problems. One of them uses the p-center dispersion measure, while the other uses the p-median dispersion measure. Both models consider constraints that ensure district balance, district connectivity, and a fixed number of districts. The proposed solution methods are both iterative algorithms that use auxiliary subproblems to gradually improve the lower bound on the objective function of each problem until the optimal solution is found. Each solution method is tailored to its respective districting model in an attempt to reduce the computational effort of obtaining an optimal solution. In both solution methods, the connectivity constraints are initially relaxed, and in a final phase, a strategy to ensure connectivity is implemented. The connectivity constraints are a significant issue that contributes to the computational complexity of the districting models that are studied. The strategy to ensure connectivity is to analyze the solutions of the auxiliary sub-problems for any violations to the connectivity constraints and then adding only the constraints that correspond to them. Each one of the proposed solution methods was tested with a batch of 800 instances of varying parameters. The performance was evaluated in terms of the computational time spent to solve each instance and the ability to solve larger size instances. The proposed solution methods were compared with the best-known solution methods for the models studied so far. The results show that the proposed solution methods perform significantly faster than the existing methods and are capable of solving larger size instances efficiently. In fact, the proposed solution method for the problem with the p-center dispersion was able to solve 32% more instances within the established time limit. This proposed method was on average 128 times faster than the existing method. The proposed solution method for the problem with the p-median dispersion was on average 10.7 times faster with the computation time of the existing method. Another significant contribution of this research is the analysis made to compare the dispersion-based models studied. The main difference between these models is the dispersion measure used in the objective function to define district compactness. In the literature, both of these models or derived formulations have been used to describe districting problems. However, there is not an accurate assessment of which model has an advantage over the other, if any. For this reason, a strategy to determine which one of the model studied is more robust than the other is presented in this work. As a result, it was concluded that the model based on the p-center dispersion measure was the most robust formulation