Tech

Does Google Maps always show us the best route while navigating?

Apal Shah

23 Nov 2019 • 4 min read

This thought randomly came to my mind when I was going to a place with my friends in a car, and 3 of us started to navigate. I noticed that all of us got slightly different routes and all of them had a little variation in time. Before that, I used to believe that Maps always shows us the best route, but then I realized I never thought how Google Maps work.

I'm not going to talk about all the features of Google Maps in this post. This blog is focused on how difficult the algorithm to find one of the best routes between two places is and whether we're always getting the best route in Google Maps.

Edit 1: I got a few responses saying Google Maps is showing us different routes so that they can gather more data and make their algorithm more powerful or simply avoid the traffic. But if that is true, isn't it scary that they're controlling our traffic?

What I found How Google Maps work

After doing some research, I found that the algorithm behind this is way too complex than I expected. I couldn't find any definite answer on which algorithm is being used by Maps currently but I found some old resources that I've included in this post, which might be useful.

Let's first simplify this

And we'll gradually add complexities. Let's assume that all the roads and locations are part of a Graph(data structure). All the intersections of the roads are the vertices/nodes, and the roads that connect these vertices are the edges of that graph.

Now to reach from one point to another, we can apply any simple algorithm like Dijkstra's shortest path algorithm. But using this algorithm, we can only find the shortest path which wouldn't necessarily be the path that can take us to the destination in the least amount of time without compromising on the length of the path (But there are some solutions if both of them are somewhat dependant on each other). For that, we need a little advanced algorithm.

If we use a bit different (and faster) algorithm like A* algorithm, it can handle this issue and give us a path quickly using greedy approach (We can easily tweak the cost function to use multiple costs by converting all the costs in one but that's out of the scope for now). But one of the cons of this algorithm is, it doesn't guarantee that the output of this algorithm is always the best solution if we don't use admissible heuristic function. To justify this, I've created a demo (in the implementation section).

Nowadays, almost everyone knows that Google Maps use our smartphones to calculate traffic and ETA. So another problem is that Maps has to predict the traffic when we reach on a particular road. Also, it has to check if any road is closed at that time.

Google Maps also gives us different routes and ETAs for a car, motorcycle, etc. We can choose to avoid toll taxes, highways, etc. Also, I've seen the option of different timezones if we're traveling to a different place that has a different timezone. There can be hundreds of different things which we don't know are being done and Maps is calculating all of them on the fly, for all the users, for any place. So you can assume that how difficult is this for any algorithm to find the best route within a few seconds, for everyone.

You can also check this answer on Quora to get more idea on the other features of Google Maps.

Let's see the implementation

Now after finding all these things, I decided to implement a simple greedy solution using the A* algorithm. You can see that, this is trying to find one of the best routes but if you run this multiple times, you'll notice that the path is not always optimal (Again, this code is using greedy approach and not any kind of admissible heuristic function).

In this code, the journey starts from the top left corner and ends at the bottom right corner. It will print Impossible! if the destination is not reachable after traversing through all the possible paths.

Hit return at the bottom right corner to restart this.

Code Credits: https://rosettacode.org/wiki/A*_search_algorithm

Conclusion

We can compare this problem with the renowned traveling salesman problem, where it gets more difficult to find the best route if we add more nodes (places) on the graph. And after a point of time it becomes impossible for any algorithm to find the best route in the limited period of time given the resources are limited. Similar to this, in Maps, it is trying its best to find one of the best routes but I believe that there will always be the room for improvement in the algorithm.

Footnotes

I've tried my best to do all the research on these algorithms and still if you find any problem, error/correction or any other thing, please let me know. I would really love to know your thoughts on this. And if you like this blogs and don't want to miss any blog in future, please subscribe to this blog using the form below.