Journées de l'optimisation 2007 Optimizations days

The Traveling Salesman Problem (TSP) is arguably the most famous problem in combinatorial optimization. It has been widely studied for more than 50 years and it underlies several applications in transportation and logistics. The origins of the TSP are rather fuzzy. Early references can be found in Euler (1759), Kirkman (1855), Hamilton (1856) and Menger (1930). The Lawler et al. book (1985) and Halskau's thesis (1999) contain a number of interesting notes on this problem. The study of the TSP has stimulated most of the algorithmic ideas that now constitute the basis of combinatorial optimization. The first important reference is that of Dantzig, Fulkerson and Johnson (1954) which establishes the bases of cutting planes and polyhedral theory. The paper by Little et al. (1963) is one of the first successful applications of branch-and-bound, while Lin's article (1965) on r-opt exchanges is fundamental in local search. In this tutorial I will provide a short history of the TSP, I will describe the evolution of the main algorithmic ideas for this problem, and I will point out the most successful exact and heuristic algorithms.