The traveling salesman problem

The traveling salesman problem, or TSP for short, is this: given a finite number of ``cities'' along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. (Here, we consider just the symmetric TSP, where traveling from city X to city Y costs the same as traveling from Y to X; the ``way of visiting all the cities'' is simply the order in which the cities are visited.) To put it differently, the data consist of integer weights assigned to the edges of a finite complete graph; the objective is to find a hamiltonian cycle (that is, a cycle passing through all the vertices) of the minimum total weight. In this context, hamiltonian cycles are commonly called tours.

TSPLIB is Gerhard Reinelt's library of 110 instances of the traveling salesman problem. Some of these instances arise from the task of drilling holes in printed circuit boards and others have been constructed artificially. (A popular way of constructing a TSP instance is to choose a set of actual cities and to define the cost of travel from X to Y as the distance between X and Y.) None of them (with a single exception) is contrived to be hard and none of them is contrived to be easy; some of them have been solved (a few of these are shown here) and others have not.

David Applegate, Robert Bixby, William Cook, and I have written a computer code that solved all but three of the previously unsolved instances from the TSPLIB. One of these is the instance with 225 cities,

constructed by Stefan Tschöke and contrived to be hard for its size; the others include and their sizes range from 1,000 to 15,112 cities. (The three TSPLIB instances not solved by Concorde have 18,512 cities, 33,810 cities, and 85,900 cities; these were solved by William Cook, Daniel Espinoza, and Marcos Goycoolea, starting with Concorde and adding various routines for Adam Letchford's domino-parity constraints; in solving the 85,900-city instance, they also relied on a tour found previously by Keld Helsgaun, which they proved to be optimal.) A few comments on our work are collected in an interview intended for a general audience and published in 1996. A twelve-page survey intended for a mathematical audience was published in 1998 and awarded the in 2000. Our "local cuts" are described in there is also a set of eighteen transparencies from my talk on the same subject. Much more can be found on
Bill Cook's TSP page.

Our book

was published by Princeton University Press in February 2007 and awarded the

at the INFORMS Awards Ceremony in November 2007. Here is the citation.

Other sites related to the TSP include:

               
Back to Vašek Chvátal's home page