Análisis de double tree-shortcutting para el problema del vendedor viajero

dc.contributor.advisorVerschae, José
dc.contributor.authorRogers, Manuel
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2018-12-28T19:01:09Z
dc.date.available2018-12-28T19:01:09Z
dc.date.issued2018
dc.descriptionTesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2018
dc.description.abstractEl 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.
dc.format.extentxi, 49 hojas
dc.identifier.doi10.7764/tesisUC/ING/22236
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/22236
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/22236
dc.language.isoes
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.subject.ddc510
dc.subject.deweyMatemática física y químicaes_ES
dc.subject.otherOptimización matemática.es_ES
dc.subject.otherÁrboles (Teoría de los grafos)es_ES
dc.titleAnálisis de double tree-shortcutting para el problema del vendedor viajeroes_ES
dc.typetesis de maestría
sipa.codpersvinculados243006
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Roger_Manuel.pdf
Size:
634.44 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.31 KB
Format:
Item-specific license agreed upon to submission
Description: