Thankfully, the traveling salesman problem has been well-studied over the years and there are many ways for us to solve it in a reasonable amount of time. The traveling salesman problem is so notoriously difficult to solve that even xkcd poked fun at it:Ĭlearly, we need a smarter solution if we want to take this road trip in our lifetime.
#Road trip budget calculator free#
This complication is why Google Map's route optimization service only optimizes routes of up 10 waypoints, and the best free route optimization service only optimizes 20 waypoints unless you pay them a lot of money to dedicate some bigger computers to it. To provide some context: If you started computing this problem on your home computer right now, you'd find the optimal route in about 3.98 x 10 49 years-long after the Sun has entered its red giant phase and devoured the Earth. With 48 landmarks to put in order, we would have to exhaustively evaluate 1.24 x 10 61 possible routes to find the shortest one. If you've read my Where's Waldo? article, you're already aware of how difficult it can be to solve route optimization problems like this one. This means finding the route that backtracks as little as possible, which is especially difficult when visiting Florida and the Northeast. Now with the 2,256 capitol-capitol distances, our next step is to approach the task as a traveling salesman problem: We need to order the list of capitols such that the total distance traveled between them is as small as possible if we visited them in order. Thankfully, the Google Maps API makes this information freely available, so all it takes is a short Python script to calculate the distance and time driven for all 2,256 routes between the 48 capitols. Except this time, we need to look up 2,256 directions to get the "true" distance between all 48 state capitols-a monumental task if we have to do it by hand. If you've ever used Google Maps to get the directions between two addresses, that's basically what we have to do here. Since we can't just drive a straight line between every capitol-driving by car has this pesky limitation of having to stay on roads-we needed to find the shortest route by road between every capitol. state capitols in hand, the next step is to find the "true" distance between all of the capitols by car. Image credit: Daniel Mennerich Recap: Optimizing road trips That said, by going on this road trip we're in for an epic journey and some beautiful architecture. Lastly, to clarify: The goal is to visit the capitol buildings, not the city the buildings are located in (i.e., state capitals). Whenever possible, we will avoid routes that require us to travel through foreign countries, as entering/leaving the country requires a passport and border control tends to slow things down. We will travel only by car, so that rules out Alaska (too far away) and Hawaii (requires a plane flight) and leaves us with the 48 contiguous states (excluding D.C.). (Bonus points for entertaining or themed pictures!) state capitolsįor this road trip, there is one goal: to take a picture at as many U.S. Note: If you're not interested in the technical details of the project, skip down to the 48 U.S. I'll briefly describe how Pareto optimization works, and how it helps us optimize road trips on a limited budget. In this article, I'm going to expand on the idea of optimizing road trips by introducing multi-objective Pareto optimization to the algorithm. In reality, most of us have budgetary constraints on our road trips: we can only spend so much money, or we only have so much time off before we have to get back to work. One thought that struck me was that the road trips I created before were quite grandiose-spanning entire states or even most of Europe-such that only people who had some savings and were able to take a month off of work could even hope to go on one of the trips.
During that time, I've given some thought to how I could make that algorithm more useful to folks looking to plan their summer road trips. About a year ago, I wrote an article introducing the concept of optimizing road trips using a combination of genetic algorithms and Google Maps.
0 kommentar(er)
