Saturday, January 12, 2013
TSP Touring the United States (115,475 Cities)
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
Subscribe to:
Post Comments (Atom)
Related Posts
-
Kamar mandi / toilet biasanya dilengkapi dengan perlengkapan untuk buang air kecil maupun besar. Kamar mandi yang dilengkapi dengan urina...
-
Oleh: Andre Vincent Wenas,MM,MBA. (twitter@andrewenas) Bisnis berkembang, organisasi bertumbuh alias karyawan tambah banyak, terjadi p...
-
Menentukan tingkat inventory yang tepat merupakan pekerjaan yang paling penting dan menantang bagi operation manager. Jika terlalu banya...
-
Supply Chain Management Edisi Kedua Buku ini menyajikan konsep, teori, dan contoh-contoh aplikasi dari supply chain management. Dike...
-
by Imam Budiraharjo Dalam dunia bisnis di Jepang, ada satu istilah yang disebut dengan keiretsu (系列) atau perkongsian dalam bahasa In...
No comments:
Post a Comment