Traveling-Salesman Problem
supported by the DFG:
Oct 2004 - Sep 2006 and Oct 2007 - Feb 2010
Overview
The Traveling Salesman Problem (TSP)
The Traveling Salesman Problem (TSP) is one of the most famous problem of combinatorial optimization. Given a weighted complete graph, the task to perform is finding a cheapest tour which visits every vertex.
Which importance has the TSP?
TSP is a NP-difficult problem which -- because of its easy formulation and high practical relevance -- is used for comparing different methods and algorithms. The most important reference for these comparisons is TSPLIB with instances from 14 up to 85,900 vertices, which are mostly based on real city problems, and VLSI TSP . Although there are less polynomial time algorithms with proven approximation factors, there are many good heuristics. The current leading algorithms for the STSP are the exact branch-and-cut algorithm of Applegate, Bixby, Chvátal, Cook and the Lin-Kernighan heuristic improved by Helsgaun , and for the ATSP the branch-and-bound algorithm of Carpaneto, dell`Amico, Toth and the Contract-or-Patch heuristic of Glover, Gutin, Yeo, and Zverovich.
What are tolerances?
An important starting point for solving a TSP is the question, which edges are in a good tour with high probability and which not. For this question the term of tolerance is a good criterion. For the TSP the tolerance is defined as follows.
Let a constant (not necessarily unique) optimal tour be given.
The upper tolerance of an edge from this optimal tour is defined as the minimum weight this edge must be increased so that this edge is not contained in at least one optimal tour.
The lower tolerance of an edge outside this optimal tour is defined as the minimum weight this edge must be decreased so that this edge is contained in at least one optimal tour.
Analogously, the tolerance is defined for usual relaxations of the TSP, minimum spanning tree for the STSP, assignment problem, relaxed assignment problem for the ATSP.
What was the aim of the project?
The aim of the project was to develop and implement new methods for faster solving the TSP. For this purpose, many tolerance based criteria for the choice of the edges were analyzed and applied in heuristics as well as in branch-and-bound algorithms. In detail, we wanted to show that a tolerance based choice of edges is superior to a usual weight based choice. As the computation of the tolerances of the TSP is at least as difficult as solving the TSP itself, we used tolerances of the polynomial time problems related to the TSP which are mentioned above. For example we expect that edges of a minimum spanning tree of the graph with large upper tolerance (i.e. they are stable in the minimum spanning tree) have a high probability of being contained in a good tour of the graph.
Additionally, we looked for approaches allowing hierarchical computation of tours allowing to attack really large TSP instances, e.g., the World TSP.
How is the project originated?
In September 2003, Prof. Dr. Jop Sibeyn and Prof. Dr. Boris Goldengorin in cooperation with Dr. Holger Blaar applied for the project to the DFG and in March 2004, the project was granted. In January 2007, the project has been prolongated by the DFG for another two years period (till 2009). Dr. Gerold Jäger worked as a research assistant on the project from October 2004 till September 2006 and from October 2007 till August 2009. Since June 2005, Prof. Dr. Paul Molitor is the leader of the project. Prof. Dr. Jop Sibeyn is missed since his hike over the ice sea in Sweden in March 2005.