Introduction
Related work
Ant Colony system
Max-Min Ant system
Information entropy
Shapley value
Proposed algorithm
Cooperative game strategy
Dynamic collaborative mechanism
Pheromone fusion mechanism
Diversity description
Pheromone fusion strategy
Public path recommendation strategy
Algorithm description
Experiment analysis
Parameters setting
α | β | ρ | ζ | q0 | |
---|---|---|---|---|---|
Level 1 | 1 | 2 | 0.1 | 0.1 | 0.6 |
Level 2 | 2 | 3 | 0.2 | 0.2 | 0.7 |
Level 3 | 3 | 4 | 0.3 | 0.3 | 0.8 |
Level 4 | 4 | 5 | 0.4 | 0.4 | 0.9 |
No | α | β | ρ | ζ | q0 | Result |
---|---|---|---|---|---|---|
1 | 1 | 2 | 0.1 | 0.1 | 0.6 | 22,598.7 |
2 | 1 | 3 | 0.2 | 0.2 | 0.7 | 22,422.6 |
3 | 1 | 4 | 0.3 | 0.3 | 0.8 | 22,363.5 |
4 | 1 | 5 | 0.4 | 0.4 | 0.9 | 22,353.7 |
5 | 2 | 2 | 0.2 | 0.3 | 0.9 | 22,433.9 |
6 | 2 | 3 | 0.1 | 0.4 | 0.8 | 22,450.8 |
7 | 2 | 4 | 0.4 | 0.1 | 0.7 | 22,446.4 |
8 | 2 | 5 | 0.3 | 0.2 | 0.6 | 22,462.0 |
9 | 3 | 2 | 0.3 | 0.4 | 0.7 | 23,023.6 |
10 | 3 | 3 | 0.4 | 0.3 | 0.6 | 22,568.6 |
11 | 3 | 4 | 0.1 | 0.2 | 0.9 | 22,430.9 |
12 | 3 | 5 | 0.2 | 0.1 | 0.8 | 22,625.7 |
13 | 4 | 2 | 0.4 | 0.2 | 0.8 | 22,654.4 |
14 | 4 | 3 | 0.3 | 0.1 | 0.9 | 24,702.8 |
15 | 4 | 4 | 0.2 | 0.4 | 0.6 | 22,503.3 |
16 | 4 | 5 | 0.1 | 0.3 | 0.7 | 22,384.5 |
α | β | ρ | ζ | q0 | |
---|---|---|---|---|---|
\({H}_{1}\) | 89,738.6 | 90,710.6 | 89,864.9 | 92,373.6 | 90,132.5 |
\({H}_{2}\) | 89,793.1 | 92,144.8 | 89,985.7 | 89,969.8 | 90,277.1 |
\({H}_{3}\) | 90,648.7 | 89,744.1 | 92,551.8 | 89,750.6 | 90,094.5 |
H4 | 92,244.9 | 89,825.9 | 90,023.0 | 90,331.4 | 91,921.3 |
\({h}_{1}\) | 22,434.7 | 22,677.6 | 22,466.2 | 23,093.4 | 22,533.1 |
\({h}_{2}\) | 22,448.3 | 23,036.2 | 22,496.4 | 22,492.5 | 22,569.3 |
\({h}_{3}\) | 22,662.2 | 22,436.0 | 23,138.0 | 22,437.6 | 22,523.6 |
\({h}_{4}\) | 23,061.2 | 22,456.5 | 22,505.7 | 22,582.8 | 22,980.3 |
Max | 23,061.2 | 23,036.2 | 23,138.0 | 23,093.4 | 22,980.3 |
Min | 22,434.7 | 22,436.0 | 22,466.2 | 22,437.6 | 22,523.6 |
Range | 626.5 | 600.2 | 678.1 | 655.8 | 456.7 |
Scheme | Level 1 | Level 3 | Level 1 | Level 3 | Level 3 |
α | β | ρ | |
---|---|---|---|
Level 1 | 1 | 2 | 0.1 |
Level 2 | 2 | 3 | 0.2 |
Level 3 | 3 | 4 | 0.3 |
Level 4 | 4 | 5 | 0.4 |
No | α | β | ρ | Result |
---|---|---|---|---|
1 | 1 | 2 | 0.1 | 22,942.8 |
2 | 1 | 3 | 0.2 | 22,416.8 |
3 | 1 | 4 | 0.3 | 22,384.1 |
4 | 1 | 5 | 0.4 | 22,310.7 |
5 | 2 | 2 | 0.2 | 23,107.7 |
6 | 2 | 3 | 0.1 | 22,461.1 |
7 | 2 | 4 | 0.4 | 22,585.6 |
8 | 2 | 5 | 0.3 | 22,429.4 |
9 | 3 | 2 | 0.3 | 24,285.2 |
10 | 3 | 3 | 0.4 | 23,135.1 |
11 | 3 | 4 | 0.1 | 22,767.8 |
12 | 3 | 5 | 0.2 | 22,670.9 |
13 | 4 | 2 | 0.4 | 24,852.2 |
14 | 4 | 3 | 0.3 | 23,500.7 |
15 | 4 | 4 | 0.2 | 23,147.3 |
16 | 4 | 5 | 0.1 | 22,864.5 |
α | β | ρ | |
---|---|---|---|
\({H}_{1}\) | 90,054.3 | 95,187.8 | 91,036.1 |
\({H}_{2}\) | 90,583.7 | 91,513.7 | 91,342.6 |
\({H}_{3}\) | 92,858.9 | 90,884.7 | 92,599.3 |
\({H}_{4}\) | 94,364.7 | 90,275.3 | 92,883.5 |
\({h}_{1}\) | 22,513.6 | 23,797.0 | 22,759.0 |
\({h}_{2}\) | 22,645.9 | 22,878.4 | 22,835.7 |
\({h}_{3}\) | 23,214.7 | 22,721.2 | 23,149.8 |
\({h}_{4}\) | 23,591.2 | 22,568.8 | 23,220.9 |
Max | 23,591.2 | 23,797.0 | 23,220.9 |
Min | 22,513.6 | 22,568.8 | 22,759.0 |
Range | 1077.6 | 1228.2 | 461.9 |
Scheme | Level 1 | Level 4 | Level 1 |
Parameter | ACS | MMAS |
---|---|---|
α | 1 | 1 |
β | 4 | 5 |
ρ | 0.1 | 0.1 |
ζ | 0.3 | – |
q0 | 0.8 | – |
M | 20 | 20 |
Iteration | 2000 | 2000 |
E(P)* | 4 | – |
Con* | – | 0.8 |
Strategy analysis
Instance | Algorithm | Best | Worst | Average |
---|---|---|---|---|
kroA100 | LOST-1 | 21,282 | 21,600 | 21,347.40 |
LOST-2 | 21,282 | 21,577 | 21,328.47 | |
LOST-3 | 21,282 | 21,373 | 21,307.60 | |
DCM-ACO | 21,282 | 21,373 | 21,294.13 | |
lin318 | LOST-1 | 42,276 | 43,407 | 42,890.20 |
LOST-2 | 42,454 | 43,423 | 42,885.75 | |
LOST-3 | 42,372 | 43,338 | 42,776.35 | |
DCM-ACO | 42,179 | 43,002 | 42,651.00 |
Comparison with traditional ACO algorithm
No | TSP | Optimal | Algorithm | Best | Worst | Average | Error (%) | Std (%) |
---|---|---|---|---|---|---|---|---|
ACS | 426 | 435 | 428.6 | 0.00 | 2.18 | |||
1 | eil51 | 426 | MMAS | 426 | 432 | 428.1 | 0.00 | 2.04 |
DCM-ACO | 426 | 427 | 426.5 | 0.00 | 0.51 | |||
ACS | 538 | 551 | 544.9 | 0.00 | 4.16 | |||
2 | eil76 | 538 | MMAS | 538 | 552 | 542.2 | 0.00 | 4.71 |
DCM-ACO | 538 | 541 | 538.7 | 0.00 | 1.06 | |||
ACS | 21,282 | 21,835 | 21,450.6 | 0.00 | 157.83 | |||
3 | kroA100 | 21,282 | MMAS | 21,282 | 21,945 | 21,396.3 | 0.00 | 166.59 |
DCM-ACO | 21,282 | 21,373 | 21,290.3 | 0.00 | 20.30 | |||
ACS | 22,270 | 22,496 | 22,366.4 | 0.58 | 53.72 | |||
4 | kroB100 | 22,141 | MMAS | 22,220 | 22,580 | 22,320.3 | 0.36 | 90.47 |
DCM-ACO | 22,141 | 22,275 | 22,167.9 | 0.00 | 38.13 | |||
ACS | 6162 | 6348 | 6245.0 | 0.85 | 57.94 | |||
5 | ch130 | 6110 | MMAS | 6121 | 6259 | 6188.4 | 0.18 | 37.35 |
DCM-ACO | 6110 | 6218 | 6151.4 | 0.00 | 20.65 | |||
ACS | 6548 | 6778 | 6600.5 | 0.31 | 54.02 | |||
6 | ch150 | 6528 | MMAS | 6528 | 6641 | 6578.3 | 0.00 | 29.55 |
DCM-ACO | 6528 | 6563 | 6546.4 | 0.00 | 11.86 | |||
ACS | 26,244 | 27,269 | 26,699.1 | 0.43 | 292.44 | |||
7 | kroB150 | 26,130 | MMAS | 26,196 | 27,034 | 29,443.9 | 0.25 | 214.31 |
DCM-ACO | 26,130 | 26,463 | 26,294.5 | 0.00 | 75.35 | |||
ACS | 29,536 | 30,290 | 29,827.9 | 0.57 | 233.57 | |||
8 | kroA200 | 29,368 | MMAS | 29,460 | 30,184 | 29,639.0 | 0.31 | 213.40 |
DCM-ACO | 29,368 | 29,608 | 29,494.6 | 0.00 | 59.89 | |||
ACS | 29,737 | 30,701 | 30,343.6 | 1.01 | 272.47 | |||
9 | kroB200 | 29,437 | MMAS | 29,721 | 30,957 | 30,195.9 | 0.96 | 405.92 |
DCM-ACO | 29,437 | 30,081 | 29,653.2 | 0.00 | 136.01 | |||
ACS | 49,198 | 51,702 | 49,734.4 | 0.13 | 671.45 | |||
10 | pr264 | 49,135 | MMAS | 49,135 | 51,927 | 49,715.0 | 0.00 | 786.85 |
DCM-ACO | 49,135 | 49,203 | 49,163.4 | 0.00 | 25.01 | |||
ACS | 2589 | 2712 | 2636.6 | 0.38 | 35.77 | |||
11 | a280 | 2579 | MMAS | 2587 | 2683 | 2624.8 | 0.31 | 27.06 |
DCM-ACO | 2579 | 2608 | 2596.2 | 0.00 | 8.68 | |||
ACS | 42,790 | 43,586 | 43,277.0 | 1.81 | 221.68 | |||
12 | lin318 | 42,029 | MMAS | 43,046 | 44,879 | 43,614.5 | 2.42 | 447.74 |
DCM-ACO | 42,179 | 42,915 | 42,638.9 | 0.35 | 177.35 | |||
ACS | 12,031 | 12,404 | 12,185.9 | 1.43 | 100.58 | |||
13 | fl417 | 11,861 | MMAS | 12,006 | 12,363 | 12,174.1 | 1.22 | 94.02 |
DCM-ACO | 11,901 | 12,042 | 11,955.6 | 0.33 | 29.20 | |||
107,217 | ACS | 108,309 | 116,846 | 110,905.9 | 1.02 | 2402.69 | ||
14 | pr439 | MMAS | 107,929 | 114,244 | 110,826.9 | 0.66 | 1682.36 | |
DCM-ACO | 107,400 | 109,158 | 108,408.8 | 0.17 | 475.95 | |||
ACS | 35,032 | 37,318 | 35,476.7 | 1.12 | 535.75 | |||
15 | p654 | 34,643 | MMAS | 36,257 | 37,923 | 36,996.8 | 4.66 | 518.65 |
DCM-ACO | 34,795 | 35,496 | 34,927.7 | 0.43 | 161.82 | |||
ACS | 279,388 | 293,489 | 285,565.9 | 3.40 | 3496.78 | |||
16 | rl1323 | 270,199 | MMAS | 285,858 | 309,420 | 298,623.8 | 5.80 | 5855.98 |
DCM-ACO | 273,707 | 279,855 | 276,716.7 | 1.29 | 1663.25 | |||
ACS | 20,760 | 23,121 | 21,503.8 | 3.15 | 566.40 | |||
17 | fl1400 | 20,127 | MMAS | 22,204 | 23,718 | 22,963.6 | 10.32 | 440.49 |
DCM-ACO | 20,368 | 20,904 | 20,629.8 | 1.19 | 143.72 | |||
ACS | 83,671 | 87,556 | 85,748.2 | 4.00 | 1147.31 | |||
18 | d2103 | 80,450 | MMAS | 85,062 | 89,832 | 87,043.3 | 5.73 | 1462.16 |
DCM-ACO | 81,957 | 84,382 | 82,853.4 | 1.87 | 546.47 |
Comparison with other algorithms
TSP | Optimal | DCM-ACO | SOS-ACO | ||||
---|---|---|---|---|---|---|---|
Best | Average | Std | Best | Average | Std | ||
eil51 | 426 | 426 | 426.5 | 0.55 | 426 | 428.1 | 1.14 |
eil76 | 538 | 538 | 538.6 | 1.11 | 538 | 541.7 | 2.49 |
kroA100 | 21,282 | 21,282 | 21,289.2 | 8.57 | 21,282 | 21,290.1 | 12.56 |
ch150 | 6528 | 6528 | 6546.4 | 11.86 | 6558 | 6571.2 | 10.52 |
kroA200 | 29,368 | 29,368 | 29,494.6 | 59.89 | 29,413 | 29,520.7 | 69.31 |
pr264 | 49,135 | 49,135 | 49,163.4 | 25.01 | 49,135 | 49,250.7 | 107.60 |
lin318 | 42,029 | 42,179 | 42,638.9 | 177.35 | 42,473 | 42,762.7 | 169.69 |
pr439 | 107,217 | 107,400 | 108,408.8 | 475.95 | 107,978 | 108,873.8 | 350.89 |
TSP | Optimal | DCM-ACO | PSO-ACO-3opt | ||||
---|---|---|---|---|---|---|---|
Best | Worst | Average | Best | Worst | Average | ||
eil51 | 426 | 426 | 427 | 426.5 | 426 | 428 | 426.4 |
eil76 | 538 | 538 | 541 | 538.6 | 538 | 539 | 538.3 |
kroA100 | 21,282 | 21,282 | 21,373 | 21,289.2 | 21,301 | 21,554 | 21,445.1 |
ch150 | 6528 | 6528 | 6563 | 6546.4 | 6538 | 6622 | 6563.9 |
kroA200 | 29,368 | 29,368 | 29,595 | 29,494.6 | 29,468 | 29,957 | 29,646.0 |
fl417 | 11,861 | 11,901 | 12,042 | 11,955.5 | 11,947 | 12,003 | 11,980.4 |
pr439 | 107,217 | 107,400 | 109,158 | 108,408.8 | 108,530 | 109,341 | 108,873.8 |
p654 | 107,217 | 34,795 | 34,927.7 | 34,927.7 | 35,052 | 35,145 | 35,098.2 |
Algorithm | eil51 | eil76 | kroA100 | ch150 | kroA200 | pr264 | |
---|---|---|---|---|---|---|---|
Proposed | Best | 426 | 538 | 21,282 | 6528 | 29,368 | 49,135 |
Algorithm | Error% | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
LDTACO | Best | 426 | 538 | 21,282 | 6528 | 29,380 | – |
(2021) | Error% | 0.00 | 0.00 | 0.00 | 0.00 | 0.04 | – |
DBAL | Best | 426 | 538 | 21,282 | – | 29,368 | 49,135 |
(2021) | Error% | 0.00 | 0.00 | 0.00 | – | 0.00 | 0.00 |
PPACO | Best | 426 | 538 | 21,282 | 6528 | 29,368 | 49,135 |
(2021) | Error% | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
HAACO | Best | 426 | 538 | 21,282 | 6566 | 29,483 | – |
(2020) | Error% | 0.00 | 0.00 | 0.00 | 0.58 | 0.39 | – |
DSMO | Best | 428 | 558 | 21,298 | – | 30,481 | – |
(2020) | Error% | 0.67 | 3.72 | 0.07 | – | 3.79 | – |
NACO | Best | 426 | – | 21,282 | 6528 | 29,368 | 49,144 |
(2020) | Error% | 0.00 | – | 0.00 | 0.00 | 0.00 | 0.02 |
PACO-3opt | Best | 426 | 538 | 21,282 | 6570 | 29,368 | – |
(2018) | Error% | 0.00 | 0.00 | 0.00 | 0.64 | 0.00 | – |
DSOS | Best | 426 | 542 | 21,282 | 6542 | 29,477 | 50,454 |
(2017) | Error% | 0.00 | 0.74 | 0.00 | 0.21 | 0.37 | 2.68 |
HMMA | Best | 438 | 549 | 21,371 | 6654 | 29,999 | 50,554 |
(2015) | Error% | 0.00 | 0.00 | 0.09 | 1.89 | 0.34 | 2.89 |
Algorithm | lin318 | fl417 | pr439 | p654 | rl1323 | fl1400 | |
---|---|---|---|---|---|---|---|
Proposed | Best | 42,179 | 11,901 | 107,400 | 34,795 | 273,707 | 20,368 |
Algorithm | Error% | 0.35 | 0.34 | 0.17 | 0.43 | 1.29 | 1.19 |
DBAL | Best | 42,072 | 11,861 | 107,603 | – | – | – |
(2021) | Error% | 0.10 | 0.00 | 0.36 | – | – | – |
PACO-3opt | Best | – | 11,972 | 108,482 | 35,027 | – | – |
(2018) | Error% | – | 0.94 | 1.12 | 1.24 | – | – |
IVNS | Best | 43,924 | 12,180 | 11,175 | – | 295,607 | 21,040 |
(2018) | Error% | 4.51 | 2.69 | 4.22 | – | 9.45 | 4.53 |
HMMA | Best | 45,443 | 45,349 | 12,543 | 114,095 | – | 23,099 |
(2015) | Error% | 8.12 | 7.90 | 5.07 | 6.41 | – | 14.77 |
Reference [42] | Best | 42,487 | – | – | – | 277,642 | 20,593 |
(2011) | Error% | 1.09 | – | – | – | 2.75 | 2.32 |
Statistical test analysis
TSP | P-value | sig | TSP | P-value | sig |
---|---|---|---|---|---|
eli51 | 9.90E−06 | YES | eil76 | 3.78E−08 | YES |
kroA100 | 3.19E−06 | YES | kroB100 | 6.16E−06 | YES |
ch130 | 3.61E−07 | YES | ch150 | 5.76E−07 | YES |
kroB150 | 9.70E−06 | YES | kroA200 | 2.91E−07 | YES |
kroB200 | 1.92E−07 | YES | pr264 | 7.46E−08 | YES |
a280 | 6.95E−05 | YES | lin318 | 1.32E−07 | YES |
fl417 | 9.10E−08 | YES | pr439 | 2.03E−05 | YES |
p654 | 1.12E−06 | YES | rl1323 | 1.20E−06 | YES |
fl1400 | 1.43E−07 | YES | d2103 | 9.17E−08 | YES |
TSP | P-value | sig | TSP | P-value | sig |
---|---|---|---|---|---|
eli51 | 6.30E−03 | YES | eil76 | 3.85E−08 | YES |
kroA100 | 1.02E−03 | YES | kroB100 | 5.85E−07 | YES |
ch130 | 1.14 E−03 | YES | ch150 | 4.63 E−04 | YES |
kroB150 | 1.54 E−02 | YES | kroA200 | 2.03 E−02 | YES |
kroB200 | 6.01E−07 | YES | pr264 | 1.70E−05 | YES |
a280 | 3.53E−04 | YES | lin318 | 1.23E−07 | YES |
fl417 | 7.84E−08 | YES | pr439 | 4.53E−06 | YES |
p654 | 6.79E−08 | YES | rl1323 | 6.80E−08 | YES |
fl1400 | 6.75E−08 | YES | d2103 | 6.80E−08 | YES |
Sample1–Sample2 | Test statistic | Std. error | Std. test statistic | sig | Adj.Sig |
---|---|---|---|---|---|
DCM-ACO-NACO | − 1.47 | 0.47 | − 3.11 | 0.002 | 0.011 |
DCM-ACO-LDTACO | − 1.67 | 0.47 | − 3.54 | 0.000 | 0.002 |
DCM-ACO-PPACO | − 1.80 | 0.47 | − 3.82 | 0.000 | 0.001 |