Google Maps (& similar apps) Directions Algorithm

Factual Questions
1

The other day I was driving some from work and decided as a lark to see what directions Google Maps would give me. (It actually varied a bit from the various ways I’ve used over the years, but that’s not relevant here.) What I found odd was that it told me to take the state road I was on about 7 miles past where I usually get off, and take an interstate road from that point. Now I happen to know that that interstate road is heavily traveled and would take longer and did not intend to take it, and was going to get off earlier and take the county road that I ordinarily use. And lo and behold, as I got closer to my exit, the app announced that I could save 4 minutes by taking the earlier exit that I had known to be faster anyway. Question is why this happened.

It’s theoretically possible that there was a accident or sudden build up of traffic on the state or interstate road, but I doubt it (usually it tells you that). My theory is that the algorithm for an app of this sort is programmed to look only at major roads when calculating long distance trips, but switches to looking more closely at more minor roads when the distance gets closer. And the reasoning is simply a matter of complexity.

Imagine you asked for directions from NY to California. If the app tried to calculate every possible permutation of roads that went from NY to CA, every possible variation and shortcut over the course of that trip, it would be overwhelmed. It’s a lot simpler to simply favor at the outset major roads which cover hundreds of miles and not even consider the myriad alternatives. But as you get closer, the number of permutations gets much smaller, and it’s more feasible to consider them all.

Something of this sort may be at work here. The idea being that as I was further away, with any number of exits that I could have turned off on, the app simply disregarded all this in favor of a state road. Once I was closer, and had already passed up most of the possible alternative routes, then the calculation became simpler and the algorithm considered the earlier exit with the county road route.

I’m not certain this is correct (though I suppose I could test it by trying the same thing again and seeing if it consistently happens). But if it is, I can think of a couple of possible practical ramifications.

[ol]
[li]Suppose you don’t keep the app live but instead print it out before you leave. You would never have the opportunity for the app to reconsider.[/li][li]Suppose there are 2 routes, Route A and Route B. Using only major roads, Route A is shorter, but Route B has shortcuts which make it shorter. At the outset the app will direct you to take Route A, and you will never even get the opportunity to avail yourself of the app reconsidering the Route B shortcuts.[/li][/ol]

2

A simple algorithm might behave as you describe. But Google’s algorithm isn’t simple. If its recommendations change, it’s because of changing traffic conditions.

3

This would be my assumption, as well, that it is reacting to real-time traffic conditions. Check again tomorrow, OP, and see if it gives you the same route. And then check again a third time. I don’t recall Google Maps app telling me about why a route is a certain way (like accidents, etc.) It just shows me the quickest route, according to its current assessment of road conditions.

4

So, for a more extreme example: suppose at 3:30 on a Friday afternoon, I ask Google Maps for directions from my home in Portland, OR to Boston. Does Google take the current rush-hour traffic in Chicago into account when calculating the route, and estimating the time the trip will take?

5

That’s a good question. I don’t know whether it’s smart enough to predict what traffic will be like in X hours’ (or days’) time in a place that you will reach much later. Or if it just bases its route on what the traffic is like now, and updates on the fly as you go.

6

Not an answer, but ever since Google Maps once recommended I take an unplowed forest road to my destination (Somehow Google Maps thinks cars can drive through 1.5 m of snow) I’ve given up on that.

I know Apple Maps and Google Maps have also frequently advised me to take roads that are closed due to construction.

So I’m thinking that whatever algorithm they use can be fooled by people on snowmobiles and construction workers who happen to carry phones.

7

That’s because Google Maps bases its information on what local road authorities give them. If the local authorities listed the road as open, Google didn’t magically realize it wasn’t.

Last year it drove me crazy for a while that multiple mapping apps would insist in forcing stages I hadn’t included, until I realized that’s the way the French road authority communicates detours: if I went close enough to a closed road, and even if I didn’t actually go to a place which would include it, the detour (the forced stage) got triggered. Compared with the Spanish road authority’s attitude of “what do you mean, we should post some kind of warning when a major route is going to be closed for a month?” it became a net positive once I’d understood what it was (now that I know it, I can search for and remove those stages).

8

You can use your mouse on a pc to grab the google map route and drop it onto an alternative route. Google will update all the directions and recalculate the mileage from point to point.

I’ve never been able to do that with the google maps app on my phone. I can’t grab and drag the route with my finger.

9

I tried it again yesterday and it gave me the shorter (county road) route. Which seems to argue against my theory.

