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.
Here are a few news items concerning 48-state tours.
|
|
American Statesman, May 23, 2010
|
| 
