July 10, 2015 at 14:15The history of routing in the MAPS.ME project
Routing from one point to another has become a must-have feature for electronic maps, even if they are not used as a navigator. In this article I will tell the story of the creation of routing in the MAPS.ME project: what stages we went through and what we learned during this time.
The history of routing MAPS.ME
First attempts
Routing was originally developed as an additional feature to an already finished application. At the time the route development began, maps were already issued, and the first users took our app 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, Dijkstra's algorithm was chosen . This is a well-known algorithm that can find the shortest route in any road graph with non-negative ribs. However, the first tests showed that the algorithm works slowly even on the computers of developers. There was no question of transferring to a telephone. To speed up the route search, Dijkstra's algorithm has been replacedAlgorithm A * . The program began to work significantly faster, but still too slow.
Nevertheless, the experience of the implemented algorithms made it possible to formulate the main problems that we encountered:
- Resource limit. We run routing on mobile phones, so we can not rely on a fast processor, nor on a large amount of RAM, nor on fast reading from disks.
- The graphic nature of OSM. We do not have a road graph, but we have a map created for drawing. And since lane, cornering restrictions, speed limits and other road tags are not drawn on the map, they are filled much worse than roads.
- Traffic Laws. They greatly complicate the road graph compared to the flat graph that is drawn on the screen. The program has to take into account additional restrictions: prohibitions of turns, multi-level interchanges, inability to turn around on the spot.
Working solution
Hoping for books and scientific articles, we began to look for an algorithm that would solve the problems of routing performance on mobile devices. And at that time, the contraction hierarchies algorithm was found (hereinafter I will call it simply CH). Compared to Dijkstra's classic algorithm, CH provides an incredible performance boost, but it needs a specially crafted road graph. This algorithm is based on precalculation of the edges of the graph to speed up route construction. We plan to describe CH in more detail in a separate article.
After choosing an algorithm, we were faced with the fact that good data for drawing and good data for routing are not the same thing. In addition, due to the features of OSM, getting a good road graph is quite difficult, and so we decided to use the finished open source OSRM project(open source routing machine). OSRM at the stage of data preparation processes the OSM map, creating a road graph on which you can plot routes. Thus, you can get road graphs for car, bicycle, pedestrian and any other routing. However, OSRM still 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 in order 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 repackaged data through a simple interface. Thus, using the OSRM backlog, MAPS.ME got its first routing and .routing files, which must be downloaded in order to get directions.
International routing
We cut the world map into separate areas in order to reduce the amount of data for downloading and storage on the phone. Moreover, the better the terrain is mapped, the more the graph of roads occupies, and the less pieces that you have to cut the map into. As a result, for example, the map of Germany was divided into provinces. The CH algorithm draws 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 routing across several cards, we selected those that do not require a large amount of additional data. As a result, we got such an architecture: the graph of each of the maps has N roads, which are its inputs and outputs. We can also calculate the distance between them, to speed up the route search between maps. The result is some travel overgraph between map files. With such a journey, we do not need files of all world maps, but only adjacent ones will suffice. Moreover: we can have different versions of these files. If one card manages to be updated, but the second does not, then the program will still get directions. In the spring we released this version of the route planning.
Hiking trails
But you always want more! And we wanted to add new types of routing. We started by walking. When we decided what pedestrian routing would be, we proceeded from the premises:
- pedestrian navigation should not take up additional space comparable to a car graph, but should make maximum use of existing data;
- pedestrians do not need the distances that automobile routes need;
- a pedestrian graph is easier in terms of logic: there are no forbidden maneuvers and one-way roads.
As a result, we decided to return to where we started and get out of the cloth the old implementation of the A * algorithm, which worked with a graphical representation of road data. And during the hackathon week, a team of four was occupied with this problem. As a result, we were able to make a pedestrian routing algorithm, which was presented in the new MAPS.ME update. Moreover, having optimized and debugged the two-way A * algorithm, we were able to use it in routing between cards, which accelerated the construction of long-distance routes.
Option 1. A simple unidirectional Dijkstra algorithm. Dots show every tenth rib seen when searching for a route.
Option 2. Bidirectional algorithm A *. Dots show every tenth rib seen when searching for a route.
We have almost completed our pedestrian navigation, and soon you can see it on your smartphones.
conclusions
What did the history of developing routing for our application teach us? The first thing I want to note: do not throw the code . It helped us a lot that the previous versions of the routing algorithms were in the gita. They survived when the repository moved, which at one time wasted energy. Even though they were bogged down in history and lagged behind the master branch, they managed to be quickly restored, adapted to existing interfaces and used to solve the problem. Search and read related materials. Modern routing algorithms have gone far ahead, and academic work on optimizing their work is published monthly. Reinventing the CH level algorithm is incredibly difficult. Use external librarieswhen possible and there is confidence in their quality. OSRM allowed us not to write an OSM card parsing from scratch and use the already debugged code of the complex CH algorithm.
List of references
For those interested, I’ll give you some interesting works that helped us understand modern routing algorithms:
- Route Planning in Transportation Networks MSR-TR-2014-4 . Comparative review from MS of modern routing algorithms.
- Route Planning in Road Networks. Dominik Schultes . Thesis on routing algorithms. A detailed description of the principles of most modern algorithms
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. Robert Geisberger . Graduation work entirely devoted to Contraction Hierarchies algorithms.
