Logo USA > 48 States
USA
  Home
  TSP Test Data
  USA
  115,475 Cities
  USA Tours
48 States
  Leader Board

Hitting each of the 48 States

A variant of the traveling salesman problem is when the salesman needs only to visit one city from each of a number of groups of cities. A prominent example is to visit a city in each of the lower 48 states. You get to choose the cities, but the goal is to minimize the total travel time over all possible choices.

The 50-states version of the challenge is discussed in the New York Times Numberplay blog from January 16, 2012. And reaching all states in 10 days or under is a standing motorcycle rally challenge.

The list of locations in the new 115,475-city TSP instance is organized state-by-state, so this data set can be used as a specific case of the 48-states challenge: What is the shortest tour or path that includes at least one city from the list in each of the 48 states?

To capture the spirit of the motorcycle rally, you would need to use driving distances (from, say, Google Maps), rather than the straight-line distances we use in the TSP instance. So consider it as two problems. In the first we use the TSPLIB Euclidean distance between cities and in the second we use driving distances.

Newsweek

Here are a few news items concerning 48-state tours.

Statesman
American Statesman, May 23, 2010
Home | USA Back
Last Updated: August 2022