Bounded Single-Depot Multiple Traveling Salesman Problem (multiple-TSP)
This variant of multiple-TSP (called bounded multiple-TSP) restricts the number of cities a salesman must visit in its tour, by imposing lower and upper bounds regarding the traveled cities. Therefore the number of nodes a salesman can visit lies within a predetermined interval with the aim of obtaining balanced solutions. The problem is to find the tours of each salesman such that the previous restrictions are satisfied and the overall cost of visiting all nodes is minimized. Such restrictions appear in real-life applications where the purpose is to have a good balance of workloads for the salesmen.
The values for the lower (denoted by K) and upper (denoted by L) bounds, that are parameters in the ILP model solved with CPLEX, were obtained after running 30 times the k-Means clustering algorithm on the same instance and choosing the partition with the minimum intra-cluster variance. For the chosen partition, K was set equal to the size of the smallest cluster and L equal to the size of the largest cluster.
Meaning of the table columns
- Instance Name: denotes the name of the TSP instance taken from TSPLIB
- M: denotes the number of salesmen from the multiple-TSP instance that will have to visit the cities
- K: denotes the lower bound, more specifically the minimum number of cities a salesman must visit in his tour
- L: denotes the upper bound, more specifically the maximum number of cities a salesman must visit in his tour
- Optimal Cost: a single number indicates that the optimal length of all the tours traveled by the salesmen is known; otherwise an interval is indicated with a lower and upper bound for the optimal tour length
- Tours: points to a file containing the tours traveled by each salesman along with the number of cities visited in a tour by each salesman and the individual cost of each tour
- Graphic: points to a file which graphically depicts the tours that each salesman traveled
eil51 – 51-city problem (Christofides/Eilon)
For a visualization of the distribution of cities click here (the depot city is marked with red color)
| Instance Name | M | K | L | Optimal Cost | Tours | Graphic |
|---|---|---|---|---|---|---|
|
2 |
23 |
27 |
442.32 |
|||
|
3 |
15 |
20 |
464.11 |
|||
|
5 |
7 |
12 |
[519.10, 529.70] |
|||
|
7 |
5 |
10 |
[584.02, 605.21] |
berlin52 – 52 locations in Berlin (Groetschel)
For a visualization of the distribution of cities click here (the depot city is marked with red color)
| Instance Name | M | K | L | Optimal Cost | Tours | Graphic |
|---|---|---|---|---|---|---|
|
2 |
10 |
41 |
7753.89 |
|||
|
3 |
10 |
27 |
8106.85 |
|||
|
5 |
6 |
17 |
[8894.50, 9126.33] |
|||
|
7 |
4 |
17 |
[9415.99, 9870.02] |
eil76 – 76-city problem (Christofides/Eilon)
For a visualization of the distribution of cities click here (the depot city is marked with red color)
| Instance Name | M | K | L | Optimal Cost | Tours | Graphic |
|---|---|---|---|---|---|---|
|
2 |
36 |
39 |
558.59 |
|||
|
3 |
21 |
30 |
579.30 |
|||
|
5 |
12 |
17 |
[623.88, 680.67] |
|||
|
7 |
7 |
15 |
[675.38, 759.90] |
rat99 – Rattled grid (Pulleyblank)
For a visualization of the distribution of cities click here (the depot city is marked with red color)
| Instance Name | M | K | L | Optimal Cost | Tours | Graphic |
|---|---|---|---|---|---|---|
|
2 |
46 |
52 |
[1296.35, 1350.73] |
|||
|
3 |
27 |
36 |
[1357.30, 1519.49] |
|||
|
5 |
13 |
30 |
[1523.95, 1855.83] |
|||
|
7 |
9 |
22 |
[1712.15, 2291.82] |
Each of the below tables and graphics reflects the results obtained with the methods described in the paper "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, 22nd-24th June, 2015"
Table 3: The performance of the ACS variants for the berlin52 instance
Table 4: The performance of the ACS variants for the eil76 instance
Table 5: The performance of the ACS variants for the rat99 instance
Fig. 3: Results obtained in 50 runs for berlin52: a) total cost, b) amplitude of the costs of tours; the groups correspond to different settings for m: 2, 3, 5, 7
Fig. 4: Results obtained in 50 runs for eil76: a) total cost, b) amplitude of the costs of tours; the groups correspond to different settings for m: 2, 3, 5, 7
Fig. 5: Results obtained in 50 runs for rat99: a) total cost, b) amplitude of the costs of tours; the groups correspond to different settings for m: 2, 3, 5, 7
Fig. 6: Results obtained in 50 runs for a) eil51, b) berlin52, c) eil76 and d) rat99: confidence intervals for the means computed for total costs; the four groups on each plot correspond to different settings for m: 2, 3, 5, 7