An Analysis of the Hardness of TSP Instances for Two High-performance Algorithms
Thomas Stützle, Holger H. Hoos, Peter Merz · 2005
The task in the Traveling Salesman Problem (TSP) is to find a minimum length closed tourthrough a given set of n cities with known inter-city distances such that each city is visitedexactly once. The TSP has played a central role in the development of many Stochastic LocalSearch (SLS) algorithms, such as Ant Colony Optimization [5], or Simulated Annealing [9].Currently, the best performing SLS algorithms for the TSP strongly rely on the exploitationof high-performing local search algorithms, and most top-performers are iterated local search(ILS) algorithms [1, 3, 8, 7] or memetic algorithms [4, 11]. While most ILS algorithms are basedon the Lin-Kernighan algorithm (LK) [10], Glover [6] and Rego [13] present an approach basedon an edge based ejection chain method, which, compared to LK, tends to find better tourswhile requiring more computation time. Small and medium size TSP instances ranging froma few hundred to several thousand cities are also solved rather efficiently by exact algorithms,the best example being the branch & cut code of Applegate, Bixby, Chv´atal, and Cook [2].However, a disadvantage of exact algorithms is that they show a very strong variability incomputation time between different TSP instances. Performance variability among instancescan also be observed for SLS algorithms, in addition to the variability in the performance onany given instance that is caused by the stochastic nature of these algorithms.It is clear that the structure of TSP instances influences the amount of time needed tosolve them to optimality. For the scope of this article, our investigation of structure focuses onthe distribution of the cities in the Euclidean plane. In particular, the instances we study arederived from highly structured TSP instances that can be solved in polynomial time, by eitherremoving cities or by perturbing city coordinates. We analyze the impact of these variations inthe structure of TSP instances on the run-time of two high-performance algorithms: Applegateet al.’s branch & cut code (concorde) [2] and Helsgaun’s iterated Lin-Kernighan algorithmlkh[7]. concordeis currently the best performing exact algorithm for the TSP using state-of-the-art B&C methods and is freely available for academic purposes. Helsgaun’s lkhalgorithmVienna, Austria, August 22–26, 2005