糖心TV

Title:     The Traveling Salesman Problem: Theory and Practice in the Unit Square

Speaker:   David S. Johnson (AT&T Research Lab)
Time:      27 April 2011, 16:00
Location:  MS.05

Abstract:

In the Traveling Salesman Problem (TSP) we are given a collection of cities and the distance between each pair, and asked to find the shortest route that visits all the cities and returns to its starting place. When writers in the popular press wish to talk about NP-completeness, this is the problem they typically use to illustrate the concept, but how typical is it really? The TSP has also been highly attractive to theorists, who have proved now-classical results about the worst-case performance of heuristics for it, but how relevant to practice are those results?

In this talk I provide a brief introduction to the TSP, its applications, and key theoretical results about it, and then report on experiments that address both the above questions. I will concentrate on randomly generated instances with cities uniformly distributed in the unit square, which I will argue provide a reasonable surrogate for the instances arising in many real-world TSP applications. I'll first survey the performance of heuristics on these instances, and then report on an ongoing study into the average length and structure of their optimal tours, based on extensive data generated using state-of-the-art optimization software for the TSP, which can regularly find optimal solutions to TSP instances with 1000 cities or more.