Friday, March 13, 2015
The Traveling Tourist Problem
The most talked about map of this week has to be Randy Olson's map showing a road-trip route across the United States, taking in the top 50 major U.S. landmarks. Randy has actually created two maps, one for the USA - Optimal Road Trip Across the U.S. and one for Europe - the Optimal Road Trip Across Europe.
For both maps Randy took an arbitrary list of the top landmarks to visit and then set about the task as a Traveling Salesman problem. That is finding the shortest possible route that visits each landmark and returns to the origin starting point.
To solve the problem Randy used the Google Maps API and in particular the Google Maps API Directions Service. This enabled him to find the shortest routes between each landmark. He then created his own genetic algorithm to create a route visiting each of the landmarks so that the total distance traveled between them is as small as possible.
Over the years on Maps Mania we have posted a number of maps that help to solve the perennial Traveler Salesman Problem (TSP). Among the most interesting solutions has been the Forio Route Optimizer.
The developers at Forio decided that the TSP was not challenging enough and therefore set themselves the additional challenge of finding the quickest route taking into account real-time traffic conditions. The resulting Forio Route Optimizer finds the quickest route, taking in a number of stops and factoring in the actual traffic on the roads.
The Route Optimizer comes with a number of example routes in San Francisco, including a book crawl and a sightseeing tour of the city. Forio has written-up an interesting blog post on how the Route Optimizer was created, including a link to the source code of the Optimizer on GitHub.