Please use this identifier to cite or link to this item: http://repositorio.udec.cl/jspui/handle/11594/6640
Title: Formulaciones y algoritmos exactos para el problema del vendedor viajero asimétrico selectivo con múltiples visitas.
Authors: Aguayo Bustos, Maichel Miguel; supervisor de grado
Slater Carrasco, José Manuel
Keywords: Problema de Vendedor Viajero;Optimización Combinatoria;Programación Heurística;Algoritmos
Issue Date: 2018
Publisher: Universidad de Concepción.
Abstract: Este trabajo, aborda una extensión del problema vendedor viajero asimétrico (ATSP), denominado problema del vendedor viajero selectivo asimétrico con múltiples visitas (SHMATSP). El objetivo en este problema es encontrar un tour que comience y termine en el nodo inicial, que maximice el beneficio obtenido por la visita de nodos, sujeto a la restricción de distancia máxima permitida y la posibilidad de visitar algunos nodos más de una vez. Para capturar el S-HMATSP se proponen tres modelos de programación lineal entera, uno de tamaño polinomial y dos de tamaño exponencial. Para resolver el S-HMATSP, se diseñan dos tipos de algoritmos exactos, un método secuencial de cutting planes y otro paralelo de Branch-and-Cut, ambos algoritmos resuelven relajaciones del problema y agregan cortes para eliminar subtours desde soluciones enteras. En instancias que involucran entre 300 y 1001 nodos, los algoritmos propuestos muestran una clara superioridad sobre los métodos de descomposición de Benders y Branch-and-Cut disponibles en CPLEX.
Description: Tesis Para optar al grado de Magíster en Ingeniería Industrial.
URI: http://repositorio.udec.cl/jspui/handle/11594/6640
metadata.dc.source.uri: https://go.openathens.net/redirector/udec.cl?url=http://tesisencap.udec.cl/concepcion/slater_c_j/index.html
Appears in Collections:Ingeniería Industrial - Tesis Magister

Files in This Item:
File Description SizeFormat 
Resumen.pdf132,93 kBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons