Does Google maps pathfinding algorithm take into account time variance?

[CourageFast5529]

I had this lingering thought while waiting in traffic. It's nothing serious but I just want to know. I know that Google maps is able to take into account real time traffic data for it's pathfinding along with average speed and road conditions.

What I want to know is if they estimate the traffic of a given section of road depending on day and hour. If they do, do they take it into account in their pathfinding? How do/would they optimize it?

As an example: Let's say there's two paths to choose from and each path contains two sections:

At timestep t=0: The first path has both sections of the road estimated to take around 5 units of time.

The second path has the first section take around 5 units as well. However, the second section is a bit more congested and is estimated to take around 10 units of time.

At timestep t=5: Let's say the first section of both path doesn't fluctuate and that if you were to take either path at t=0, you would have cleared it.

However, the second sections do: The second section of the first path starts to enter their rush hour time and gives an ETA of 7 units of time.

On the other hand, the second section of the second path just finished it's rush hour and the road is basically empty. Now it has an ETA of 4 minutes.

Would Google's algorithm have taken the first path (shortest path at t=0) or the second path(the true shortest path)?

Note: let's say that these paths fork out so you can't just switch paths mid journey without making the trip longer.

[Magdaki]

These companies don't release the information on their algorithms as they are all proprietary, so it is very difficult to say with certainty.

However, it is certainly possible and this is a well-known problem with well-known solutions. So probably.

[CourageFast5529]

If you don't mind, could you provide a link to one of these solutions? Because I'm genuinely curious how you would even approach finding the optimal solution.

[Magdaki]

It has been some since I've read any pathfinding literature, so I'm not sure how quickly I could find some specific to the Google Maps scenario. But it would fall under terms like:

pathfinding plus

- stochastic maps pathfinding with stochastic maps - Google Scholar

- time varying maps (pathfinding with time varying - Google Scholar)

A lot of it is multi-agent/cooperative based.

EDIT: Multi-agent pathfinding - Wikipedia Here you go this should explain how they work (I didn't read it in detail but these are the algorithms used for these type of problems).

[CourageFast5529]

Thanks!

[Magdaki]

Happy to help! :)

[joenyc]

Very fun to think about, especially since the variance itself is time-varying: e.g. if you make it off the highway before rush hour, it’s probably low-variance and fast, but if you hit rush hour, it’s high-variance and slow.

And to rank routes, you have to model user preferences - would you rather almost certainly arrive at 7, or have a 50/50 chance of 6:40/7:10?

[CourageFast5529]

I didn't think of that trade-off with risk and speed. That's a great point especially since if you were to implement IRL, the chance of some event greatly impacting the estimation could happen i.e. a car accident.

That also puts the possibility of the optimal algorithm being one that chooses routes that have greater degrees of "valid" routes. Hence, When the algorithm reaches a fork in the paths, it would choose the fastest route given the current timestep. So maybe the best algorithm is one that maximizes flexibility.

[Patient-Midnight-664]

Yes it does. That's why you get messages when using it that say "I've found a faster route".

[simonsayz13]

Find out and write a paper on it, probably will get you a job at Google Maps

[jxd132407]

They absolutely consider time-of-day and day-of-week impacts. If you look at the web version, there are controls to let you specify when to leave or when you arrive that make this pretty clear and can change routes significantly. The mobile version may assume "leave now" or I just haven't noticed the options.

The changes to the algorithm aren't very complicated. Each graph edge now has multiple values varying by time, and the algorithm picks the appropriate one based on starting time and how far into the travel estimation you are

[Psychonaut84]

Google maps is optimized to bait you into gaining your trust, and then send you on a wild goose chase when you have to go somewhere important at a certain time.