Authors: David Applegate, Robert Bixby, Vasek Chvatal, William Cook
ABSTRACT
TSPLIB is Gerhard Reinelt's library of some hundred instances of the
traveling salesman problem. Some of these instances arise from
drilling holes in printed circuit boards; others arise from X-ray
crystallography; yet others have been constructed artificially. None
of them (with a single exception) is contrived to be hard and none of
them is contrived to be easy; their sizes range from 17 to 85,900
cities; some of them have been solved and others have not.
We have solved twenty previously unsolved problems from the TSPLIB.
One of them is the problem with 225 cities that was contrived to be
hard; the sizes of the remaining nineteen range from 1,000 to 7,397
cities.
Like all the successful computer programs for solving the TSP, our
computer program follows the scheme designed by George Dantzig, Ray
Fulkerson, and Selmer Johnson in the early nineteen-fifties. The
purpose of this preliminary report is to describe *some* of our
innovations in implementing the Dantzig-Fulkerson-Johnson scheme; we
are planning to write up a more comprehensive account of our work
soon.
DIMACS Home Page