Colleagues are welcome to attend the below seminar hosted by CORMSIS at the University of Southampton.
Time : 16:00 - 17:00, Thursday 21st February 2008
Location : University of Southampton, School of Mathematics, Room 8B
http://www.soton.ac.uk/about/campusmaps/highfieldmap.html
'A Short History of the Travelling Salesman Problem'
by
Gilbert Laporte
Canada Research Chair in Distribution Management
HEC Montreal
Abstract: The Travelling 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) contains 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. I will provide a short history of the TSP, I will describe the evolution of the main ideas for this problem, and I will point out the most successful exact and heuristic algorithms.
|