Solving Traveling Salesman Problems

Given the cost of travel between each pair of a finite number of cities, the traveling salesman problem (TSP) is to find the cheapest tour passing through all of the cities and returning to the point of departure. We will present a survey of recent progress in algorithms for largescale TSP instances, including the solution of a million city instance to within 0.09% of optimality and the exact solution a 15,112-city instance. We will also discuss extensions of TSP techniques to other path-routing problems, and describe the solution of the WhizzKids’96 problem in vehicle routing. This talk is based on joint work with David Applegate, Robert Bixby, Vasek Chvátal, Sanjeeb Dash and Andre Rohe.