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