Algoritmos de Búsqueda en Entorno Variable para el Doble Problema del Viajante con Múltiples Pilas

Resumen

El Doble Problema del Viajante con M¶ultiples Pilas (DTSPMS) es un problema de entrega y recogida de mercanc¶³as que consiste en encontrar dos ciclos hamiltonianos en dos grafos distintos, uno para la recogida y otro para la entrega, cuya suma de longitudes sea m¶³nima. Se dispone de un conjunto de encargos determinados por una localizaci¶on de recogida y una de entrega, debi¶endose recoger cierta mercanc¶³a en la primera locali- zaci¶on y entregarse en la segunda. La carga recogida se almacena en varias pilas, cada una de las cuales obedece un principio LIFO (Last-In-First- Out): si dos encargos se almacenan en la misma pila deben entregarse en orden inverso a como fueron recogidos. No hay restricciones entre las pilas y no se permite reorganizar la carga. Las regiones de entrega y recogida se suponen muy alejadas geogr¶a¯camente, no siendo el trayecto entre ambas parte del problema. En este trabajo se presentan varios algoritmos de B¶usqueda en Entorno Variable para la resoluci¶on del DTSPMS, analizando su comportamiento y comparando los resultados obtenidos.