|
Solving a 50-city touring problem of the type described in Discovery News is easy these days. If we are presented with the distance, or time, to travel between each pair of locations, then we have a purely mathematical problem: find the tour around the points that is the shortest among all of the many possible routes. No one knows how to solve such a problem if we are given 100,000 or so points, but for 50 locations, easy peasy.
|
|
The Discovery News problem asks for the best way to visit 50 selected landmarks in the USA. Is this really such a simple task? Well, yes and no. The mathematical problem of finding the best route is certainly very easy, taking well under a second on an iPhone. But to get to the mathematical problem, we need to be handed the point-to-point distance for each pair of the 50 locations. Obtaining good data of this type is far from simple.
The overall tour-finding task is called the traveling salesman problem (TSP), and it has a fearsome reputation for complexity, but only when the number of locations is large. The task of finding a point-to-point route is called the shortest-path problem, and it is known be one of the easiest problems in mathematical optimization. Okay, but when we want to travel on actual roads, the easy point-to-point routing becomes a beast. This is where the mathematics gets entangled with the messy world of traffic, construction, closures, detours, mis-named map data, and on and on.
In 1954, Dantzig, Fulkerson, and Johnson were interested only in the mathematical challenge of the TSP. They selected a city in each of the 48 states in such a way that the point-to-point road distances were readily available in a Rand McNally road atlas. With the distances in hand, they knocked off the TSP challenge in a couple of weeks of by-hand calculations.
For the Discovery News 50-landmarks problem, Randy Olson employed the modern-day version of a road atlas, setting up a computer code to obtain point-to-point travel distances from Google Maps. Fair enough.
Google Maps is an amazing feat of engineering, providing turn-by-turn directions between pairs of points, pretty much anywhere in the world. Still, it is a messy world. And even Google Maps data must be treated with care, to be sure we are getting what we ask for.
In the USA tour, found by Randy Olson and reported throughout the media in March 2015, there is a clear mistake in the data used to create the mathematical TSP challenge. One of the landmark sites that Tracy Staedter and Randy Olson selected for the USA tour is the New Castle Historic District in Delaware. This is a lovely spot near to Wilmington. But the reported USA tour does not come within an hour's drive of New Castle.
|
|
The Discovery News tour misses the stop at New Castle, Delaware Click for larger version |
The problem is that the query to Google Maps for the location of the New Castle district returned a spot in the center of Delaware. Simply modifying the drive to go up to see the landmark site would add two hours to the overall tour (and perhaps cause you to miss your dinner). Much better is to change the order of the tour reported in Discovery News. The optimal route is to travel Annapolis->New Castle->Philadelphia->Cape May->Statue of Liberty, rather than Annapolis->(missing New Castle)->Cape May->Philadelphia->Statue of Liberty.
This correction is due to the error in the input data to the TSP challenge. We have already discussed an improvement in the Discovery News tour that comes from solving optimally the TSP instance constructed by Olson: there is a better way to order the visits in the center of the country.
Finally, when we are really out on the road, the time to travel from location A to location B can be slightly different than the time for the B to A trip. Geoffery De Smet found that, using these more accurate distances, an improvement is also possible in how we visit the Carolinas.
Putting all this together, we are likely getting close to the final word on the planning of the 50-landmarks tour: the TSP mathematics is perfect, but there may be additional ways to tinker with the construction (and choice) of point-to-point distances.
To bring this to a close, I went to the expert in turn-by-turn driving directions, Alain L. Kornhauser of Princeton University. I asked him if he could construct point-to-point travel times for the 50 locations, using the routes recommended by his sophisticated turn-by-turn tools.
A couple of days later, Alain sent a table with travel times (in 1/1000ths of hours) between all pairs of points, including traveling from both A to B and from B to A, to be sure we got the direction of travel correct this time. A half second after that, the Concorde TSP solver produced the shortest possible route through the country, totaling 239.047 hours. (It was actually here when we noticed the error in the location of New Castle in the distances produced by Olson with his Google queries: the optimal tour with Alain's data gave an alternative route through Delaware.)
Here, finally, is the route Alain and I recommend you use to tour the country. The estimated total driving time is just under 10 days.
|
|
Recommended Tour for the 50 USA Landmarks Problem Click for larger version |
