Introducción

• El Doble Problema del Viajante con Múltiples Pilas (DTSPMS, Double Traveling Salesman Problem with Multiple Stacks) fue introducido por Hanne L. Petersen en el año 2006 en un technical report.
   

• El DTSPMS es NP-duro y bastante más difícil de resolver que el TSP.
   

• Hay más información disponible acerca de los primeros trabajos sobre el DTSPMS, además de las primeras instancias generadas para el problema (de 33 y 66 encargos de tamaño), en la web de Hanne L. Petersen: http://www2.imm.dtu.dk/~hlp/ 

• He realizando mi tesis doctoral sobre este problema. Resolver instancias de tamaño razonable de forma exacta es computacionalmente inviable, por lo que nos hemos centrado sobre todo en enfoques heurísticos.

Instancias para el DTSPMS

• Las primeras instancias para el DTSPMS fueron generadas por Hanne L. Petersen y están disponibles en su web http://www2.imm.dtu.dk/~hlp/.
   

• Estas instancias y todas las que se generaron posteriormente siguen el formato que se utiliza habitualmente para instancias del TSP, y que se utiliza, por ejemplo, para el software Concorde.
   

• Cada instancia viene determinada por dos archivos .tsp con nombres idénticos salvo el último carácter: el archivo cuyo nombre acaba en p contiene los datos relativos al grafo de recogidas (pickups) y el acabado en d al grafo de entregas (deliveries).
   

• Se han generado 3 conjuntos de 10 problemas con 33, 66 y 132 encargos, respectivamente, que se han utilizado para calibrar los parámetros de los algoritmos utilizados. Cada conjunto de datos está disponible a continuación en un archivo .zip:

Conjunto C33 (10 problemas de 33 encargos)

Conjunto C66 (10 problemas de 66 encargos)

Conjunto C132 (10 problemas de 132 encargos)

• También se ha generado otro conjunto de 20 problemas con 132 encargos para evaluar el comportamiento de las heurísticas diseñadas para problemas de mayor dimensión, completando los otros conjuntos de problemas de tamaño 33 y 66 generados para los primeros estudios sobre el DTSPMS. Estas instancias de tamaño 132 están disponibles a continuación en un archivo .zip:

Conjunto T132 (20 problemas de 132 encargos)

• Recientemente se han generado otros conjuntos de instancias en las que las localizaciones de recogida y entrega no se generan uniformemente, sino que están agrupadas formando clústers. En total se han considerado 5 tipos de instancias y se han generado 10 instancias de cada tipo con 33, 66 y 132 encargos. Los archivos de datos de estas instancias están disponibles a continuación en un archivo .zip:
  
        Conjunto Clusters (150 problemas, 5 tipos, tamaño 33, 66 y 132)

Algoritmos heurísticos

• Los primeros algoritmos heurísticos aplicados al problema (H. L. Petersen, 2006) fueron una Búsqueda Tabú, un Temple Simulado y un algoritmo de Steepest Descent, en los cuales se utilizaban 2 estructuras de entornos para la realización de las búsquedas locales.
   

• Posteriormente propusimos otras 4 estructuras de entornos diferentes que se utilizaron, junto con las dos anteriores, para diseñar un algoritmo de Búsqueda en Entorno Variable (VNS) para resolver el DTSPMS. Los detalles de las estructuras de entornos diseñadas y los algoritmos desarrollados se pueden encontrar en las siguientes referencias:
  
  - A. Felipe, M.T. Ortuño, G. Tirado. The Double Traveling Salesman Problem with Multiple Stacks: a Variable Neighborhood Search approach. Computers & Operations Research 36: 2983-2993 (2009).
  
  - A. Felipe, M.T. Ortuño, G. Tirado. New neighborhood structures for the Double Traveling Salesman Problem With Multiple Stacks. TOP 17: 190-213 (2009).
   

Presentaciones

• Aquí tienes disponible la presentación (en inglés) que utilicé en el EURO XXII en Praga, en julio de 2007, en la que se presentan las 6 estructuras de entornos para el problema, los algoritmos VNS en los que se utilizan y algunos resultados computacionales obtenidos.