Traveling Salesman

What do airlines, truckers, and college students have in common? They all want to travel long distances without spending much money! The problem they’re trying to solve (somewhat simplified) is known as the Traveling Salesman Problem (TSP): find a route for a salesman to visit a number cities at the lowest possible total cost. While the problem is easy to state, it is difficult to solve, because even for a modest number of cities, the number of possible routes is huge. See how close to optimal you can get.

Visit all the cities!

Click on any city to start, and visit all of them, trying to minimize total cost. Blue=already visited (but it's ok to visit again if that helps).

Current Path Cost: 0

All cities visited:? No

Salesman’s Path

No stops have been visited yet.

 


Why is this significant?

Being able to solve this and similar problems can make or break a trucking company, for example. Perhaps more surprisingly, this problem is as hard as a large class of problems for which no efficient solution method is known. Finding an efficient method to solve TSP would give us a method to solve hundreds of other problems in computer science, engineering, biology, chemistry, physics, economics, and mathematics. It would also enable you to play Minesweeper better, and to break strong cryptographic codes used to protect your banking data. Most computer scientists believe (but no one has proven) that no general efficient method to solve TSP exists. Whoever resolves this question (which was first posed by BU’s own Leonid Levin together with Stephen Cook) will win a $1 million prize. Find out about TSP on Wikipedia or Bill Cook's site. Also, check out this comic.