Análisis de double tree-shortcutting para el problema del vendedor viajero
Loading...
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
El problema del vendedor viajero consiste en, dado un grafo completo, encontrar un ciclo de costo mínimo que visite todos los nodos del grafo exactamente una vez. Este problema es difícil de resolver y está presente en múltiples áreas de la optimización, ya sea como el objetivo principal o un sub-problema. Dentro de las áreas más comunes en donde se puede encontrar este problema están la logística de equipos o ruteo de vehículos. La relevancia actual de buscar optimizar rutas y tours en distintos rubros ha impulsado la investigación de este problema, por lo que se han hecho varios análisis desde hace décadas y aún se realizan avances sobre sus diversas variantes. El análisis de los algoritmos de aproximación que forman ciclos Eulerianos para el problema del vendedor viajero se centra en la formación de dicho ciclo y no en la conversión del ciclo Euleriano a un tour utilizando técnicas de shortcutting. En particular, estaba la pregunta abierta para algoritmos de Double Tree Shortcutting en el caso Euclideano de si es posible tener un factor de aproximación menor a 2. En esta tesis cerramos esa pregunta mediante la construcción de una instancia en donde existe un ciclo Hamiltoniano que tiene un peso equivalente al del árbol generador de costo mínimo y no existen reducciones relevantes de costos al convertir el ciclo Euleriano del árbol generador duplicado en uno Hamiltoniano sin importar de qué manera se haga la transformación. Esta instancia particular se contrasta con un escenario esperado de puntos aleatorios, en donde sí se puede reducir el costo del ciclo en un factor constante. Otro resultado de esta tesis es una aproximación a un factor constante de la reducción máxima que se puede hacer con técnicas de shortcutting a un ciclo Euleriano que viene de un árbol generador duplicado. Finalmente, se aborda un caso particular, el cual es cualquier instancia en donde no existan shortcuts que tengan una reducción local de los costos importante. En este caso, se puede concluir que el peso del árbol generador mínimo es cercano al peso del camino más largo de dicho árbol, lo cual implica que el árbol generador duplicado tiene un factor de aproximación menor a 2 sin necesidad de realizar ningún atajo. Esto es un primer avance en caracterizar el factor de aproximación del algoritmo Double Tree Shortcutting y parametrizarlo en función de la estructura de las instancias.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2018