OTOH, I also got some support for my theory as well. Because this time, I turned on the app at an earlier point, while in the parking lot of my office. The app told me to turn right and take a certain major road which is right next to my office. I instead turned left to the (shorter, backroads) route I usually take. The app immediately recalculated the route and shaved a couple of minutes off the estimated time. I don’t see any other explanation other than an initial bias in favor of the major road.

So I’m wondering if the changing recommendation is possibly due to the app recognizing that I’ve historically taken that route? Seems a bit far-fetched but these are mysterious matters …

I’ve had this happen many times. “A traffic incident has been reported in X miles”.

10

Google maps can give you current traffic or do some predictions based on the requested time of day, day of the week. There’s a drop down that defaults to “Leave Now” but can be set to any particular start time or end time.

11

If I’m already on a route, then, yes, I remember it saying something like that. I just don’t remember it saying that when I’m starting a route. It presumably gives me the fastest (or easiest–in the sense that it may be biased towards major roads) route at the time. If while on the route there’s an accident reported then, yes, it’ll chirp up and say something.

12

My experience has been the same. But in this case, I was already on a route. Per the OP “as I got closer to my exit, the app announced that I could save 4 minutes by taking the earlier exit that I had known to be faster anyway”, and my question was what happened to trigger this mid-trip change. I would think had there been an accident, the app would have said so, as it has done in previous circumstances.

(In addition, I don’t think - based on my living in the area and being familiar with these roads - it was at all likely that the initial route chosen by the app was the quicker route even if there were no accident. So I think it’s unlikely that an accident is what triggered the change.)

13

AH, I see. Maybe for whatever reason, it didn’t have the data as to why there was a slowdown, just saw other app users with a slowdown along a certain route (or used local roadway data, or however in the heck they do it these days. I typically use Waze, which is crowdsourced data, as far as I know.)

14

My guess is that they do actually look at the routes, but they have some kind of pruning mechanism to disqualify routes that would be slower. For example, if you’re leaving a metro area, they probably have a mechanism that recognizes that it’s likely to be faster on the interstate than some piddly farm-to-market road leading in the same direction, and shuts down the calculation of every permutation of the farm-to-market road from that point forward.

Waze (not Google maps, but owned by Google anyway), does consider current traffic/road closure information when starting a trip. More than once, driving from between Houston and Dallas, or Austin and Dallas, it’s proposed a different route within the destination city at the beginning of the trip than it actually ends up recommending when we get there. In particular, the Austin ones change a lot if we’re heading there after work- it’ll come up with strange ones during rush hour, but by the time we get there at 9 pm, it just sends us straight down MOPAC.

15

With the unplowed lumber road, I suspect that it’s more just that that road isn’t much used even in good conditions. So Google can see that nobody’s been on it in the past day, but doesn’t find that too remarkable, since it often goes a day between users.

16

Finding optimal paths through flow networks is really not that bad, algorithmically speaking; you shouldn’t have to “prune” anything (other than to satisfy weight constraints, roads only open during certain times of day, etc.) The real problem is to adapt to unpredictable traffic conditions in real time, and to do so accurately. Regular traffic patterns like rush hour should not present any special problems, I mean things like unexpected road closings.

17

Garmin does this too. Even within a ½ hour of home it tries to send me on the longer distance but faster (expressway) route. When I ignore it & go my way it eventually recalculates to faster.

The annoying thing is that for a couple of minutes/miles it keeps trying to take you that way so it directs me to turn off at the next road to go back to the way it originally wanted me to go, which is now even longer. It has rerouted me, but it’s stubborn in holding onto it’s original plan.

18

It might be that Google’s algorithm has a sense of communication to it: It knows that there are two different routes, and that there are reasons why either one might be preferred (such as shorter distance vs. quicker). But it doesn’t, at first, know which one you prefer. So at the start, it gives you the one that it thinks the majority would prefer, but then when you turn onto the other route, it takes that as a signal of which one you prefer, and then continues to route you that way.

19

I have an old Garmin GPS that definitely has a settings option of fastest or shortest. In your situation of wanting to switch over mid-way I would have to manually change the setting mid-route, though.

20

For a trip to Oregon to New York, it does not need to look at all possible combinations, unless you want the shortest route, and then it will, I assume, do a buffer search of available roads for the shortest route as it starts working out a path. It should know that backtracking 20 miles is not a great idea unless it gets boxed in on the route.

Not looking at traffic, the fastest route would be easier to calculate.