{"id":12597,"date":"2015-05-02T18:18:40","date_gmt":"2015-05-03T01:18:40","guid":{"rendered":"http:\/\/overlandbound.com\/?p=12597"},"modified":"2022-06-24T00:25:53","modified_gmt":"2022-06-24T00:25:53","slug":"the-perfect-u-s-road-trip","status":"publish","type":"post","link":"https:\/\/www.overlandbound.com\/the-perfect-u-s-road-trip\/","title":{"rendered":"The Perfect U.S. Road Trip"},"content":{"rendered":"

Randal S. Olson<\/a>,\u00a0a fourth-year Computer Science graduate research assistant at\u00a0Michigan State, has conducted an experiment. He has computed the perfect road trip across America. You can jump on from any state, and complete the circuit in 10 days (assuming no traffic). I’m not sure what condition you would be in at \u00a0the end, but its theoretically possible!<\/p>\n

 
\nComputing the optimal road trip across the U.S.
\nPosted on March 8, 2015<\/a> by Randy Olson<\/a><\/p>\n

Last week, Tracy Staedter<\/a> from Discovery News proposed an interesting idea to me: Why not use the same algorithm from my Where\u2019s Waldo article<\/a> to compute the optimal road trip across every state in the U.S.? Visiting every U.S. state has long been on my bucket list, so I jumped on the opportunity and opened up my machine learning tool box for another quick weekend project.<\/p>\n

Note: If you\u2019re not interested in the technical details of the project, skip down to the Road trip stopping at major U.S. landmarks<\/a> section.
\nPlanning the road trip
\nOne of the hardest parts of planning a road trip is deciding where to stop along the way. Given how large and diverse the U.S. is, it\u2019s especially difficult to make a road trip that will appeal to everyone. To stand a chance at making an interesting road trip, Tracy and I laid out a few rules from the beginning:<\/p>\n

\tThe trip must make at least one stop in all 48 states in the contiguous U.S.
\n\tThe trip would only make stops at National Natural Landmarks, National Historic Sites, National Parks, or National Monuments.
\n\tThe trip must be taken by car and never leave the U.S.<\/p>\n

With those objectives in mind, Tracy compiled a list of 50 major U.S. landmarks \u2014 one in each state excluding Alaska\/Hawaii and including D.C., and two in California. Tracy wrote about that process on Discovery News here<\/a>.<\/p>\n

The result was an epic itinerary with a mix of inner city exploration, must-see historical sites, and beautiful natural landscapes. All that was left was to figure out the path that would minimize our time spent driving and maximize our time spent enjoying the landmarks.<\/p>\n

<\/a><\/p>\n

Image credit: Dean Franklin<\/a>
\nComputing the optimal road trip across the U.S.
\nWith the list of landmarks in hand, the next step was to find the \u201ctrue\u201d distance between all of the landmarks by car. Since we can\u2019t just drive a straight line between every landmark \u2014 driving by car has this pesky limitation of having to stay on roads \u2014 we needed to find the shortest route by road between every landmark.<\/p>\n

If you\u2019ve ever used Google Maps to get the directions between two addresses, that\u2019s basically what we had to do here. Except this time, we needed to look up 2,500 directions to get the \u201ctrue\u201d distance between all 50 landmarks \u2014 a monumental task if we had to do it by hand. Thankfully, the Google Maps API<\/a> makes this information freely available, so all it took was a short Python script to calculate the distance and time driven for all 2,500 routes between the 50 landmarks.<\/p>\n

Now with the 2,500 landmark-landmark distances, our next step was to approach the task as atraveling salesman problem<\/a>: We needed to order the list of landmarks such that the total distance traveled between them is as small as possible if we visited them in order. This means finding the route that backtracks as little as possible, which is especially difficult when visiting Florida and the Northeast.<\/p>\n

If you read my Where\u2019s Waldo article<\/a>, you\u2019re already aware of how difficult it can be to solve route optimization problems like this one. With 50 landmarks to put in order, we would have to exhaustively evaluate 3 x 1064 possible routes to find the shortest one.<\/p>\n

To provide some context: If you started computing this problem on your home computer right now, you\u2019d find the optimal route in about 9.64 x 1052 years \u2014 long after the Sun has entered its red giant phase<\/a> and devoured the Earth<\/a>. This complication is why Google Map\u2019s route optimization service only optimizes routes of up 10 waypoints, and the best free route optimization service<\/a> only optimizes 20 waypoints unless you pay them a lot of money to dedicate some bigger computers to it.<\/p>\n

The traveling salesman problem is so notoriously difficult to solve that even xkcd<\/a> poked fun at it:<\/p>\n

<\/a><\/p>\n

Clearly, we need a smarter solution if we want to take this epic road trip in our lifetime. Thankfully, the traveling salesman problem has been well-studied<\/a> over the years and there are many ways for us to solve it in a reasonable amount of time.<\/p>\n

If we\u2019re willing to accept that we don\u2019t need the absolute best route between all of the landmarks, then we can turn to smarter techniques such as genetic algorithms<\/a> to find a solution that\u2019s good enough for our purposes. Instead of exhaustively looking at every possible solution, genetic algorithms start with a handful of random solutions and continually tinkers with these solutions \u2014 always trying something slightly different from the current solutions and keeping the best ones \u2014 until they can\u2019t find a better solution any more.<\/p>\n

I\u2019ve included a visualization of a genetic algorithm solving a similar routing problem below.<\/p>\n

Road trip stopping at major U.S. landmarks
\nAfter less than a minute, the genetic algorithm reached a near-perfect solution that makes a complete trip around the U.S. in only 13,699 miles (22,046 km) of driving. I\u2019ve mapped that route below.<\/p>\n

Note: There\u2019s an extra stop in Cleveland to force the route between Vermont and Michigan to stay in the U.S. rather than go through Canada. If you\u2019re able to drive through Canada without issue, then take the direct route through Canada instead.<\/p>\n

<\/a><\/p>\n

Click here<\/a> for the interactive versionAssuming no traffic, this road trip will take about 224 hours (9.33 days) of driving in total, so it\u2019s truly an epic undertaking that will take at least 2-3 months to complete. The best part is that this road trip is designed so that you can start anywhere on the route as long as you follow it from then on. You\u2019ll hit every major area in the U.S. on this trip, and as an added bonus, you won\u2019t spend too long driving through the endless corn fields of Nebraska.<\/p>\n

Here\u2019s the Google Maps of the route: <\/a> <\/a> <\/a> <\/a> <\/a> <\/a><\/p>\n

(Note that Google maps itself only allows 10 waypoints to be routed at a time, hence why there\u2019s multiple Maps links.)<\/p>\n

Here\u2019s the full list of landmarks in order:<\/p>\n

\tGrand Canyon, AZ
\n\tBryce Canyon National Park, UT
\n\tCraters of the Moon National Monument, ID
\n\tYellowstone National Park, WY
\n\tPikes Peak, CO
\n\tCarlsbad Caverns National Park, NM
\n\tThe Alamo, TX
\n\tThe Platt Historic District, OK
\n\tToltec Mounds, AR
\n\tElvis Presley\u2019s Graceland, TN
\n\tVicksburg National Military Park, MS
\n\tFrench Quarter, New Orleans, LA
\n\tUSS Alabama, AL
\n\tCape Canaveral Air Force Station, FL
\n\tOkefenokee Swamp Park, GA
\n\tFort Sumter National Monument, SC
\n\tLost World Caverns, WV
\n\tWright Brothers National Memorial Visitor Center, NC
\n\tMount Vernon, VA
\n\tWhite House, Washington, DC
\n\tColonial Annapolis Historic District, MD
\n\tNew Castle Historic District, Delaware
\n\tCape May Historic District, NJ
\n\tLiberty Bell, PA
\n\tStatue of Liberty, NY
\n\tThe Mark Twain House & Museum, CT
\n\tThe Breakers, RI
\n\tUSS Constitution, MA
\n\tAcadia National Park, ME
\n\tMount Washington Hotel, NH
\n\tShelburne Farms, VT
\n\tFox Theater, Detroit, MI
\n\tSpring Grove Cemetery, OH
\n\tMammoth Cave National Park, KY
\n\tWest Baden Springs Hotel, IN
\n\tAbraham Lincoln\u2019s Home, IL
\n\tGateway Arch, MO
\n\tC. W. Parker Carousel Museum, KS
\n\tTerrace Hill Governor\u2019s Mansion, IA
\n\tTaliesin, WI
\n\tFort Snelling, MN
\n\tAshfall Fossil Bed, NE
\n\tMount Rushmore, SD
\n\tFort Union Trading Post, ND
\n\tGlacier National Park, MT
\n\tHanford Site, WA
\n\tColumbia River Highway, OR
\n\tSan Francisco Cable Cars, CA
\n\tSan Andreas Fault, CA
\n\tHoover Dam, NV<\/p>\n

Bonus: Road trip stopping at popular U.S. cities
\nIf you\u2019re more of a city slicker, the road trip above may not look very appealing to you because it involves spending a lot of time outdoors. But worry not, for I created a second road trip just for you! The road trip below stops at the TripAdvisor-rated Best City to Visit<\/a> in every contiguous U.S. state.<\/p>\n

Note: Again, there\u2019s an extra stop in Cleveland to force the route between New Hampshire and Michigan to stay in the U.S. rather than go through Canada. If you\u2019re able to drive through Canada without issue, then take the direct route through Canada instead. But really, Cleveland is a nice city to stop in (ranked #53 on TripAdvisor).<\/p>\n

<\/a><\/p>\n

Click here<\/a> for the interactive versionThis road trip will more-or-less follow the same path as the major U.S. landmarks trip, covering a slightly shorter 12,290 mile (19,780 km) route around the U.S. Some larger states \u2014 like California and Texas \u2014 may have multiple cities you\u2019d like to visit, so it\u2019s probably worthwhile to stop at other larger cities along the route.<\/p>\n

You may note that cities from North Dakota, Vermont, and West Virginia are missing. Out of the top 400 recommended cities to visit on TripAdvisor, none were from North Dakota, Vermont, nor West Virginia. This is especially interesting because TripAdvisor reviewers recommend cities like Flint, MI \u2014 the 7th most crime-ridden city<\/a> in the U.S. \u2014 over any city in North Dakota, Vermont, and West Virginia. I\u2019ll leave the interpretation of that fact to the reader.<\/p>\n

Here\u2019s the Google Maps of the route: <\/a> <\/a> <\/a> <\/a> <\/a> <\/a><\/p>\n

Here\u2019s the full list of cities in order:<\/p>\n

\tOklahoma City, Oklahoma
\n\tWichita, Kansas
\n\tDenver, Colorado
\n\tAlbuquerque, New Mexico
\n\tPhoenix, Arizona
\n\tLas Vegas, Nevada
\n\tSan Francisco, California
\n\tPortland, Oregon
\n\tSeattle, Washington
\n\tBoise, Idaho
\n\tPark City, Utah
\n\tJackson, Wyoming
\n\tBillings, Montana
\n\tSioux Falls, South Dakota
\n\tOmaha, Nebraska
\n\tDes Moines, Iowa
\n\tMinneapolis, Minnesota
\n\tMilwaukee, Wisconsin
\n\tChicago, Illinois
\n\tIndianapolis, Indiana
\n\tLouisville, Kentucky
\n\tColumbus, Ohio
\n\tDetroit, Michigan
\n\tCleveland, Ohio
\n\tManchester, New Hampshire
\n\tPortland, Maine
\n\tBoston, Massachusetts
\n\tProvidence, Rhode Island
\n\tNew Haven, Connecticut
\n\tNew York City, New York
\n\tOcean City, New Jersey
\n\tPhiladelphia, Pennsylvania
\n\tWilmington, Delaware
\n\tBaltimore, Maryland
\n\tWashington, D.C.
\n\tVirginia Beach, Virginia
\n\tCharlotte, North Carolina
\n\tCharleston, South Carolina
\n\tOrlando, Florida
\n\tAtlanta, Georgia
\n\tNashville, Tennessee
\n\tBirmingham, Alabama
\n\tJackson, Mississippi
\n\tNew Orleans, Louisiana
\n\tHouston, Texas
\n\tLittle Rock, Arkansas
\n\tBranson, Missouri<\/p>\n

Make your own road trip
\nIf you\u2019d like to customize your own road trip, I\u2019ve released the Python code I used in this project with an open source license and instructions for how to optimize your custom road trip. You can find the code here<\/a>.
\nWhat about other parts of the world?
\nI\u2019ve made another version for Europe here<\/a>. Check it out!<\/p>\n

If you\u2019d like to collaborate on making an optimal road trip for other parts of the world, feel free toemail me<\/a>.
\nConclusions
\nThe saying goes, \u201cA journey of a thousand miles begins with a single step.\u201d Really, that\u2019s not true. Every major journey begins with a plan: where you\u2019re going, where you\u2019re stopping along the way, and how you\u2019re getting there. I hope this article convinced you that machine learning can play a crucial role in that planning phase and save you a ton of time along the way.<\/p>\n

Of course, it may not be practical for you to take a road trip of epic proportions like the ones described here. But really, this algorithm works just as well when you\u2019re planning a smaller trip within your state as when you\u2019re planning a larger trip spanning the entire world. All the algorithm needs are the distances travelled between every stop so it can compute the optimal route. How you get between those stops is up to you.<\/p>\n

Happy road tripping!<\/p>\n","protected":false},"excerpt":{"rendered":"

Randal S. Olson,\u00a0a fourth-year Computer Science graduate research assistant at\u00a0Michigan State, has conducted an experiment. He has computed the perfect road trip across America. You can jump on from any state, and complete the circuit in 10 days (assuming no traffic). I’m not sure what condition you would be in at \u00a0the end, but its […]<\/p>\n","protected":false},"author":0,"featured_media":13034,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[26,25],"tags":[],"class_list":["post-12597","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news","category-tips"],"_links":{"self":[{"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/posts\/12597","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/comments?post=12597"}],"version-history":[{"count":0,"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/posts\/12597\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/media?parent=12597"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/categories?post=12597"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.overlandbound.com\/marketing-api\/wp\/v2\/tags?post=12597"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}