48 state capitols in 8 1/2 days
Olson established a series of premises that would determine his later calculations. In the first place, the objective was not to visit cities, but as many state capitols as possible . In second place, would only travel by car , which leaves Alaska out of the route, due to its distance, and Hawaii, due to the need to take a plane, restricting the route to the 48 contiguous states. Third and last, Routes that require passing through other countries would be ruled out to avoid passports and border controls that slow down any journey, explains Randal S. Olson on his website.
Taking this into account, the researcher used a combination of genetic algorithms, Google Maps and Pareto multi-objective optimization , or what is the same, he discovered that perfection in a road trip through the United States supposes visit 48 state capitols traveling 21,420 km in 8 and a half days . As long as there is no traffic, of course. In addition, he also determined that the trip can be started from any point on the route without altering the final result.
How did he do it? With the list of capitols in hand, Olson had to establish what was the actual distance, by road and not in a straight line, between these buildings. To do this, he turned to the Google Maps API, which calculated the distances on the 2,256 possible routes.
With the routes calculated, the next thing was to order them so that their combination would result in the least possible number of kilometers traveled. The genetic algorithm had the answer. His interest lies in the fact that, instead of looking for all possible options, he provides random solutions, always trying something different and keeping the best proposals, until he cannot find a better one.
All this combined with the application of Pareto multi-objective optimization , which allows optimizing multiple criteria at the same time. In this case at hand, it would maximize the number of states to visit and minimize the time needed to do so.