Traveling Salesman Problem

Given a set of cities, find the shortest route that visits each city exactly once and returns to the home city.

Applications include:

• Vehicle routing -- eg, how do we route school buses to pick up children, how do Federal Express and UPS assign packages to trucks?
• VLSI chip board manufacturing: holes need to be drilled on the board. How do we route the drill to visit all these holes so it takes the shortest possible route?

Website:

http://www.keck.caam.rice.edu/tsp/

Largest problem solved to date has more than 13000 cities.