Benchmark data for the Single-Depot Multiple Traveling Salesman Problem (multiple-TSP)

Derived from the well-known Traveling Salesman Problem (TSP), the Multiple Traveling Salesman Problem (multiple-TSP) with single depot is a straightforward generalization, that involves further a new parameter - the number of salesmen. Several salesmen located in a given city (the depot) need to visit a set of interconnected cities, such that each city is visited exactly once (by a single salesman) while the total cost of their tours is minimized.

This page contains benchmark data for several multiple traveling salesman instances. The multiple-TSP instances were generated by taking 4 Traveling Salesman Problem (TSP) instances (eil51, berlin52, eil76 and rat99) from TSPLIB library and specifying 4 different values for the number of salesmen (i.e. 2, 3, 5, 7) to visit the cities. Therefore, it resulted a total of 16 multiple-TSP instances, where the depot city is considered to be the first city from the list of cities.

Table: Multiple-TSP instances

TSP instance n (# cities) m (#salesmen) MTSP instance

eil51

51

2

eil51-m2

3

eil51-m3

5

eil51-m5

7

eil51-m7

berlin52

52

2

berlin52-m2

3

berlin52-m3

5

berlin52-m5

7

berlin52-m7

eil76

76

2

eil76-m2

3

eil76-m3

5

eil76-m5

7

eil76-m7

rat99

99

2

rat99-m2

3

rat99-m3

5

rat99-m5

7

rat99-m7


Each of these multiple-TSP instances were solved using CPLEX optimizer based on an integer linear programming (ILP) model and the obtained results are reported for each instance in a separate table.

According to the imposed constraints on the formulation of single depot multiple-TSP (SD-MTSP) there are 3 differrent variants and for two of them, the obtained results will be reported in the sections below:


[1] Necula, R., Breaban, M., Raschip, M.: Performance Evaluation of Ant Colony Systems for the Single-Depot Multiple Traveling Salesman Problem, 10th International Conference on Hybrid Artificial Intelligence Systems (HAIS), 22-24 June, Bilbao, Spain, vol. 9121, pp. 257-268, 2015 [link]

[2] Necula, R., Breaban, M., Raschip, M.: Tackling the Bi-criteria Facet of Multiple Traveling Salesman Problem with Ant Colony Systems, 27th International Conference on Tools with Artificial Intelligence (ICTAI), 9-11 November, Vietri sul Mare, Italy, pp. 873-880, 2015 [link]; the source code of the algorithms investigated in this paper can be found at this link