Making use of the great data collected by the US Geological Survey, I'd like to
propose a 115,475-city challenge through (nearly) all cities, towns, and
villages in the contiguous 48 states. The nearly comes from pruning the USGS
data set to remove places with different names but almost identical
latitude-longitude coordinates.
A drawing of the point set is given below. Click on the image to see a larger
version of the drawing.
It is tempting to consider actual driving distances for the TSP instance, but
this would make it a moving target (as roads are created or improved) and it
would also make it very difficult to manage the large amount of data. To make
the instance precise, we specify the travel cost between two points to be the
Euclidean distance rounded to the nearest integer value, that is, we imagine our
salesman owns a helicopter. This is the TSPLIB travel cost that has been the
standard since the early 1990s.
The point set is available in TSPLIB format in the file usa115475.tsp.
-Are there really 115,475 cities in the United States?
-Previous TSP tours of the 48 states.
-Hitting each of the 48 states.
To add a bit of spice, we are offering $500 to the person/team who first
provides, before July 4, 2013, the best tour reported up to that date. This is
not asking for a provably optimal solution to the problem (although that is, of
course, the long-term goal), but a year-long competition for tour-finding
heuristic methods. Who can find the shortest tour?
More info:
http://www.tsp.gatech.edu/data/usa/index.html
No comments:
Post a Comment