A breakthrough came when George Dantzig, Ray Fulkerson, and
Selmer Johnson (1954) published a description of a method for solving
the TSP and illustrated the power of this method by solving an instance
with 49 cities, an impressive size at that time. They created this instance
by picking one city from each of the 48 states in the U.S.A. (Alaska and
Hawaii became states only in 1959) and adding Washington, D.C.; the costs
of travel between these cities were defined by road distances. Rather than
solving this problem, they solved the 42-city problem obtained by removing
Baltimore, Wilmington, Philadelphia, Newark, New York, Hartford, and Providence.
As it turned out, an optimal tour through the 42 cities used the edge joining
Washington, D.C. to Boston; since the shortest route between these two
cities passes through the seven removed cities, this solution of the 42-city
problem yields a solution of the 49-city problem.
(Picture is a link to a higher resolution version.)
|
