University of Kaiserslautern » Department of Computer Science » DAG

Home

People

Peter Merz

Thomas Fischer

Steffen Wolf

Mathias Dalheimer

Matthias Priebe

Research

Publications

Contact

Links

University Home

Department Home

Disco Group

Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) is a well-known NP-hard problem.

Instances

Instances for the TSP problem are usually stored in the TSPLIB format. Using this format allows accessing a large variety of existing instances. The most prominent collections of TSP instances are:

• The original TSPLIB library including a set of symmetric instances and optimal tours (if available). Provided by Gerhard Reinelt.
• National Traveling Salesman Problems derived from maps of real countries. Provided by William Cook.
• The VLSI Data Sets contain instances based on research in VLSI design. Instance data provided by Andre Rohe.
• Random instances as used for the DIMACS/TSP Challenge can be generated by the provided C code.

Tours

Whilst there are many TSP instance available for testing and you will find the length values for optimal tours of these instances, too, it is harder to find the tours itself. Here, we provide a collection of various tours for well-known TSP instances which can be used for your own TSP research.

Tour Data

Name	Lower Bound	Best Known (% above Lower Bound)	Additional Information
berlin52	unknown	7542 (optimal)	[EPS] [SVG] [PNG]
brd14051	unknown	469385 (optimal)	[EPS] [SVG] [PNG]
d15112	unknown	1573084 (optimal)	[EPS] [SVG] [PNG]
d18512	645230	645238 (optimal)	[EPS] [SVG] [PNG]
pcb442	unknown	50778 (optimal)	[EPS] [SVG] [PNG]
pla7397	unknown	23260728 (optimal)	[EPS] [SVG] [PNG]
pla33810	unknown	66048945 (solved to optimality by Cook, Espinoza, and Goycoolea)	[EPS] [SVG] [PNG]
pla85900	142348737	142366091 (0.0122%), 142382641 (0.0238%)	[EPS] [SVG] [PNG]
pr2392	unknown	378032 (optimal)	[EPS] [SVG] [PNG]
See also: TSPLIB
Name	Lower Bound	Best Known (% above Lower Bound)	Additional Information
ch71009	4565452	4566556 (0.0242%), 4566563 (0.0243%)	[EPS] [SVG] [PNG]
fi10639	520383	520527 (0.0277%)	[EPS] [SVG] [PNG]
gr9882	unknown	300899 (optimal)	[EPS] [SVG] [PNG]
it16862	unknown	557315 (optimal)	[EPS] [SVG] [PNG]
ja9847	unknown	491924 (optimal)	[EPS] [SVG] [PNG]
kz9976	1061387	1061881 (0.0465%), 1061882 (0.0467%)	[EPS] [SVG] [PNG]
mo14185	427246	427377 (0.0307%)	[EPS] [SVG] [PNG]
sw24978	unknown	855597 (optimal)	[EPS] [SVG] [PNG]
vm22775	569115	569288 (0.0304%)	[EPS] [SVG] [PNG]
See also: National Traveling Salesman Problems
Name	Lower Bound	Best Known (% above Lower Bound)	Additional Information
fnc19402	unknown	59288 (unknown)	[EPS] [SVG] [PNG]
ido21215	63501	63519 (0.0284%)	[EPS] [SVG] [PNG]
lsb22777	unknown	60977 (unknown)	[EPS] [SVG] [PNG]
pjh17845	unknown	48094 (unknown)	[EPS] [SVG] [PNG]
xia16928	unknown	52850 (unknown)	[EPS] [SVG] [PNG]
xmc10150	unknown	28387 (unknown)	[EPS] [SVG] [PNG]
xrb14233	unknown	45464 (unknown)	[EPS] [SVG] [PNG]
xvb13584	unknown	37084 (unknown)	[EPS] [SVG] [PNG]
See also: VLSI Data Sets
Name	Lower Bound	Best Known (% above Lower Bound)	Additional Information
E10k.0	71362276	72212830 (1.1919%)	[EPS] [SVG] [PNG]
E10k.1	71565485		[EPS] [SVG] [PNG]
E10k.2	71351795		[EPS] [SVG] [PNG]
E31k.0	126474847		[EPS] [SVG] [PNG]
E31k.1	126647285		[EPS] [SVG] [PNG]
E100k.0	224330692		[EPS] [SVG] [PNG]
E100k.1	224241789		[EPS] [SVG] [PNG]
See also: TSP Challenge

© 2005–2009 Peter Merz - - Contact