DIMACS TSP Challenge Results
Current best tours found by LKH

 

Tour quality for E-instances

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

 

Tour quality for C-instances

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

 

Last updated: October 6, 2014

[home]