• The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) was introduced by Hanne L. Petersen in 2006 in a technical report.

  • The DTSPMS is NP-hard and quite more difficult to solve than the TSP.

  • There is more information available about the first papers related to the DTSPMS and the first problem instances generated for it (sizes of 33 and 66 orders) in Petersen's web site:

  • I approached this problem on my PhD thesis (in Spanish). Solving problem instances of reasonable size is computationally intractable, so we have concentrated on heuristics.


Instances for the DTSPMS

  • The first instances for the DTSPMS were generated by Hanne L. Petersen and they are available in her web site:

  • These instances and all the ones generated afterwards are available in the TSP-format, that is used, for example, by Concorde software.

  • Each instance is determined by two .tsp files with identical names but the last character: the file ending with a p character contains the data corresponding to the pickup network and the one ending with a d contains the data corresponding to the delivery network.

  • 3 sets of 10 instances with 33, 66 and 132 orders were generated for calibration of parameters. These 3 sets are available here in a .zip file:

Set C33 (10 instances with 33 orders)

Set C66 (10 instances with 66 orders)

Set C132 (10 instances with 132 orders)

  • We also generated another set of 20 instances with 132 orders to evaluate the performance of the designed heuristics for larger instances, complementing the other two sets of instances with size 33 and 66 that were generated in the first papers on the DTSPMS. These 132-order instances are available here in a .zip file:

Set T132 (20 instances with 132 orders)

  • Recently we have also generated other sets of instances in which pickup and delivery locations are not generated uniformly, but they are grouped in clusters of different sizes. We have considered 5 types of instances and 3 sizes (33, 66 and 132 orders) and 10 instances of each type have been generated. These instances are available here in a .zip file:

          Set Clusters (150 instances, 5 types, sizes 33, 66 and 132)


Heuristic algorithms

  • The first heuristic algorithms that were applied to the DTSPMS (H. L. Petersen, 2006) were Tabu SearchSimulated Annealing and Steepest Descent, using 2 neighborhood structures to perform local search.

  • Then we proposed 4 new different neighborhood structures that were used, together with the two other existing ones, to design a Variable Neighborhood Search (VNS) algorithm for the DTSPMS. The designed neighborhood structures and the developed algorithms are detailed in the following references:

    - 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).


  • Here you can donwload the presentation (in English) that I used in the EURO XXII conference held in Prague in july 2007. In this presentation you will find the 6 neighborhood structures defined for the DTSPMS, the VNS algorithms that we designed for it and some preliminary computational results.

Go up



                Gregorio Tirado Domínguez. Depto. Estadística e Investigación Operativa de la UCM.               Last update: 11th July 2010