TSPLIB
TSPLIB is a library of sample instances for the TSP (and related problems) from various sources and of various types.
Frequently asked questions
We have a small collection of answers to frequently asked questions (FAQ). Please read this and the description of the library before reporting problems with TSPLIB.
Symmetric traveling salesman problem (TSP)
Given a set of n nodes and distances for each pair of nodes, find a roundtrip of minimal total length visiting each node exactly once. The distance from node i to node j is the same as from node j to node i. - -> TSP data
Best known solutions for symmetric TSPs
Hamiltonian cycle problem (HCP)
Given a graph, test if the graph contains a Hamiltonian cycle or not. - -> HCP data
Asymmetric traveling salesman problem (ATSP)
Given a set of n nodes and distances for each pair of nodes, find a roundtrip of minimal total length visiting each node exactly once. In this case, the distance from node i to node j and the distance from node j to node i may be different. - -> ATSP data
Best known solutions for asymmetric TSPs
Sequential ordering problem (SOP)
This problem is an asymmetric traveling salesman problem with additional constraints. Given a set of n nodes and distances for each pair of nodes, find a Hamiltonian path from node 1 to node n of minimal length which takes given precedence constraints into account. Each precedence constraint requires that some node i has to be visited before some other node j. - -> SOP data
Best known solutions for sequential ordering problems
Capacitated vehicle routing problem (CVRP)
We are given n-1 nodes, one depot and distances from the nodes to the depot, as well as between nodes. All nodes have demands which can be satisfied by the depot. For delivery to the nodes, trucks with identical capacities are available. The problem is to find tours for the trucks of minimal total length that satisfy the node demands without violating truck capacity constraint. The number of trucks is not specified. Each tour visits a subset of the nodes and starts and terminates at the depot. (Remark: In some data files a collection of alternate depots is given. A CVRP is then given by selecting one of these depots.) - -> CVRP data
Remark
Except for the Hamiltonian cycle problems, all problems instances are defined on a complete graph and, at present, all distances are integer numbers. There is a possibility to require that certain edges appear in the solution of a problem.
Description
A complete description of the library is given here (Postscript-, GZip- and Zip-Version)
Implementation challenge
The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) is organizing an implementation challenge for TSP heuristics. Details can be found at http://www.research.att.com/~dsj/chtsp/
Links
Pablo Moscato is compiling a bibliography of TSP related papers and software. Links to further interesting data bases can be found at Michael Trick's homepage http://mat.gsia.cmu.edu.
Address
Last change: December 6, 2001