The traveling salesman problem (TSP) asks for the cheapest possible tour through a given collection of cities. Solving the problem means to not only find the best tour but also to prove that no cheaper tour is possible. Early work on the TSP in the 1950s focused exclusively on the this full solution of the problem.
Starting in the mid-1960s researchers began to study the relaxed version of the TSP where we ask only for a tour of low cost. This task is much easier, but performing it well is an important ingredient in a full (exact) solution method, as well as being an interesting problem in its own right. Indeed, tour finding is a very popular topic, having a large and growing literature devoted to its various aspects. And like the TSP itself, tour finding has led researchers to discover general purpose search techniques that have found application in many domains.
The Sweden TSP was attacked by a number of groups with some of the top tour-finding methods that have been developed to date. Information on the improvements in the best known tour length can be found in the Sweden Computation Log; the results are summarized in the following table.
 |
|
|
|
| 855618 | September 4, 2001 | Tour Merging | Cook and Seymour |
| 855612 | September 20, 2001 | LKH | Helsgaun |
| 855610 | September 30, 2001 | LKH Merge | Helsgaun |
| 855602 | March 16, 2003 | Hybrid Genetic | Hung Dinh Nguyen |
| 855597 | March 18, 2003 | LKH | Helsgaun |
The final improvement in the tour length was made by Keld Helsgaun using a version of his LKH code. This 855,597 value was proved to be optimal by the Concorde TSP code.
The Concorde solver can accept as an input parameter the value of the best known tour for a TSP instance if one is available. As a full (exact) TSP solver, Concorde is designed to find optimal solutions regardless of the quality of the estimate, but knowledge of a good tour allows for better tuning of parameters that are set in the computer code.
In the case of the Sweden TSP, the results of the tour-finding attacks guided our choices in approaching the full solution of the problem. Most importantly, the final stages that improved the lower bound from 855,595 up to the optimal value 855,597 required approximately 8 years of computation time (running in parallel on a network of Linux workstations) and without knowledge of the 855,597 tour we would not have make the decision to carry out this final computation.