The traveling salesman problem, or TSP for short, is easy to state: given a number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. The simplicity of the statement is deceptive - the TSP is one of the most intensely studied problems in computational mathematics and yet no effective solution method is known for the general case. Indeed, the resolution of the TSP would settle the P versus NP problem and fetch a $1,000,000 prize from the Clay Mathematics Institute.
Although the complexity of the TSP is still unknown, for over 50 years its study has led the way to improved solution methods in many areas of mathematical optimization. We will discuss the history of the TSP and examine the role it has played in modern computational mathematics. We will also present a collection of TSP applications, ranging from genome sequencing to on-line grocery shopping. Finally, we will present a survey of recent progress in algorithms for large-scale TSP instances, including the solution of a million-city instance to within 0.09% of optimality and the exact solution of a 15,112-city instance.
This talk is based on joint work with David Applegate, Robert Bixby, and Vasek Chvátal. It is partially supported by the Institute of Technology Alumni Society.