Logo TSP History > TSP in Pictures > 1954: 49
TSP Joke Book
  Home
  TSP History
  TSP in Pictures
1954: 49
  1962: 33
  1977: 120
  1987: 532
  1987: 666
  1987: 2392
  1994: 7397
  1998: 13509
  2001: 15112
  2004: 24978
  Milestones
  Bibliography
  Travelling
The First Big TSP
1954
n=49
1962
n=33
1977
n=120
1987
n=532
1987
n=666
1987
n=2392
1994
n=7397
1998
n=13509
2001
n=15112
2004
n=24978
 Next

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.

Dantzig, Fulkerson, and Johnson's optimal tour
(Picture is a link to a higher resolution version.)

Home | TSP History Back
Last Updated: Jan 2005