How does Google or Mapquest figure out the quickest way to Point A to Point B?

[OldGuy]

The computer programs certainly have improved over the years. When Mapquest was first out, it routed me through CT by getting on and off I-95 and using the parallel route 1.

And no it wasn’t the shortest distance option.

[Irishman]

US Bureau of Labor Statistics said:

At first, the only route it would return would be through Little Rock. About a year ago it started returning through Little Rock and through the Ozarks up Highway 71. Then it added a path directly west into Oklahoma then directly north pretty much making two legs of a right triangle.

Let me get this straight: It was sending you up Hwy 71 (i.e. I-540), then across Hwy 412? Or is that through the Oachita to Y-city, then Hwy 71 South, then I-40 to Hwy 75?

Just now in the past couple months it’s started defaulting to the Hwy 71 route, offering a route which goes through more the Oklahoma side than Arkansas, and the Little Rock route is listed third.

That the path you have highlighted?

This is about consistent with reality: the first two sides are roughly the same travel time, the Little Rock path is about 15-30 minutes longer.

I’m not clear on what you’re saying, but the highlighted route is shortest and fastest. The route through Little Rock is mostly interstate vs. the winding state highways through the mountains, so I can see how the trip could average out to be not that much slower (though longer). (Mountain road routes have lower speed limits, plus pass through towns at 25 to 30 mph for stretches, breaking up the travel.) But that wouldn’t apply to the northern half the trip. The path through Muskogee is interstate quality hwy, so I can’t see going I-540 to Fayetteville getting any advantage, and it is farther. Though the I-540 route is much nicer than when it was just Hwy71 north. (I’ve driven the Ft. Smith/Tulsa route numerous times, and the Hwy 71 north bit a few times. Also been the Hwy 71 south run a bunch, but kept south to Texarkana at Y-city.)

[Gary_Robson]

@Chronos

A related one is the delivery driver problem: Given deliveries at these six addresses, what’s the best order to do them?

Isn’t that the same as the traveling salesman problem? Assuming, of course, that you already know the distance between any pair of addresses.

And six addresses seems like a poor test… That’s small enough that you can still easily brute-force it, which means you’re not teaching any of the non-brute-force methods that become necessary for larger sets.

I picked the number six at random. I don’t remember how many were in the assignment in college, but I think our programs had to handle any arbitrary number that fit within our allocation of memory and CPU time (this was back in the days of timesharing systems). In real life, of course, if applied to something like a UPS truck, the number would be pretty big.

I do remember the prof walking through the problem manually on the board using matrix manipulation, and that was with a small number of deliveries.