Althouse: "Computing the optimal road trip across the U.S."

May 22, 2015

"Computing the optimal road trip across the U.S."

"[W]e needed to look up 2,500 directions to get the 'true' distance between all 50 landmarks... Now with the 2,500 landmark-landmark distances, our next step was to approach the task as a traveling salesman problem: 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...."

32 comments:

J2 said...: 1. "Wallyworld"; 5/22/15, 7:30 AM
MadisonMan said...: Why pick Taliesin when you can pick The House on the Rock?; 5/22/15, 7:35 AM
paminwi said...: If you like road trips - awesome!
Some places I'd leave out, others I'd add but it would be a good staring point for someone so inclined.

As far as Taliesin - I think others are more impressed with FLW than I will ever be after reading a biography of him. He was an ass.; 5/22/15, 7:38 AM
pm317 said...: Cool! In the comments people are questioning some of the choices for the landmarks though.; 5/22/15, 7:38 AM
john said...: Don't focus on the stops, focus instead on the method. You can design your own optimal trip with these instructions, then you can fit in all the Nebraska cornfields you wish.; 5/22/15, 7:38 AM
jimbino said...: The drive from San Antonio to Carlsbad will be longer and more boring than one through Nebraska cornfields.

Do me the favor of keeping track of all the Black, Brown and Red American faces you see in those vaunted national parks, forests and monuments. I bet you find about 1 minority face to 1000 white faces. You would find the same variety if you toured Florida golf clubs and gated communities.

The difference is that our minorities are not charged for acquiring and maintaining those gated white communities and white golf clubs.; 5/22/15, 7:52 AM
pm317 said...: The order of the states to visit without too much backtracking does not need a Genetic TSP alg..; 5/22/15, 7:57 AM
WillowViney said...: Given that TSP is NP-Complete, solving it for N=25,000 might take a while. Years maybe?; 5/22/15, 8:03 AM
Etienne said...: With 40,000 deaths on the roads every year, I encourage everyone to get out there and participate.; 5/22/15, 8:03 AM
Roger Sweeny said...: If you're going to drive a lot, the driving should be part of the pleasure. Forget this and get a copy of The [120] Most Scenic Drives in America (which includes a lot of destinations along the way).; 5/22/15, 8:10 AM
Jaq said...: 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 — the 7th most crime-ridden city in the U.S. — over any city in North Dakota, Vermont, and West Virginia. I’ll leave the interpretation of that fact to the reader.

Color me unsurprised. I was wondering when I saw this were they would go in our great state. Maybe the site of the St Albans raid, where Confederate soldiers robbed a bank near the Canadian border?

IDK, Shelburn Farms? I guess... There are lots of national forests here, but no national parks. Burlington is cute, but so is Ithaca, State College, etc... Vermont is more a federation of small things joined together along the idea of being an English speaking version of the French countryside. There is no *one* place to visit here. But at Shelburn Farms, there is a view of the lake and across it the Adirondacks, specifically the Adirondack park on the far side, and the view is unspoiled on the Vermont side by development beyond hay fields and the occasional barn. It really does look like a painting right out of the "Hudson Valley School." So they should take a nice camera, a tripod, and a lot of time to wait for the light to be just right.; 5/22/15, 8:12 AM
Jaq said...: @jimbino,
We got your message. White people should stop reproducing, we should raze the National Parks and sell the land for condos.; 5/22/15, 8:13 AM
Etienne said...: ...we should raze the National Parks and sell the land for condos.

It would help pay off the Reagan years of the debt :-); 5/22/15, 8:24 AM
Clyde said...: Shouldn't it be 2,450 rather than 2,500? 50 destinations times the other 49?; 5/22/15, 8:27 AM
Jaq said...: It would help pay off the Reagan years of the debt :-)

What are we going to to sell off to pay for the fact that Obama doubled it?; 5/22/15, 8:31 AM
Ignorance is Bliss said...: Willow Viney said...

Given that TSP is NP-Complete, solving it for N=25,000 might take a while. Years maybe?

The number of routes they give is 2,500, not 25,000. And, as Clyde points out, it should be 2450.

But that is the number of routes. When discussing the complexity of the TSP, N is the number of cities, not the number of routes. Thus, N = 50.; 5/22/15, 8:32 AM
Etienne said...: What are we going to to sell off to pay for the fact that Obama doubled it?

I'd sell Wyoming to the ranchers who are squatting on federal land already.; 5/22/15, 8:34 AM
lgv said...: Someone like me thinks this is totally awesome and deserves a Nobel Prize. But then again, I once thought every decision in my life could be represented in a multiple regression or linear programming model.

