DIMACS TSP Challenge Results
Current best tours found by LKH
Instance |
n |
Current best tour |
HK lower bound |
HK gap (%) |
E10k.0 |
10,000 |
71,865,826 |
71,362,276 |
0.706 |
E10k.1 |
10,000 |
72,031,630 |
71,565,485 |
0.651 |
E10k.2 |
10,000 |
71,822,483 |
71,351,795 |
0.660 |
E31k.0 |
31,623 |
127,282,138 |
126,474,847 |
0.638 |
E31k.1 |
31,623 |
127,452,384 |
126,647,285 |
0.636 |
E100k.0 |
100,000 |
225,784,127 |
224,330,692 |
0.648 |
E100k.1 |
100,000 |
225,654,639 |
224,241,789 |
0.630 |
E316k.0 |
316,228 |
401,301,206 |
398,582,616 |
0.682 |
E1M.0 |
1,000,000 |
713,187,688 |
708,703,513 |
0.633 |
E3M.0 |
3,162,278 |
1,267,318,198 |
1,260,000,000 |
0.581 |
E10M.0 |
10,000,000 |
2,253,088,000 |
2,240,000,000 |
0.584 |
Instance |
n |
Current best tour |
HK lower bound |
HK gap (%) |
C10k.0 |
10,000 |
33,001,034 |
32,782,155 |
0.668 |
C10k.1 |
10,000 |
33,186,248 |
32,958,946 |
0.690 |
C10k.2 |
10,000 |
33,155,424 |
32,926,889 |
0.694 |
C31k.0 |
31,623 |
59,545,390 |
59,169,193 |
0.636 |
C31k.1 |
31,623 |
59,293,266 |
58,840,096 |
0.770 |
C100k.0 |
100,000 |
104,617,752 |
103,916,254 |
0.675 |
C100k.1 |
100,000 |
105,390,777 |
104,663,040 |
0.695 |
C316k.0 |
316,228 |
186,870,839 |
185,576,667 |
0.697 |
Found by LKH by improving tours found by Zhang-Hua Fu et al.:
A Hierarchical Destroy and Repair Approach for Solving
Very Large-Scale Travelling Salesman Problem,
Preprint, August 9, 2023.
Instance |
n |
Current best tour |
HK lower bound |
HK gap (%) |
E3M.0 |
3,162,278 |
1,267,295,473 |
1,260,000,000 |
0.579 |
E10M.0 |
10,000,000 |
2,253,040,346 |
2,240,000,000 |
0.582 |
Last updated: August 25, 2023
[home]