|
Given a collection of cities and the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all of the cities and returning to your starting point.
In the standard version we study, the travel costs are symmetric in the sense that traveling from city X to city Y costs just as much as traveling from Y to X.
The simplicity of the statement of the problem 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 70 years its
study has led the way to improved solution methods in many areas of
mathematical optimization.
|