Now, where the application that allows us to pick and choose all the landmarks and spits out the optimum route for our selected landmarks and starting point? Better hurry if he wants to monetize this puppy.; 5/22/15, 8:42 AM
Eric the Fruit Bat said...: (1) They played that kind of nodal analysis for laughs on The Big Bang Theory. Had something to do with the guys using a dry erase board to figure out where to get dinner before a movie or something like that.

Sheldon made the project more complicated than it had to be, of course.

(2) Watched a bit of Cowboys & Aliens, last night. Too much CGI jiggy stuff zipping across the screen for my middle-aged tastes, but Olivia Wilde may quite possibly be the most beautiful woman ever in the entire history of the human species.

A compensation.; 5/22/15, 8:47 AM
Jaq said...: It only takes one hot woman to make a movie bearable.; 5/22/15, 9:02 AM
Ignorance is Bliss said...: With 50 landmarks to put in order, we would have to exhaustively evaluate 3 x 1064 possible routes to find the shortest one.

To provide some context: If you started computing this problem on your home computer right now, you’d find the optimal route in about 9.64 x 1052 years — long after the Sun has entered its red giant phase and devoured the Earth.

Silly alarmism.

They're talking about the brute force approach. If they use a smarter algorithm they can get a perfect solution in ~300,000 years. Plenty of time to plan your trip before the Sun goes red-giant.; 5/22/15, 9:25 AM
rhhardin said...: When a town with rental housing annexes surrounding territory, the roads in the surrounding territory disintegrate.

The town voters prefer their programs to paving roads they never use, but they like the tax revenue from the annexation.

So my store bike route is longer to avoid direct roads with potholes in them.

In short, distance is not the only thing to consider.; 5/22/15, 9:40 AM
MadisonMan said...: Who in their right mind is going to take this trip, anyway?

The whole thing is clickbait and I am sorry to have succumbed.

I did like the link at the story from the person who took his kids to visit all the County Seats/Courthouses of Colorado. That's something that is a better goal -- get to know your own state. I don't think I've ever been in Oconto County (or even Door County!); 5/22/15, 9:57 AM
George Grady said...: The number of routes they give is 2,500, not 25,000. And, as Clyde points out, it should be 2450.

Actually, it should be only 1225, since the distance should be (essentially) the same regardless of which direction you go.; 5/22/15, 9:58 AM
Michael K said...: A nice road trip is a week in a motor home in Alaska. I did it with my kids 25 years ago and suggested it for the grandkids this summer but they are probably a couple of years too young. Not sure I'll be around when the time is right.; 5/22/15, 10:09 AM
Jaq said...: Actually, it should be only 1225, ...

Not to mention that a simple bounding box twice the size of, say, Texas, of latitude and longitude for each location could probably remove hundreds of absurd candidate routes. Did they *really* need to know the exact distance to Yellowstone from the Statue of Liberty?; 5/22/15, 10:39 AM
Jason said...: Start with the "Eight Queens" problem. Then work your way up.; 5/22/15, 10:59 AM
KLDAVIS said...: The solution can't be optimal. It drives through my home town (a place that couldn't even qualify as the middle of nowhere in Montana), which is inexcusable.; 5/22/15, 3:29 PM
Anonymous said...: We did a similar sort of road trip last fall. Left Upstate New York and took the northern route (sort of) to Montana, and then down towards San Clemente, CA. Came back the southern route to TN for a wedding, and then back home. Had some time and location constraints, as well as hotel room constraints. Took 7 weeks and 10,000 miles.

Saw IU, the Mustard Museum, Lake Superior, the Corn Palace, Mt Rushmore, Custer's Last Stand, Glacier NP, National Bison
Range, Yellowstone NP, Grand Tetons NP, Jackson Hole, Bryce Canyon NP, and Zion NP.

Trip back was less exciting--saw Lake Mead, Boulder Dam (now called Hoover Dam), the Grand Canyon NP, the Codetalker Museum in the Navajo Nation, Durango, the Aztec Ruins, Taos, NM, the Alamo and the Riverwalk, Lafayette, LA, Mississippi Gulf Coast (Pass Christian), Mobile, Chattanooga, Pigeon Forge, TN and then home.

We now know what we want to see more of, and it's all out west.; 5/22/15, 4:20 PM
readering said...: What--2 versions of the road trip and neither stops in Southern California?; 5/22/15, 5:01 PM
Carol said...: Tim, couldn't one visit the home of Calvin Coolidge? Isn't there a monument of some sort there?

Seemed like it would be a pretty area.; 5/22/15, 5:03 PM
Largo said...: Not just a hard road trip -- an NP-hard road trip!; 5/23/15, 3:54 AM