GPS, Waze: how do their algorithms work?

Working in IT development often leads to an interest in the functioning of the tools that we can use on a daily basis. This was the case on the road recently, with Waze launched, wondering how the GPS guidance algorithms could work. Because when you think about it, going from point A to point B, with the multitude of possible routes, it can make you a bit dizzy to know which one to choose. Especially when you add the constraints related to traffic conditions that can change quickly.

The idea in this article is not to tell you precisely how GPS or Waze algorithms work, because they are proprietary. However, there have long been a number of algorithms that must play their part in the “recipe” for arriving at the best route.

When you think about it in a simple way, to find a route, you have to:

up-to-date cartography, to take into account the latest changes (new roads, change in direction of traffic, etc.)
calculate the best route between two points. Under standard conditions, and also take into account traffic events (traffic jams, accidents, exceptional closures, etc.)

GPS, Waze: have up-to-date cartography

There are several possibilities for having an up-to-date cartography. This can go through mapping services, or through communities that maintain an up-to-date map. For example, on Waze you can submit map changes .

We cannot know how the algorithms of Waze or other GPS work in detail. But one can also imagine that the algorithm makes it possible to deduce cartographic information. For example, if a car passes through a place where no road is known, a question may arise. If a lot of cars pass by there, we can probably deduce at some point the presence of a road. This may also be true for traffic directions. A lane in the wrong direction but which is taken by many vehicles over several days can make it possible to deduce a change (even temporary for works for example).

This can also cause some problems in some cases. I remember once driving on the Ile de Ré, and Waze sent me on a small road because the main road was jammed. However, it was prohibited except for agricultural vehicles. We can imagine that he proposed it because a certain number of cars borrowed it.

GPS, Waze: find the best route

Now that we have an up-to-date map, we need to determine the best route. And this is where things get tricky. Because imagine from point A to point B the possibilities of itineraries, with the number of options growing exponentially with distance.

Graph Theory

The first key is to think of a map as a graph , with vertices and edges. The vertices are intersections, and the edges are the roads connecting these intersections.

Once the graph has been represented, there are two possibilities for traversing it:

For the calculation of the route, it will be the course in width which will be privileged.

As for the application of these algorithms to development, I recommend that you look at this article on the blog “I am a dev”.

Dijkstra’s algorithm

We know how to traverse a graph, now the idea is to do it in the most optimal way possible. To respond quickly and avoid using too many computational resources unnecessarily. This is what Dijkstra’s algorithm for calculating the shortest path, which was published in 1959, proposes to do.

I offer you two explanatory videos on the subject, which will be worth more than a long speech to understand the principle:

The A* algorithm

Always with the idea of optimizing the calculations as much as possible, other algorithms exist. This is the case of the A* algorithm . The idea is to add heuristic criteria to the search , ie criteria allowing a problem to be solved quickly, perhaps not necessarily in the most optimal way. This means that in many cases he will be more optimal than Dijkstra. But in some more specific cases not. A possible heuristic criterion in the context of the route search is the distance as the crow flies.

In the context of A*, the option is to take into account the previous cost, the future cost and the distance as the crow flies to guide the choices. The idea being to say that the closer you get to the objective, the better the decision.

I recommend this video (in English but easy to understand) to clarify all this

GPS, Waze: Calculate travel time

We saw in the previous paragraph that to find the best route, several algorithms were possible. But all of them follow graph theory. Namely, from point A, go through ridges to reach other peaks and finally point B.

We then understand that the travel time can be associated with an edge. Via an attribute indicating the time it takes to browse the latter. Indeed, it is easy to imagine that the edges can carry a certain amount of useful information:

distance
time to go through it
possibly toll rate
…

The next question is how to determine this time?

Again, several options are possible. This may be a theoretical time if we do not have more information. If, on the other hand, we have data related to the use of the software, we can be more precise. This is what Waze does, when you use the software it takes the opportunity to recover data. In particular knowing what is the speed on an edge, how long it takes to cross it. The outlying values (driver much faster or much slower than the others) are set aside, as is often the case in statistical studies.

This information is then used for two things:

short-term use to be able to give motorists behind up-to-date information on journey times. Also note the possibility via the application to report events (accidents, slowdowns, stopped vehicle, etc.).
a longer term use to have statistical data on the edge in question. This will allow for example to make averages according to days and hours. And to determine even in advance an approximate time by driving on such a day at such a time.

I have also seen on a recent journey the use of these statistical times on journey times. I arrived on a Tuesday late afternoon in the Paris region during the Christmas holidays. No traffic jam was announced, but I think he took into account the traffic conditions on a usual late Tuesday afternoon (excluding holidays). Because he overestimated the ETA (estimated time of arrival) by anticipating traffic jams.

You can also see the traffic in real time, and also calculate an estimated travel time per hour on https://www.waze.com/livemap