How do online mapping tools calculate best distance + time?

Poorly….

GREAT QUESTION. ive been wondering this forever because they always seem to give the longest/dumbest way.

Generally they use posted speed-limits to do the estimating, but as you have discovered, the algorithms are flawed.

They certainly don’t account for rush hour, construction, bad drivers, or the likelihood of running into a three-mile-long train.

My understanding is they use pre-computed segments to solve the problem using an algorithm such as Dijkstra’s (or something similar—see the list of graph and tree search algorithms in the right sidebar). Anyone who graduates with a computer science degree [should have] studied some of these famous algorithms.

As for traffic I hear they use anonymous GPS data from anyone with a smartphone (e.g. Android OS phones). They can detect what speed you are traveling at, what your course over ground is and compute average traffic given the time of day as well as instantaneous traffic (i.e. is anyone on highway X moving at all?).

Whoa, Tim, that just got you over 3K, unless I’m maxed out on you.

@timtrueman Thanks! I’m also interested in the differences between different sites—I’m getting different results; is it more likely they’re using different shortest-path algos, or using the same algos with different data?

The algorithms are probably roughly the same (anyone that found a breakthrough algorithm would instantly have world fame in the computer science world and engineers suck at keeping secrets if my observations serve me correctly). I would guess the data is significantly different. If I had to recommend any one service, I would say Google is hands down the one I’d go with—insanely smart engineers, a relentless pursuit of more and more data and one of the biggest networks of mobile phone providing useful, anonymous data to make more and more accurate estimates. Nobody is ever perfect but I’d say they are the closest. I sound like a Google fanatic but really I’m not—hey other people, get your act together!

@timtrueman And how do these compare with your average onboard gps for initially programming routes

I am always surprised when I test my GPS against my knowledge of back country roads around where I live. It always does a nearly “human” job of decision making. It must have a lot of data.

Calculating the shortest path is a very hard and complex computational problem. It can be done in numerous ways, but the most popular algorithm is Dijkstras algorithm. This algorithm runs at a speed of Ordo(Number of cities + Number of roads), which is computer lingo for saying “it’s fucking slow”.

Basically it’s trying every possible solution, which takes alot of time and CPU power. It’s very similar to the Travelling salesman problem, which is known to be NP-complete. NP-complete means there is no way to find a quick solution, except trying all the possible alternatives (which takes a LONG time – solving a simple problem with only 1000 citites and 10000 roads would take a set of high powered computers many years).

You can think of NP-completeness in terms of the rubiks cube. Say you make a move on your cube, are you now closer or further from having solved the cube? You can’t tell can you? That’s because the problem in itself gives no clues as to wether you have moved closer to the solution or not. So what’s the fastest way (fewest moves) to solve a rubiks cube? There’s no way to know without having the computer try all possible ways to get a solution. That’s what NP-completeness means.

Finding the shortest path is very computationally heavy, thats why most online sites use a combination of dijkstras with some added on heuristics (a fancy word to say “more or less educated guesses”), different sites have different heuristics, which is why you get different results.

It’s basically a very hard problem to calculate the shortest path quickly, and the more cities and roads you add, the worse the problem gets. If someone would invent an algorithm that could do it quickly, they would become very famous and very rich very quickly, as that would solve the whole family of NP-complete problems (all the problems in the family can be translated in terms of eachother – so solving one would solve all of them).

We’ve rented cars in old EU cities and tried to use GPS, but the ‘reading the map and orienting yourself to the highest visual point (usually the church)’ always saves the day and gets us there in the end. (even if we have to sneak through an alley way or up a one way road with no traffic on it for a second or two… hehehehe).

To test these things too, we’ve used them to map out known trips we take and know the way ourselves and they do sometimes plot out a very strange route, indeed. Hubby works in the field of navigation and GPS, so when these things first came out online we were very anxious to see how they worked.

I don’t think they should be relied on entirely, but they do spit out semi-useful maps in a pinch. We might use them and now are aware that they aren’t 100% efficient, but somewhat helpful in finding the way. We had one experience in France where we were trying to find our B&B outside of a little town called Salon. But the computerised plot map failed in two areas. 1. Detours because of road works 2. Recently completed road works! We were trying to count the round abouts and the map was very wrong and disorienting. In the end, we stopped and asked a shopkeeper. We vowed to never totally rely on the computerised way finders again and to always have a back up.