Formulaciones y algoritmos exactos para el problema del vendedor viajero asimétrico selectivo con múltiples visitas.

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.