The history of routing in the project MAPS.ME

Laying routes from one point to another has become a mandatory function for electronic maps, even if they are not used as a navigator. In this article I will tell the story of creating a routing in the project MAPS.ME: what stages we went through and what we learned during this time.

Routing history MAPS.ME

First attempts

Routing was originally developed as an additional feature to an already finished application. At the time of the beginning of the development of routes, maps were already released, and the first users took our application with them on a trip. The project team gained experience in drawing, storing and processing OSM data. Therefore, after researching the subject area, the team implemented classical algorithms on data for drawing maps. For the first attempt was chosen algorithm Dijkstra . This is a well-known algorithm that can find the shortest route in any road graph with non-negative rides. However, the first tests showed that the algorithm is slow even on the developers' computers. On the transfer to the phone could not be considered. To speed up the search for a route, Dijkstra’s algorithm was replaced by A * . The program began to work significantly faster, but still too slow.

Nevertheless, the experience of implemented algorithms allowed us to formulate the main problems we encountered:

Resource Limit. We run the routing on mobile phones, so we can not rely either on a fast processor, or on a large amount of RAM, or on fast reading from disks.
The graphic nature of OSM. We do not have a graph of roads, but there is a map created for drawing. And since banding, turning restrictions, speed limits and other road tags are not drawn on the map, they are filled much worse than the roads.
Traffic Laws. They significantly complicate the graph of roads compared to a flat graph, which is drawn on the screen. The program has to take into account additional restrictions: prohibitions of turns, multi-level interchanges, the inability to turn around on the spot.

Working solution

Sowing for books and scientific articles, we began to look for an algorithm that would solve the performance problems of routing on mobile devices. And at this time the contraction hierarchies algorithm was found (hereinafter, I will call it simply CH). Compared with the classic Dijkstra algorithm, CH gives an incredible performance boost, but he needs a specially processed graph of roads. This algorithm is based on pre-calculating the edges of the graph to accelerate the construction of the route. We plan to describe CH in more detail in a separate article.
')
After selecting the algorithm, we are faced with the fact that good drawing data and good routing data are not the same thing. In addition, due to the nature of OSM, getting a good graph of roads is quite difficult, and therefore we decided to use a ready-made open source project OSRM (open source routing machine). OSRM at the stage of data preparation processes the OSM map, creating a road graph on which you can create routes. Thus, it is possible to get road graphs for automobile, cycling, pedestrian and any other routing. However, OSRM has one significant drawback: it is designed for use on servers, and stores all the information used in its large intermediate files. But most of the information of these files we already have on the phone in the map file, and to avoid duplication, we have to repack them. In addition, OSRM itself is a multi-threaded http daemon and is not designed to run on mobile devices.

But thanks to the well-thought-out architecture, OSRM has the ability to separately use the CH algorithm and provide the repacked data through a simple interface. Thus, using the backlog of OSRM, MAPS.ME received its first routing and .routing files that must be downloaded in order to create routes.

International routing

We cut the world map into separate areas to reduce the amount of data for downloading and storing on the phone. Moreover, the better the terrain is mapped, the more the graph of the roads takes, and the smaller the pieces into which the map has to be cut. As a result, for example, the map of Germany broke down by province. The CH algorithm paves the routes within each such area. The likelihood of routing between multiple maps increased with each new addition to OSM, and it was time to develop routing between maps. When choosing a solution for multi-card routing, we chose those that do not require a large amount of additional data. As a result, we have such an architecture: the graph of each of the maps has N roads, which are its inputs and outputs. We can also calculate distances between them to speed up the search for a route between maps. The result is a certain caption for traveling between map files. In this journey, we do not need the files of all the maps of the world, and only adjacent ones will suffice. Moreover: we can have different versions of these files. If one card has time to upgrade, and the second is not, then the program will still pave the route. In the spring, we released this version of laying routes.

Hiking trails

But you always want more! And we wanted to add new types of routing. We started with a pedestrian. When we decided how pedestrian routing would be, we proceeded from the prerequisites:

Pedestrian navigation should not take up additional space, comparable to the automobile graph, but should make the most of the existing data;
pedestrians do not need the distances that are needed by car routes;
pedestrian graph is easier from the point of view of logic: there are no forbidden maneuvers and one-way roads.

As a result, we decided to go back to where we started, and get from under the cloth the old implementation of the A * algorithm, which worked with a graphical representation of traffic data. And during the week of the hackathon a team of four people was busy with this problem. As a result, we were able to make a pedestrian routing algorithm, which was presented in the new update of the MAPS.ME program. Moreover, by optimizing and debugging the algorithm of two-way A *, we were able to apply it in the routing between the cards, which accelerated the construction of intercity routes.

Option 1. A simple unidirectional Dijkstra algorithm. The dots show every tenth edge that was searched for the route.

Option 2. Bidirectional algorithm A *. The dots show every tenth edge that was searched for the route.

We have almost completed our pedestrian navigation, and soon you will be able to see it on your smartphones.

findings

What did the history of developing routing for our application teach us? The first thing I want to note: do not throw out the code . We were greatly helped by the fact that the previous versions of the routing algorithms were in the gita. They survived when the repository was moved, for which forces were once spent. Even despite the fact that they are bogged down in history and lagged behind the master branch, they were quickly restored, adapted to the existing interfaces and used to solve the problem. Search and read materials on the topic. Modern routing algorithms have gone far ahead, and academic work on optimizing their work is published monthly. Re-inventing the CH level algorithm is incredibly difficult. Use external libraries whenever possible and have confidence in their quality. OSRM allowed us not to write an OSM card from scratch and use the already debugged code of the complex CH algorithm.