Logo TSP History > Milestones > 49 cities
big problem
  Home
  TSP History
  TSP in Pictures
  Milestones
49 cities
  120 cities
  318 cities
  532 cities
  666 cities
  2392 cities
  7397 cities
  15112 cities
  24978 cities
  Bibliography
  Travelling
DANTZIG42

DANTZIG42 is the reduced problem obtained by Dantzig, Fulkerson, and Johnson in their classic 1954 paper on the solution of a TSP consisting of one city in each of the 48 continental states in the U.S., plus Washington, D. C. The authors worked with a 42-city instance, noting that the optimal tour through the 42 cities uses roads that pass through the 7 cities that were excluded. The instance is specified by the inter-city travel distances bewteen the 42 points; the authors write that the distance table was prepared by Bernice Brown of the Rand Corporation. The data set is part of the TSPLIB.

49 cities

Home | TSP History Back
Last Updated: Jan 2005