Optimal Road Trips

Plotting road trips has long been a source of inspiration for TSP researchers. Dantzig, Fulkerson, and Johnson used a Rand McNally distance table in their classic work, ploting an optimal tour through 49 USA cities in 1954. In the early 1970s, Martin Groetschel set a TSP world record by solving a 120-city instance, where he obtained the point-to-point travel distances from a German atlas.

In the 1980s and onward, attention turned to geometric examples of the TSP, where travel costs were measured as the straight-line Euclidean distance (rounded to a whole number). The reason for abandoning road-trip examples was the need for ever larger data sets, as TSP solution methods and available computing platforms improved year after year.

With the rise of mapping services, such as Google Maps and Open Street Map, it is now possible to go back to the TSP's roots and work on road-trip problems, similar in spirit to those solved by actual traveling salesman in the early 20th century.

Portion of optimal college tour. Click for a full image. For an interactive version Click Here.

Outside Links

• Computing the optimal road trip across the U.S., blog post by Randy Olson. Randy made a nice Google Map drawing of a near-optimal tour through 50 USA landmarks. His tour was discussed on NPR's Weekend Edition.
• The Fastest Parade Ever, blog post by Sam Burer. Sam describes another nice way to create a TSP map with a call to Concorde.