Por favor, use este identificador para citar o enlazar este ítem:
http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/2602| Models and Algorithms for Depot-Free Multiple Traveling Salesperson Problems | |
| JOSE ALEJANDRO CORNEJO-ACOSTA | |
| Jesús García Díaz Julio César Pérez Sansalvador | |
| Acceso Abierto | |
| Atribución-NoComercial-SinDerivadas | |
| integer programming combinatorial optimization heuristics mTSP DFmTSP k-center evolutionary computing | |
| This thesis addresses different aspects of Depot-Free Multiple Traveling Salesperson Problems (DFmTSPs), which generalize the Multiple Traveling Salesperson Problem (mTSP). Unlike traditional mTSPs, DFmTSPs do not require the depot concept. Thus, they pose unique challenges that need to be addressed. This research primarily focuses on developing and analyzing mathematical models and algorithms for DFmTSPs. This document introduces innovative and novel integer programs that depend on the dummy depot concept. These integer programs show theoretical and practi- cal advantages since they are general enough to be useful for the main variants of DFmTSPs. Additionally, a two-phase constructive heuristic and a memetic algorithm are proposed to tackle large graph instances where exact methods are impractical. For the two-phase constructive heuristic, the cluster-first route-second technique is used. In the clustering phase, a heuristic for the Capacitated Vertex k-Center Problem is proposed. This heuristic is based on a relationship with the Minimum Capacitated Dominating Set. Afterward, for the routing phase, the farthest-first heuristic and Lin-Kernighan heuristic were used, the latter is one of the best-known heuristics for the classical Traveling Salesperson Problem (TSP) in the state-of-the-art. For the memetic algorithm, a deep study of the diversity of solutions is performed. Thus, diversity management techniques and novel genetic components are designed and analyzed. The performance of these algorithms is rigorously tested on various benchmark instances, demonstrating significant improvements in the quality of the returned solutions. The results underline the practical viability of the proposed models and algorithms, paving the way for future research in related optimization problems. Esta tesis aborda diferentes aspectos de los Problemas de Múltiples Agentes Viajeros sin almacenes (DFmTSPs, por sus siglas en inglés), los cuales generalizan el Problema de Múltiples Agentes Viajeros (mTSP). A diferencia del mTSP tradicional, los DFmTSPs no consideran el concepto de almacén. Por lo tanto, presentan retos únicos y específicos que deben ser considerados para su resolución. Esta investigación se centra en el desarrollo y análisis de modelos matemáticos y algoritmos para los DFmTSPs. Esta investigación propone formulaciones de programación entera que son inno- vadoras, novedosas, y que explotan el concepto de almacenes ficticios. Estas formula- ciones ofrecen ventajas teóricas y prácticas, ya que son lo suficientemente generales para abordar las principales variantes de los DFmTSPs. Además, se proponen una heurística constructiva de dos fases y un algoritmo memético para abordar instancias más grandes del estado del arte, en donde los métodos exactos resultan ser poco prácticos. Para la heurística constructiva de dos fases, se utiliza la técnica de cluster-first route-second (agrupar primero, enrutar después). En la fase de agrupamiento, se propone una heurística para el Problema de Localización de k Instalaciones Capacitadas (Capacitated Vertex k-center Problem), que se basa en una relación con el Conjunto Dominante Mínimo con Capacidades (Minimum Capacitated Dominating Set). Posteriormente, para la fase de enrutamiento se emplea la heurísticas farthest-first y la heurística Lin-Kernighan, la cual es considerada una de las mejores en el estado del arte para el problema clásico del Agente Viajero (TSP, por sus siglas en inglés). En cuanto al algoritmo memético, se realiza un estudio a profundidad de la diversi- dad de las soluciones. Para ello, se diseñan y analizan técnicas de gestión de diversidad explícita y operadores genéticos novedosos. El rendimiento de estos algoritmos es probado rigurosamente en diversas instancias del estado del arte, mostrando mejoras significativas en la calidad de las soluciones encontradas. Los resultados demuestran la viabilidad práctica de los modelos y de los algoritmos propuestos, además de sentar las bases para futuras investigaciones en problemas de optimización relacionados. | |
| Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| 2024-11 | |
| Tesis de doctorado | |
| Inglés | |
| Estudiantes Investigadores Público en general | |
| Cornejo Acosta, J. A., (2024), Models and Algorithms for Depot-Free Multiple Traveling Salesperson Problems, Tesis de Doctorado, Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| OTRAS ESPECIALIDADES TECNOLÓGICAS | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Doctorado en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| CORNEJOAJA_DCC.pdf | 2.14 MB | Adobe PDF | Visualizar/Abrir |