Ten to 15 years ago, every driver’s glovebox contained a road atlas – an indispensible guide for planning driving routes. Now, instead of road atlas books, drivers rely more on electronic maps and mobile applications – and, inadvertently, on smart algorithms, which do the hard work figuring out the best routes. Yandex helps people plan journeys with the maps.yandex.ru service, as well as with the Yandex.Navigator and Yandex.Maps mobile apps. The technology for plotting routes currently used in all mapping or navigation products all over the world is the same everywhere; the only thing that differs is the interface.
The main components of Yandex’s route constructor are the road graph and the algorithm that figures out the best route.
What is a road graph?
A road graph represents a network of roads. It consists of numerous interconnected fragments. For example, the road graph for the city of Saratov (population 840,000) consists of 7,592 fragments. Each contains information about its section of the road network: geographical coordinates, traffic direction, average speeds in the segment, and other parameters. Every fragment also contains data about how it connects with the neighbouring sections. A driver might need to know whether the road ahead has left or right turnoffs, U-turn possibilities, or a strictly one-way direction.
Of course, a road graph can't be completed once and for all. Urban transport systems have a habit of changing. New roads and interchanges appear, the direction of traffic changes. Where yesterday there was a turnoff, tomorrow there might be a “no entry” sign. To keep up with real conditions, Yandex regularly updates its data.
Users help us with this task, too. They notify us of inaccuracies with the help of mobile Yandex.Maps, Yandex.Navigator and the Yandex.Maps web service. Yandex experts are constantly working with these notifications, as well as with information from other open sources such as local administration websites.
Also, we have a special system to identify inaccuracies on the road graph. This system registers incidents when a vehicle’s movement (the information about which is anonymously and automatically provided to us by drivers) doesn’t match our road network information. If it’s not a one-off case in which a rogue driver strays onto the verge or takes an illegal turn, then it’s possible that the traffic scheme has changed. All such cases are analysed, and then changes are made to the road graph.
Several copies of the road graph are stored in Yandex’s servers, so that even if one is temporarily unavailable, the route constructor will still work.
How routes are constructed
Routes are constructed according to Dijkstra's algorithm. With its help, the system calculates the fastest route, based on the length of each section and the speed of movement along it. If a user chooses to construct a route without accounting for traffic jams, the algorithm uses the average speed in each segment. And if the user wants to know how to get somewhere fastest, taking the traffic situation into account, then the algorithm uses data about current traffic conditions.
How it works can be illustrated with an example. Imagine that you need a route from point A to point B. The algorithm starts to methodically identify all possible routes. First it plots just one step (or graph fragment) in all directions from point A. Then it calculates how long it would take to travel the length of each route segment (easily done by dividing distance by speed). After that, it chooses the point that can be reached fastest – let’s call it C.
Having identified the point C – the algorithm then works on the next step of the route, analysing all directions from this point.
The point reached fastest becomes D – and the next stage of the route is plotted from here. And so the algorithm continues working in this way until it finds the fastest of all possible route options to reach the final destination.
Courtyards are a special issue. As you may be aware, it’s forbidden to use them as thoroughfares. Besides that, a winding path through courtyards often takes longer than a direct route. To make sure the service doesn’t construct routes through courtyards, the algorithm adds extra penalty minutes for passage through them. This doesn’t affect the journey time that the user sees, however. Once the fastest route has been determined, the time of routes through courtyards is recalculated without adding the penalty minutes. In most cases, the algorithm chooses other routes – they’re faster. But if the final destination is in a courtyard, naturally the algorithm has to “drive in”.
Routes are constructed very quickly. In the time it took you to read a few sentences of this article, the service could have laid a spider web of routes criss-crossing entire Russia. To achieve such speed, the system automatically divides the entire map into a multitude of areas, and calculates the optimal routes for crossing each one. Such an area might be, for example, a small town intersected by just one intercity highway that is the only option for driving into or out of the town. For such cases, Yandex would have a pre-calculated optimal route.
If there are several such areas in a user’s journey, Yandex simply joins together these ready fragments to construct the route.
Yandex plots all possible variations for driving through and between all areas in advance, every time the road graph is updated. Then, when a user asks the service to construct a route, the ready-made route is simply fetched from memory. Of course, this only works when the user requests a route without accounting for current traffic conditions, since the routes constructed in advance are based on average speeds. If the user wants to construct a route taking current traffic conditions into consideration – and if there are traffic jams in the area at that time – Yandex constructs a route for the user from scratch.