1 Introduction
-
In the existing literature, GTSPs are considered only in a crisp environment.
-
Existing algorithms for GTSP are not capable of solving GTSPs in an imprecise environment.
-
The presence of multiple paths of any GTSP is overlooked/ignored by the researchers.
2 Problem definition and mathematical prerequisites
3 Swap sequence-based particle swarm optimization for GTSP
4 Genetic algorithm for GTSP
5 K-Opt operation for GTSP
6 Proposed algorithm for GTSP
6.1 GA algorithm for selection of cities from different groups to find the optimal path corresponding to a sequence of groups \(X_k(t)\)
6.2 K-Opt operation on sequence of groups for improvement of sequence of groups \(X_k(t)\)
-
Remove three edges (randomly selected) from the sequence of group \(X_k(t)\), it makes three sub-sequences of group \(X_{ki}(t)\), \(i=1,2,3\).
-
Reverses of the contents of these sub-sequence of groups are called revers_sub-sequence, represented as \({X_{ki}^r(t)}\), \(i=1,2,3\), i.e., \({X_{k1}^r(t)}\) = revers_sub-sequence of group\(X_{k1}(t)\), \({X_{k2}^r(t)}\) = revers_sub-sequence of \(X_{k2}(t)\), \({X_{k3}^r(t)}\) = revers_sub-sequence of \(X_{k3}(t)\).
-
Now, combining the sub-sequences of groups \(\{X_{k1}(t)\), \(X_{k2}(t)\), \(X_{k3}(t)\}\), \(\{X_{k1}^r(t)\), \(X_{k2}^r(t)\), \(X_{k3}^r(t)\},\) a new sequence of groups can be formed in the following eight combinations:×
7 Experimental results
Problem from TSPLIB | Number of cities (n) | Number of groups (m) | Optimal cost of the problem | Best cost obtained | Cost of the solution obtained in different runs | Average cost of the solutions | Error (%) | Computational time in second | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Run1 seed \(=\)1 | Run2 seed \(=\) 2 | Run3 seed \(=\) 3 | Run4 seed \(=\) 4 | Run5 seed \(=\) 5 | ||||||||
10ATT48 | 48 | 10 | 5394 | 5394 | 5394 | 5394 | 5394 | 5394 | 5394 | 5394.00 | 0.00 | 2.15 |
11EIL51 | 51 | 11 | 174 | 174 | 174 | 174 | 174 | 174 | 174 | 174.00 | 0.00 | 2.52 |
14ST70 | 70 | 14 | 316 | 316 | 316 | 316 | 316 | 316 | 316 | 316.00 | 0.00 | 3.42 |
16EIL76 | 76 | 16 | 209 | 209 | 209 | 209 | 209 | 209 | 209 | 209.00 | 0.00 | 5.62 |
16PR76 | 76 | 16 | 64,925 | 64,925 | 64,925 | 64,925 | 64,925 | 64,925 | 64,925 | 64,925.00 | 0.00 | 6.27 |
20RAT99 | 99 | 20 | 497 | 497 | 497 | 497 | 497 | 497 | 497 | 497.00 | 0.00 | 18.27 |
20KROA100 | 100 | 29 | 9711 | 9711 | 9711 | 9711 | 9711 | 9711 | 9711 | 9711.00 | 0.00 | 25.42 |
20KROB100 | 100 | 20 | 10,328 | 10,328 | 10,328 | 10,328 | 10,328 | 10,328 | 10,328 | 10,328.00 | 0.00 | 20.48 |
20KROC100 | 100 | 20 | 9554 | 9554 | 9554 | 9554 | 9554 | 9554 | 9554 | 9554.00 | 0.00 | 22.30 |
20KROD100 | 100 | 20 | 9450 | 9450 | 9450 | 9450 | 9450 | 9450 | 9450 | 9450.00 | 0.00 | 27.64 |
20KROE100 | 100 | 20 | 9523 | 9523 | 9523 | 9523 | 9523 | 9523 | 9523 | 9523.00 | 0.00 | 24.25 |
21EIL101 | 101 | 21 | 249 | 249 | 249 | 249 | 249 | 249 | 249 | 249.00 | 0.00 | 38.64 |
22PR107 | 107 | 22 | 27,898 | 27,898 | 27,898 | 27,898 | 27,898 | 27,898 | 27,898 | 27,898.00 | 0.00 | 33.96 |
25PR124 | 124 | 24 | 36,605 | 36,605 | 36,605 | 36,605 | 36,605 | 36,605 | 36,605 | 36,605.00 | 0.00 | 56.63 |
26BIER127 | 127 | 26 | 72,418 | 72,418 | 72,418 | 72,418 | 72,418 | 72,418 | 72,418 | 72,418.00 | 0.00 | 68.25 |
28PR136 | 136 | 28 | 42,570 | 42,570 | 42,570 | 42,570 | 42,570 | 42,570 | 42,570 | 42,570.00 | 0.00 | 74.28 |
29PR144 | 144 | 29 | 45,886 | 45,886 | 45,886 | 45,886 | 45,886 | 45,886 | 45,886 | 45,886.00 | 0.00 | 94.32 |
30KROB150 | 150 | 30 | 11,018 | 11,018 | 11,018 | 11,018 | 11,018 | 11,018 | 11,018 | 11,018.00 | 0.00 | 98.65 |
31PR152 | 152 | 31 | 51,576 | 51,576 | 51,576 | 51,576 | 51,576 | 51,576 | 51,576 | 51,576.00 | 0.00 | 150.32 |
40D198 | 198 | 40 | 10,557 | 10,557 | 10,557 | 10,557 | 10,557 | 10,557 | 10,557 | 10,557.00 | 0.00 | 198.62 |
46PR226 | 226 | 46 | 64,007 | 64,007 | 64,007 | 64,007 | 64,007 | 64,007 | 64,007 | 64,007.00 | 0.00 | 205.52 |
Problem form TSPLIB | Different optimal path | Cost of the solution |
---|---|---|
45,41,25,24,27,1,22,20,50,10,33 | ||
27,24,25,41,44,33,10,50,20,22,1 | ||
11EIL51 | 20,16,49,33,45,41,25,24,27,1,22 | 174 |
44,33,9,16,20,22,1,27,24,25,41 | ||
41,45,33,49,29,20,22,1,27,24,25 | ||
23,69,59,57,26,8,44,43,61,39,54,11,64,16 | ||
44,43,61,39,48,11,64,16,23,69,59,19,26,8 | ||
14ST70 | 11,64,16,23,69,59,57,4,7,26,44,61,39,54 | 316 |
43,44,8,26,19,59,69,23,16,64,11,54,39,61 | ||
8,44,43,61,39,62,11,64,16,23,69,59,19,26 | ||
59,11,38,39,9,25,49,41,42,62,2,48,37,15,13,14 | ||
9,25,49,41,42,22,47,37,27,52,46,8,59,11,58,39 | ||
16EIL76 | 9,39,38,11,59,8,52,45,29,37,47,22,42,41,49,25 | 209 |
14,13,15,37,48,30,62,42,23,49,25,9,39,58,11,59 | ||
59,8,52,45,5,37,47,42,43,23,49,25,9,39,72,11 | ||
26,35,34,53,71,80,89,87,95,83,65,56,57,48,30,11,2,4,7,17 | ||
7,4,2,11,30,48,57,56,65,83,95,87,89,80,71,53,34,35,26,17 | ||
20RAT99 | 11,30,48,57,56,65,83,95,87,89,80,62,53,34,35,26,17,7,4,2 | 497 |
7,5,2,11,30,48,57,56,65,83,95,87,89,80,71,53,34,35,26,17 | ||
65,83,95,87,89,80,71,53,34,35,26,17,7,4,2,11,30,48,57,56 | ||
24,84,47,98,77,83,29,48,78,96,82,44,73,69,67,8,92,75,66,18 | ||
77,83,29,48,78,96,82,44,73,69,67,8,92,75,66,18,24,84,47,98 | ||
20KROA100 | 96,78,48,29,83,77,98,47,84,24,18,66,75,92,8,67,69,73,44,82 | 9711 |
92,75,66,18,24,84,47,98,77,83,29,48,78,96,82,44,73,69,67,8 | ||
2,75,66,18,24,84,47,98,77,83,29,48,78,96,82,44,73,69,67,8 | ||
49,64,11,10,30,20,35,78,29,54,39,23,41,15,14,44,85,6,60,8,47 | ||
39,23,41,57,14,44,93,6,83,8,47,49,64,11,10,30,20,35,78,29,54 | ||
21EIL101 | 44,14,42,22,23,39,54,29,78,35,20,30,10,11,64,49,47,8,60,6,96 | 249 |
11,64,49,47,8,60,6,85,44,14,42,22,23,39,54,29,34,35,20,30,10 | ||
30,10,11,64,49,47,8,60,6,85,44,14,57,41,23,39,54,29,34,35,20 |
Problems from TSPLIB | Number of cities (n) | Number of groups (m) | Optimal cost of the problem | Results obtained after introduction of different amount of fuzziness | Computational time in second | ||
---|---|---|---|---|---|---|---|
5% fuzziness | 10% fuzziness | 15% fuzziness | |||||
10ATT48 | 48 | 10 | 5394 | (5364.68, 5394.00, 5428.78) | (5333.65, 5394.00, 5455.45) | (5301.65, 5394.00, 5489.45) | 5.24 |
11EIL51 | 51 | 11 | 174 | (143.62, 174.00, 202.78) | (113.24, 174.00, 231.57) | (82.86, 174.00, 260.36) | 9.15 |
14ST70 | 70 | 14 | 316 | (287.48, 316.00, 346.64) | (253.56, 316.00, 384.99) | (230.46, 316.00, 407.94) | 52.62 |
16EIL76 | 76 | 16 | 209 | (166.83, 209.00, 253.21) | (143.83, 209.00, 307.12) | (69.91, 209.00, 331.18) | 67.97 |
20RAT99 | 99 | 20 | 497 | (449.95, 499.00, 540.89) | (414.27, 497.00, 598.81) | (373.85, 497.00, 655.16) | 105.25 |
20KROA100 | 100 | 20 | 9711 | (9673.45, 9711.00, 9751.23) | (9643.87, 9713.00, 9794.45) | (9619.53, 9714.00, 9831.43) | 110.32 |
21EIL101 | 101 | 21 | 249 | (205.45, 249.00, 300.63) | (163.83, 250.00, 372.62) | (119.66, 252.00, 409.43) | 99.65 |
22PR107 | 107 | 22 | 27,898 | (27863, 27898, 27937) | (27829, 27900, 27982) | (27795, 27900, 28023) | 125.84 |
26BIER127 | 127 | 26 | 72,418 | (72373.53, 72422.00, 72457.76) | (72345.65, 72431.00, 72500.43) | (72309.34, 72439.00, 72549.34) | 160.42 |
28PR136 | 136 | 28 | 42,570 | (42547.39, 42579.00, 42624.67) | (42520.76, 42585.00, 42667.30) | (42493.49, 42588.00, 42697.38) | 205.65 |
29PR144 | 144 | 29 | 45,886 | (45852.67, 45893.56, 42928.56) | (458826.65, 45905.00, 45836.87) | (45792.54, 45902.00, 45987.25) | 250.75 |
Problem from TSPLIB | Amount of fuzziness introduced (%) | Different optimal paths obtained | Cost of the solution |
---|---|---|---|
11EIL51 | 5 | 24, 27, 1, 22, 20, 29, 10, 33, 45, 41, 25 | (143.62, 174.00, 202.78) |
44, 33, 9, 16, 20, 22, 1, 27, 24, 25, 41 | (143.87, 174.00, 203.42) | ||
29, 49, 33, 44, 41, 25, 24, 27, 1, 22, 20 | (143.83, 174.00, 204.05) | ||
24, 27, 1, 22, 20, 29, 10, 33, 45, 41, 25 | (113.24, 174.00, 231.57) | ||
10 | 44, 33, 9, 16, 20, 22, 1, 27, 24, 25, 41 | (113.74, 174.00, 232.84) | |
29, 49, 33, 44, 41, 25, 24, 27, 1, 22, 20 | (113.66, 174.00, 234.10) | ||
24, 27, 1, 22, 20, 29, 10, 33, 45, 41, 25 | (82.86, 174.00, 260.36) | ||
15 | 44, 33, 9, 16, 20, 22, 1, 27, 24, 25, 41 | (83.62, 174.00, 262.26) | |
29, 49, 33, 44, 41, 25, 24, 27, 1, 22, 20 | (83.50, 174.00, 264.15) | ||
16, 64, 11, 54, 39, 40, 68, 8, 26, 4, 57, 59, 69, 23 | (287.48, 316.00, 346.64) | ||
5 | 16, 64, 11, 54, 39, 9, 68, 8, 26, 4, 57, 59, 69, 23 | (290.87, 316.00, 348.68) | |
9, 68, 8, 26, 4, 57, 59, 69, 23, 16, 64, 11, 54, 39 | (290.87, 316.00, 348.68) | ||
16, 64, 11, 54, 39, 40, 68, 8, 26, 4, 57, 59, 69, 23 | (253.56, 317.00, 384.99) | ||
14ST70 | 10 | 23, 16, 64, 11, 54, 39, 61, 43, 44, 8, 26, 19, 59, 69 | (247.75, 316.00, 378.79) |
26, 8, 68, 40, 39, 54, 11, 64, 16, 23, 69, 59, 57, 4 | (243.65, 316.00, 370.76) | ||
16, 64, 11, 54, 39, 40, 68, 8, 26, 4, 57, 59, 69, 23 | (230.46, 316.00, 407.94) | ||
15 | 16, 64, 11, 54, 39, 9, 68, 8, 26, 4, 57, 59, 69, 23 | (240.63, 316.00, 414.05) | |
57, 59, 69, 23, 16, 64, 11, 54, 39, 40, 68, 8, 26, 4 | (230.46, 316.00, 407.94) | ||
58, 11, 59, 8, 52, 45, 5, 37, 28, 42, 41, 63, 16, 3, 25, 39 | (166.90, 211.00, 253.17) | ||
5 | 22, 42, 23, 49, 50, 25, 39, 72, 11, 59, 8, 52, 45, 5, 37, 28 | (166.83, 209.00, 253.21) | |
49, 50, 25, 39, 58, 11, 59, 8, 46, 52, 27, 37, 47, 22, 42, 23 | (161.09, 209.00, 251.97) | ||
72, 11, 59, 8, 52, 45, 29, 37, 21, 42, 41, 63, 16, 3, 25, 39 | (130.31, 211.00, 300.85) | ||
16EIL76 | 10 | 47, 37, 29, 45, 52, 8, 59, 11, 58, 39, 9, 25, 49, 41, 42, 22 | (143.83, 209.00, 307.12) |
8, 59, 11, 72, 39, 25, 50, 49, 41, 42, 22, 28, 37, 29, 45, 52 | (155.31, 209.00, 308.70) | ||
37, 47, 22, 42, 41, 49, 50, 25, 39, 58, 11, 59, 8, 46, 52, 27 | (69.91, 209.00, 331.18) | ||
15 | 22, 42, 23, 49, 25, 9, 39, 58, 11, 59, 8, 52, 45, 5, 37, 28 | (78.31, 209.00, 332.85) | |
49, 50, 25, 39, 58, 11, 59, 8, 52, 45, 29, 37, 28, 42, 43, 23 | (72.93, 209.00, 331.02) | ||
74, 56, 57, 39, 30, 11, 2, 4, 7, 17, 26, 34, 44, 53, 71, 80, 89, 87, 95, 83 | (449.95, 499.00, 540.89) | ||
5 | 74, 56, 57, 39, 30, 11, 2, 4, 7, 17, 26, 34, 44, 53, 71, 80, 89, 87, 95, 83 | (449.95, 499.00, 540.89) | |
71, 53, 52, 43, 35, 26, 17, 7, 4, 2, 11, 30, 57, 56, 65, 83, 95, 97, 88, 80 | (453.41, 502.00, 561.27) | ||
74, 56, 57, 39, 30, 11, 2, 4, 7, 17, 26, 34, 44, 53, 71, 80, 89, 87, 95, 83 | (405.95, 499.00, 611.89) | ||
20RAT99 | 10 | 52, 43, 35, 17, 7, 5, 2, 11, 22, 31, 57, 56, 65, 83, 95, 87, 89, 80, 71, 53 | (411.44, 504.00, 612.10) |
48, 57, 56, 74, 83, 95, 87, 89, 80, 71, 53, 34, 35, 26, 17, 7, 4, 2, 11, 30 | (414.27, 497.00, 598.81) | ||
62, 80, 88, 97, 95, 83, 74, 56, 57, 38, 20, 2, 4, 7, 17, 26, 35, 34, 52, 53 | (333.85, 503.00, 658.96) | ||
15 | 2, 5, 7, 17, 26, 35, 34, 53, 71, 80, 79, 97, 95, 83, 65, 56, 57, 48, 30, 11 | (363.16, 498.00, 635.97) | |
71, 53, 34, 35, 26, 17, 7, 5, 2, 11, 30, 48, 57, 56, 65, 83, 95, 87, 89, 80 | (373.85, 497.00, 655.16) |
Problems from TSPLIB | Cost of optimal path | Cost of the best path and the corresponding | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Error (%) obtained using | ||||||||||||
PSO | Error (%) | GA | Error (%) | Time (S.) | GCGA | Error (%) | Time (S.) | Proposed algorithm | Error (%) | Time (S.) | ||
11EIL51 |
174
| 176 |
3.74
| 174 |
0.00
|
0.87
| 176 |
1.15
| 2.52 |
174
|
0.00
| 2.52 |
14ST70 |
316
| 315 |
0.62
|
316
|
0.00
|
7.3
|
316
|
0.00
| 1.23 |
316
|
0.00
| 3.42 |
16EIL76 |
209
| 214 |
5.46
|
209
|
0.00
|
9.4
| 214 |
2.87
| 1.45 |
209
|
0.00
| 5.62 |
20KROA100 |
9711
| 9758 |
3.26
|
9711
|
0.00
|
18.4
| 9758 |
1.15
| 1.93 |
9711
|
0.00
| 25.42 |
20KROD100 |
9450
|
9450
|
2.46
|
9450
|
0.00
|
14.3
|
9450
|
0.00
| 1.96 |
9450
|
0.00
| 27.64 |
21EIL101 |
249
| 254 |
9.69
|
249
|
0.00
|
25.6
| 251 |
0.08
| 1.79 |
249
|
0.00
| 38.64 |
22PR107 |
27,898
| 27,901 |
1.56
|
27,898
|
0.00
|
7.4
|
27,898
|
0.04
| 2.25 |
27,898
|
0.00
| 33.96 |
25PR124 |
36,605
| 36,782 |
2.20
|
36,605
|
0.00
|
25.9
|
36,605
|
2.12
| 2.51 |
36,605
|
0.00
| 56.63 |
29PR144 |
45,886
| 45,890 |
4.04
|
45,886
|
0.00
|
8.2
| 45,890 |
0.34
| 2.67 |
45,886
|
0.00
| 94.32 |
30KROB150 |
11,018
| 11,085 |
7.93
|
11,018
|
0.00
|
60.6
| 11,117 |
3.53
| 3.26 |
11,018
|
0.00
| 98.65 |
40D198 |
10,557
| 10,693 |
5.20
|
10,557
|
0.00
|
763.1
|
10,557
|
0.42
| 3.50 |
10,557
|
0.00
| 198.62 |
Problem from TSPLIB | Probability of mutation (pm) | Probability of crossover (pc) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 |
0.8
| 0.9 | 1 | ||
25PR124 | 196.92 | 314.46 | 320.28 | 131.28 | 206.24 | 209.47 | 75.68 | 246.24 | 143.72 | 243.85 | |
29PR144 | 1 | 163.42 | 180.58 | 148.25 | 57.95 | 246.65 | 85.46 | 72.25 | 162.24 | 192.72 | 126.35 |
30KROB150 | 186.52 | 242.65 | 140.35 | 141.46 | 259.12 | 143.15 | 138.62 | 293.35 | 320.52 | 190.88 | |
25PR124 | 172.4 | 56.99 | 163.5 | 58.28 | 293.25 | 102.47 | 85.68 | 259.24 | 118.65 | 178.12 | |
29PR144 | 0.9 | 187.32 | 332.98 | 322.12 | 141.32 | 230.65 | 234.32 | 161.32 | 278.32 | 323.32 | 265.35 |
30KROB150 | 181.65 | 223.52 | 134.52 | 144.65 | 255.68 | 135.95 | 221.12 | 428.32 | 308.52 | 190.88 | |
25PR124 | 70.25 | 66.85 | 233.27 | 127.95 | 246.75 | 62.95 | 57.65 | 99.14 | 286.65 | 163.87 | |
29PR144 | 0.8 | 154.42 | 126.58 | 232.25 | 123.95 | 179.65 | 136.46 | 286.25 | 126.24 | 192.72 | 254.35 |
30KROB150 | 116.25 | 157.65 | 123.54 | 251.94 | 240.32 | 167.65 | 168.32 | 210.65 | 391.32 | 205.98 | |
25PR124 | 90.52 | 192.62 | 55.36 | 61.75 | 148.45 | 167.86 | 81.65 | 229.64 | 70.35 | 177.65 | |
29PR144 | 0.7 | 119.32 | 123.45 | 163.65 | 391.14 | 151.65 | 263.51 | 148.95 | 216.45 | 177.65 | 189.40 |
30KROB150 | 225.65 | 259.42 | 145.65 | 194.35 | 129.64 | 165.40 | 192.32 | 189.65 | 291.38 | 192.98 | |
25PR124 | 86.58 | 63.85 | 167.65 | 38.65 | 90.25 | 81.32 | 65.95 |
56.63
| 103.65 | 388.25 | |
29PR144 |
0.6
| 237.32 | 123.54 | 213.65 | 115.65 | 106.32 | 118.45 | 270.98 |
94.32
| 200.45 | 194.32 |
30KROB150 | 134.65 | 264.65 | 140.35 | 162.65 | 242.65 | 116.65 | 201.25 |
98.65
| 115.65 | 225.45 | |
25PR124 | 65.32 | 57.32 | 113.25 | 38.65 | 221.32 | 163.65 | 66.65 | 92.32 | 132.65 | 117.32 | |
29PR144 | 0.5 | 111.62 | 119.12 | 198.45 | 285.65 | 204.65 | 147.85 | 89.62 | 99.32 | 303.32 | 205.46 |
30KROB150 | 125.32 | 210.65 | 152.65 | 120.95 | 164.65 | 152.65 | 91.35 | 110.68 | 215.55 | 320.20 | |
25PR124 | 90.32 | 32.65 | 71.95 | 54.65 | 68.96 | 254.65 | 74.65 | 84.65 | 128.65 | 343.65 | |
29PR144 | 0.4 | 71.65 | 113.64 | 210.46 | 305.87 | 246.65 | 185.46 | 122.94 | 197.41 | 167.72 | 120.10 |
30KROB150 | 145.32 | 162.65 | 192.54 | 230.98 | 105.66 | 243.65 | 119.35 | 148.65 | 240.65 | 192.65 | |
25PR124 | 104.25 | 71.25 | 43.36 | 74.62 | 62.52 | 52.62 | 80.52 | 92.62 | 152.65 | 241.82 | |
29PR144 | 0.3 | 182.45 | 245.65 | 131.65 | 141.62 | 81.74 | 91.75 | 184.46 | 82.65 | 90.12 | 216.85 |
30KROB150 | 256.65 | 305.65 | 190.45 | 165.98 | 225.85 | 298.65 | 115.85 | 245.10 | 192.45 | 323.21 | |
25PR124 | 72.36 | 73.62 | 265.65 | 171.63 | 47.32 | 68.32 | 100.62 | 67.32 | 64.65 | 90.25 | |
29PR144 | 0.2 | 621.45 | 357.25 | 217.65 | 40.65 | 126.98 | 559.65 | 146.65 | 77.62 | 155.95 | 194.65 |
30KROB150 | 512.15 | 242.65 | 165.25 | 141.46 | 259.12 | 143.15 | 162.35 | 299.35 | 312.52 | 250.88 | |
25PR124 | 104.36 | 267.32 | 132.28 | 108.32 | 67.36 | 159.36 | 215.32 | 206.32 | 143.72 | 167.32 | |
29PR144 | 0.1 | 169.25 | 424.35 | 625.65 | 848.64 | 665.32 | 590.32 | 805.52 | 246.32 | 406.32 | 328.20 |
30KROB150 | 632.32 | 325.65 | 140.35 | 163.35 | 259.12 | 142.35 | 112.75 | 393.35 | 220.52 | 170.88 |
Problem from TSPLIB | Optimal cost of the solution | Cost of the best path obtained by the hybrid algorithm | |
---|---|---|---|
PSO\(+\) GA\(+\) 2−Opt | PSO\(+\)GA\(+\) 3−Opt | ||
11EIL51 |
174
|
174
|
174
|
14ST70 |
316
|
316
|
316
|
16EIL76 |
209
| 212 |
209
|
20KROA100 |
9711
| 9775 |
9711
|
20KROD100 |
9450
| 9502 |
9450
|
21EIL101 |
249
| 255 |
249
|
22PR107 |
27,898
| 27,905 |
27,898
|
25PR124 |
36,605
| 36,792 |
36,605
|
29PR144 |
45,886
| 45,965 |
4588
|