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	Optimal	427,377	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.