M. D. Batista Galván, J. Riera Ledesma, J. J. Salazar González
El Double Travelling Salesman Problem with Multiple Stacks es un problema de recogida y entrega de mercancía en el que todo el proceso de recogida se efectúa de forma previa al proceso de entrega. El transporte de la mercancía desde el área de recogida hasta el área de entrega se lleva a cabo en un único vehículo con un contenedor organizado en varias pilas, es decir sobre estructuras con organización LIFO, y capacidad limitada. Puesto que no se puede reorganizar la mercancía dentro del contenedor, el orden de recogida repercute en el orden de entrega. El problema consiste en encontrar los dos circuitos hamiltonianos, asociados al tour de recogida y de entrega respectivamente, de menor coste, compatible con la estructura de almacenamiento asociada al contenedor. Se presenta en este trabajo un algoritmo de ramificación y corte basado en desigualdades obtenidas a partir del estudio de la descomposición de Benders de un formulación matemática previa.
Palabras clave: 2TSPMS, traveling salesman problem, pickup and delivery TSP, Branch-and-Cut
Programado
VB4 Problemas de rutas
20 de abril de 2012 10:30
Sala París
