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,786,982 |
224,330,692 |
0.649 |
E100k.1 |
100,000 |
225,658,329 |
224,241,789 |
0.632 |
E316k.0 |
316,228 |
401,301,933 |
398,582,616 |
0.682 |
E1M.0 |
1,000,000 |
713,188,361 |
708,703,513 |
0.633 |
E3M.0 |
3,162,278 |
1,267,318,288 |
1,260,000,000 |
0.581 |
E10M.0 |
10,000,000 |
2,253,088,223 | 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,627,465 |
103,916,254 |
0.684 |
C100k.1 |
100,000 |
105,390,777 |
104,663,040 |
0.695 |
C316k.0 |
316,228 |
186,880,688 |
185,576,667 |
0.703 |
Last updated: October 25, 2011
[home]