.... Solving TSPs
....


World TSP

National TSPs

TSP Home Page

Earth


TSP Links

TSPLIB

Home page

Status of National TSP Instances

We present below a summary of the solution status of the 25 National TSP instances. In the table, we list the length of the best reported solution for each of the instances, and also the best reported lower bounds, that is, values for which it has been verified that there is no tour for the instance of length less than the specified number. The "Gap" column gives the % difference between the best tour and the best bound.

Name Gap Bound Tour Source of Tour
ar9152 Optimal 837,479 837,479 Hung Dinh Nguyen
bm33708 0.031% 959,011 959,289 Yuichi Nagata
ca4663 Optimal 1,290,319 1,290,319 Concorde
ch71009 0.024% 4,565,452 4,566,506 Yuichi Nagata
dj38 Optimal 6,656 6,656 Concorde
eg7146 Optimal 172,386 172,386 Keld Helsgaun
fi10639 Optimal 520,527 520,527 LKH + tmerge
gr9882 Optimal 300,899 300,899 LKH + tmerge
ho14473 Optimal 177,092 177,092 Yuichi Nagata
ei8246 Optimal 206,171 206,171 LKH
it16862 Optimal 557,315 557,315 LKH + tmerge
ja9847 Optimal 491,924 491,924 Keld Helsgaun
kz9976 Optimal 1,061,881 1,061,881 Keld Helsgaun
lu980 Optimal 11,340 11,340 Concorde
mo14185 0.031% 427,246 427,377 Keld Helsgaun
nu3496 Optimal 96,132 96,132 Concorde
mu1979 Optimal 86,891 86,891 Concorde
pm8079 Optimal 114,855 114,855 Yuichi Nagata
qa194 Optimal 9,352 9.352 Concorde
rw1621 Optimal 26,051 26,051 Concorde
sw24978 Optimal 855,597 855,597 Keld Helsgaun
tz6117 Optimal 394,718 394,718 LKH + tmerge
uy734 Optimal 79,114 79,114 Concorde
vm22775 Optimal 569,288 569,288 Keld Helsgaun
wi29 Optimal 27,603 27,603 Concorde
ym7663 Optimal 238,314 238,314 LKH + tmerge
zi929 Optimal 95,345 95,345 Concorde


Notes

1. All lower bounds were found by Concorde, our linear-programming based TSP solver.

2. LKH is Keld Helsgaun's powerful implementation of the Lin-Kernighan heuristic.

Back to TSP home.

Last Updated:  April 28, 2009.
Contact:  bico@uwaterloo.ca