The Traveling Salesman Problem: A Case Study in Local Optimization

TLDR

The traveling salesman problem has long served as a benchmark for combinatorial optimization, attracting classical local optimization methods and newer variants such as simulated annealing, tabu search, neural networks, and genetic algorithms. This chapter aims to examine how these local optimization approaches have been tailored to the TSP and to assess their relative effectiveness. The authors adapt each method to the TSP and evaluate its performance through theoretical analysis and experimental comparison.

Abstract

This is a preliminary version of a chapter that appeared in the book Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra (eds. ), John Wiley and Sons, London, 1997, pp. 215-310. The traveling salesman problem (TSP) has been an early proving ground for many approaches to combinatorial optimization, including classical local optimization techniques as well as many of the more recent variants on local optimization, such as simulated annealing, tabu search, neural networks, and genetic algorithms. This chapter discusses how these various approaches have been adapted to the TSP and evaluates their relative success in this perhaps atypical domain from both a theoretical and an experimental point of view.