Dispersion-based Models and Algorithms for Districting Problems

Show simple item record

dc.contributor DOLORES EDWIGES LUNA REYES;65193 en_US
dc.contributor.advisor Luna Reyes, Dolores Edwiges
dc.contributor.author Sandoval Esquivel, María Gabriela
dc.coverage.spatial San Andrés Cholula, Puebla. México.
dc.creator MARIA GABRIELA SANDOVAL ESQUIVE;690950 en_US
dc.date.accessioned 2020-07-17T02:20:15Z
dc.date.available 2020-07-17T02:20:15Z
dc.date.issued 2020-05-13
dc.identifier.uri http://repositorio.udlap.mx/xmlui/handle/123456789/13358
dc.description 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. en_US
dc.description.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 en_US
dc.description.statementofresponsibility Investigadores en_US
dc.language eng en_US
dc.publisher Universidad de las Américas Puebla en_US
dc.relation Versión publicada en_US
dc.relation.ispartof REPOSITORIO REMERI en_US
dc.relation.ispartof REPOSITORIO NACIONAL CONACYT en_US
dc.relation.ispartof OPENAIRE en_US
dc.rights Acceso Abierto en_US
dc.rights.uri http://creativecommons.org/licenses/by-nd/4.0 en_US
dc.subject districting en_US
dc.subject territory design en_US
dc.subject operations research en_US
dc.subject integer programming en_US
dc.subject.classification 1 CIENCIAS FÍSICO MATEMATICAS Y CIENCIAS DE LA TIERRA en_US
dc.title Dispersion-based Models and Algorithms for Districting Problems en_US
dc.type Tesis de doctorado en_US


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Acceso Abierto Except where otherwise noted, this item's license is described as Acceso Abierto

Search RI-UDLAP


Advanced Search

Browse

My Account