Yesterday, we announced a massive update to Yandex.Maps – detailed schemes of most countries of the world appeared on them. Behind this project is not just mapping new objects to the map, but above all the technological basis that allows you to store, quickly process and update this data. There are a lot of interesting technologies in Yandex.Maps, and today we want to talk about one of them – route building technology.
Ten to fifteen years ago, in the glove compartment of each driver lay an atlas of roads. He was the main assistant in planning the route. Now, instead of the atlas, people are increasingly opening electronic maps and mobile applications. And smart algorithms themselves build the best route for a person. Yandex helps people plan trips on the maps service. , in the mobile applications Navigator and Yandex.Maps. The technology for constructing a route is the same everywhere, only the interfaces differ.
The main components of routing are the road graph and the algorithm that calculates the route.
What is a graph?
A road graph is a grid of roads. It consists of many fragments that are joined together. For example, the road graph of the city of Saratov (population – about 840 thousand people) consists of 7592 fragments. Each of them carries information about its section of the road: geographical coordinates, direction of movement, average speed with which cars usually travel on this section, and other parameters. Each fragment also contains data on how it fits into neighboring sections – is there a right or left turn, is it possible to turn there in the opposite direction or is it allowed to go only straight.
Of course, a road graph cannot be made once and for all. The transport system of the city tends to change. New roads and interchanges appear, the direction of movement is changing. And where there was a turn just recently, a “brick” can hang. In order to keep up with life, Yandex regularly updates data.
Firstly, messages about inaccuracies in the graph that users send using mobile Yandex.Maps, Navigator and the Yandex.Maps web service are constantly being processed. Yandex experts work with these messages, who also use open sources of information about the transport system (for example, sites of local administrations).