Retour

Séance MB1 - Exposé magistral II / Tutorial II

Jour lundi, le 7 mai 2007
Salle Banque Scotia
Président Olivier Bahn

Présentations

15h30-
17h10
The Traveling Salesman Problem
  Gilbert Laporte, GERAD, HEC Montréal et CRT, Chaire de recherche du Canada en distributique, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7

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.


Retour