Resumen

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. Resumen. La investigación presentada en este documento de tesis se enfoca en problemas de diseño territorial. Estos problemas se estudian en el área de investigación de operaciones como una clase de problemas de localización. En este contexto, se pretende ayudar en el proceso del diseño de distritos al dividir un área geográfica de acuerdo a criterios de planificación específicos. Una de las contribuciones esenciales en este trabajo es el desarrollo de dos métodos de solución para problemas de diseño territorial. Cada uno de los métodos propuestos está dicdo para un modelo de diseño territorial específico. Los modelos estudiados se caracterizan por tener como función objetivo una medida de dispersión, diferente en cada modelo, que se usa para definir la compacidad de los distritos. Uno de estos modelos usa la medida de dispersión p-centro y el otro usa la medida de dispersión p-mediana. En ambos modelos se consideran restricciones para asegurar que los distritos estén balanceados y conectados; asícomo que haya un núm fijo de distritospredefinido. Los métodos de solución que se proponen se basan en algoritmos iterativos que usan sub-problemas auxiliares. La idea es usar estos sub-problemas para mejorar gradualmente la cota inferior en la función objetivo de cada modelo hasta encontrar la solución óptima. Cada método propuesto está diseñado específicamente para reducir la complejidad computacional que involucra su respectivo modelo. En ambos algoritmos, se relajan inicialmente las restricciones de conectividad que representan un componente importante de la complejidad de cada modelo. Para asegurar que se cumple la restricción de connectividad en las soluciones se implementa una estrategia en la que se analizan soluciones parciales para identificar violaciones a las restricciones de conectividad y entonces agregar solamente las restricciones que correspondan a dichas violaciones. Se hicieron pruebas para cada uno de to de 800 instancias que variaban en sus párametros. El desempeño de los métodos se evaluó en términos del tiempo computational que se usó para resolver cada instancia y en la capacidad de resolver instancias de mayor tamaño. La validación de los métodos se hizo mediante una comparación contra los mejores métodos conocidos hasta ahora para los modelos de diseño territorial estudiados. Los resultados mestran que los métodos de solución propuestos son significativamente más rápidos que los existentes y son capaces de resolver instancias de mayor tamaño. Con el método de solución propuesto para el problema con la medida de dispersión de p-centro se pudieron resolver un 30% más de instancias que con el método existente, dentro del tiempo límite. Este método fue, en promedio, 128 veces más rápido que el método existente. Por otra parte, el m todo propuesto para el problema con la dispersión de la p-mediana fue, en promedio 10.7 veces más rápido que el método existente. Otra contribución importante de esta investigación es el análisis que se empleó para comparar los dos modelos de diseño territorial que se estudiaron. La principal diferencia entre estos modelos está en la medida de dispersión que se usa en cada uno para definir la compacidad de los distritos. A pesar de que estos modelos han sido bien estudiados en la literatura de problemas de diseño territorial no se ha hecho una comparación entre ellos para determinar si alguno es más adecuado que el otro. Por esta razón se implementó una estrategia para comparar ambos modelos y determinar cual de ellos es más robusto que el otro. Los resultados del análisis concluyen que el modelo basado en la medida de p-centro es el más robusto. María Gabriela Sandoval Esquivel.

Palabras clave: districting; territory design; operations research; integer programming.

Esta tesis sólo puede ser consultada por miembros de la Comunidad Universitaria. (ir al índice de contenido)

Sandoval Esquivel, M. G. 2020. Dispersion-based Models and Algorithms for Districting Problems. Proyecto Final Doctorado. Sistemas Inteligentes. Departamento de Ingeniería en Computación, Electrónica y Mecatrónica, Escuela de Ingeniería, Universidad de las Américas Puebla. Mayo. Derechos Reservados © 2020.