Pictoral History of the TSP
The traveling salesman problem, or TSP for short, is easy to state:
Given a finite number of "cities" along with the cost of travel between each
pair of them, find the cheapest way of visiting all the cities and returning
to your starting point.
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 "way of visiting all the cities" is simply the order in which
the cities are visited.
To put it differently, the data consist
of integer weights assigned to the edges of a finite complete graph; the
objective is to find a hamiltonian cycle (that is, a cycle passing through
all the vertices) of the minimum total weight. In this context, hamiltonian
cycles are commonly called tours.
The origins of the TSP are obscure. In the 1920's, the mathematician
and economist Karl Menger publicized it among his colleagues in Vienna.
In the 1930's, the problem reappeared in the mathematical circles of Princeton.
In the 1940's, it was studied by statisticians (Mahalanobis (1940),
Jessen (1942), Gosh (1948), Marks (1948)) in connection with an agricultural
application and the mathematician Merill Flood popularized it among his
colleagues at the RAND Corporation. Eventually, the TSP gained
notoriety as the prototype of a hard problem in combinatorial optimization:
examining the tours one by one is out of the question because of
their large number, and no other idea was on the horizon for a long time.
Start the pictorial history with George Dantzig, Ray Fulkerson, and Selmer Johnson's 1954 breakthrough by clicking
here or jump ahead to a year that interests you by choosing one of the links in the table below.
 
|
