Ruprecht-Karls-Universität Heidelberg





TSPLIB

TSPLIB is a library of sample instances for the TSP (and related problems) from various sources and of various types.

Note that it is not intended to add further problems instances (1.1.2013)

Please read the FAQ and the Documentation before reporting problems with TSPLIB!

There you will find answers to all the questions that have been asked so far.
Please note in particular that, except for the Hamiltonian cycle problems, all problems instances are defined on a complete graph and all distances are defined to be integer numbers.

NEW: Hamiltonian Cycle Challenge (see below)

TSPLIB also available in XML format

Thanks to Ulrich Pferschy and Rostislav Stanek (University of Graz) the original TSPLIB data files are now also available in XML format.
Description
-> Examples for using the XML parser
-> TSPLIB in XML format

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
The Flinders Hamiltonian Cycle Project has launched a challenge with 1001 Hamiltonian cycle problems.
-> FHCP challenge

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

Most recent optimum solutions and best bounds have been found by L. Gouveia and M. Ruthmair. The respective report is available as GR2015.pdf

Some further optimum solutions and comments by A.A. Cire and W.-J. van Hoeve can be found in the paper Multivalued Decision Diagrams for Sequencing 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

Description

A complete description of the library is given here (Postscript-, GZip- and Zip-Version)

Further variants

The "Close-Enough Traveling Salesman Problem" was introduced by William Mennell. Benchmark data can be found at www.minlp.org.


The "TSP with Neighborhoods" is another generalization. Test instances can be found at cse.cs.ovgu.de


The "Orienteering Problem (OP)" was first introduced by T. Tsiligirides in 1984. Benchmark data can be found at github.com.


Remarks

A very nice TSP page (with history, further data sets and the best TSP code CONCORDE) is maintained by Bill Cook. The corresponding book describing the state-of-the-art of TSP computation is

Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem - A Computational Study, Princeton Series in Applied Mathematics, 2006


The Center for Discrete Mathematics and Theoretical Computer Science  (DIMACS) had organized an implementation challenge for TSP heuristics in 2002. Details and updates can be still found at  http://www.research.att.com/~dsj/chtsp/


Links to further interesting data bases can be found at Michael Trick's homepage http://mat.gsia.cmu.edu.


Address

    Gerhard Reinelt
    Universität Heidelberg
    Institut für Informatik
    Im Neuenheimer Feld 368
    D - 69120 Heidelberg
    Germany
    tel: ++49/6221/54-5749
    fax: ++49/6221/54-5750
    e-mail: Gerhard.Reinelt{at}informatik.uni-heidelberg.de
optWay
Links