TSPLIB: A Library of Standard TSP Instances

A classic resources for anyone interested in the Travelling Salesman Problem is TSPLIB. I thought I would capture a few words about TSPLIB, and how I intend to use it.

TSPLIB is comprised of more than 100 instances of the TSP collected by Professor Gerhard Reinelt in the mid 1990's. Reinelt is currently associated with the University of Heidelberg, and as such, the TSPLIB is housed on the website of the Discrete Optimization Research Group at that University (see an old mirror).

The library is composed of a set of problem instances for the TSP and related problems. I am specifically interested in the Symmetric TSP instances, although the other problems in the library include: the Hamiltonian cycle problem (HCP), the Asymmetric traveling salesman problem (ATSP), the Sequential ordering problem (SOP), and the Capacitated vehicle routing problem (CVRP).

The site provides documentation (postscript format) that describes the standardised file format for the problem instances, as well as a FAQ that relates to common questions about the library.

I had used instances of the TSPLIB before in my OAT library, although I was unaware of the number of symmetrical instances in the library, and the array of "types" for this class of problem. Specifically, the file format describes a number of distance measure used to assess tours in TSP instances (that I refer to as types). As such, symmetrical instances may be one of the following types: EUC_2D (Euclidean distance rounded to an integer), GEO (Geographical for assessing longitude and latitude coordinates), ATT (Euclidean distance with scaling and rounding), MATRIX (pre-defined distances in a matrix), and CEIL_2D (Euclidean distance rounded up).

The majority of the TSP instances are of the EUC_2D type, many of which have known solutions. Considering this, I believe I will include all types except MATRIX in the the human TSP solver application, and provide optimal solutions for visualisation on the problems that have been solved. Importantly, William Cook's additional problem instances are also available in TSPLIB format, meaning that I can use a generic importing and representation approaches in the application.

One thing I may need to consider in the future is the license under which these instances are provided. I suspect they have been released under public domain license, although this will become a concern if I chose to monetise the application.