Прокладка маршрутов из одной точки в другую стала обязательной функцией для электронных карт, даже если они не используются как навигатор. В этой статье я расскажу историю создания роутинга в проекте MAPS.ME: какие этапы мы прошли и чему научились за это время.

История роутинга MAPS.ME

Первые попытки

Роутинг изначально разрабатывался как дополнительная фича к уже готовому приложению. На момент начала разработки маршрутов карты уже были выпущены, и первые пользователи брали с собой в поездку наше приложение. Команда проекта набрала опыт по рисованию, хранению и обработке OSM-данных. Поэтому после исследования предметной области команда реализовала классические алгоритмы на данных для рисования карт. Для первой попытки был выбран алгоритм Дейкстры. Это широко известный алгоритм, который может находить кратчайший маршрут в любом дорожном графе с неотрицательными стоимостями проезда по рёбрам. Однако уже первые тесты показали, что алгоритм работает медленно даже на компьютерах разработчиков. О переносе на телефон не могло быть и речи. Чтобы ускорить поиск маршрута, алгоритм Дейкстры был заменён алгоритмом А*. Программа стала работать ощутимо быстрее, но всё равно слишком медленно.

И всё же опыт реализованных алгоритмов позволил сформулировать основные проблемы, с которыми мы столкнулись:

1. Ограничение по ресурсам. Мы запускаем роутинг на мобильниках, поэтому не можем полагаться ни на быстрый процессор, ни на большое количество оперативной памяти, ни на быстрое чтение с дисков.
2. Графический характер OSM. У нас нет графа дорог, но есть созданная для рисования карта. А так как полосность, ограничения поворотов, ограничение скорости и прочие дорожные теги не рисуются на карте, то и заполнены они гораздо хуже чем дороги.
3. Правила дорожного движения. Они значительно усложняют граф дорог по сравнению с плоским графом, который рисуется на экране. Программе приходится учитывать дополнительные ограничения: запреты поворотов, многоуровневые развязки, невозможность развернуться на месте.

Рабочее решение

Засев за книги и научные статьи, мы начали искать алгоритм, который позволил бы решить проблемы производительности роутинга на мобильных устройствах. И в это время был найден алгоритм contraction hierarchies (далее я буду называть его просто CH). По сравнению с классическим алгоритмом Дейкстры, CH даёт невероятный прирост производительности, но ему нужен специально обработанный граф дорог. Этот алгоритм основан на предрасчёте рёбер графа для ускорения построения маршрута. Мы планируем описать CH более подробно в отдельной статье.

После выбора алгоритма мы столкнулись с тем, что хорошие данные для рисования и хорошие данные для маршрутизации — это не одно и то же. Кроме того, из-за особенностей OSM получить хороший граф дорог довольно сложно, и поэтому мы решили использовать готовый проект с открытым исходным кодом OSRM (open source routing machine). OSRM на этапе подготовки данных обрабатывает OSM карту, создавая дорожный граф, на котором можно прокладывать маршруты. Таким образом, можно получить дорожные графы для автомобильного, велосипедного, пешеходного и любого другого роутинга. Однако у OSRM остаётся один весомый недостаток: он рассчитан на использование на серверах, и всю используемую информацию хранит в своих больших промежуточных файлах. Но большая часть информации этих файлов у нас уже есть на телефоне в файле карт, и, чтобы избежать дублирования, приходится их перепаковывать. Кроме того, сам OSRM представляет собой многопоточный http-демон и не предназначен для запуска на мобильных устройствах.

Но благодаря продуманности архитектуры, в OSRM есть возможность отдельно использовать алгоритм CH и через простой интерфейс предоставить ему переупакованные данные. Таким образом, используя задел OSRM, MAPS.ME получила свой первый роутинг и файлы .routing, которые необходимо скачать, чтобы прокладывать маршруты.

Международный роутинг

Мы разрезали карту мира на отдельные области, чтобы сократить количество данных для закачки и хранения на телефоне. Причём чем лучше картирована местность, тем больше занимает граф дорог, и тем меньше куски, на которые приходится нарезать карту. В результате, например, карта Германии разбилась по провинциям. Алгоритм CH прокладывает маршруты внутри каждой такой области. Вероятность прокладки маршрутов между несколькими картами возрастала с каждым новым добавлением в OSM, и настало время разрабатывать роутинг между картами. При выборе решения для маршрутизации по нескольким картам мы выбирали те, которые не потребуют большого количества дополнительных данных. В итоге у нас получилась такая архитектура: граф каждой из карт имеет N дорог, которые являются её входами и выходами. Также мы можем рассчитать расстояния между ними, чтобы ускорить поиск маршрута между картами. В итоге получается некоторый надграф по путешествиям между файлами карт. При таком путешествии нам совсем не нужны файлы всех карт мира, а хватит только смежных. Более того: мы можем иметь различные версии этих файлов. Если одна карта успеет обновиться, а вторая нет, то программа всё равно проложит маршрут. Весной мы выпустили эту версию прокладки маршрутов.

Пешеходные маршруты

Но всегда хочется большего! И нам захотелось добавить новые виды роутинга. Мы начали с пешеходного. Когда мы решали, каким будет пешеходный роутинг, мы исходили из предпосылок:

• пешеходная навигация не должна занимать дополнительное место, сравнимое с автомобильным графом, а должна максимально использовать уже имеющиеся данные;
• пешеходам не нужны такие расстояния, которые нужны автомобильным маршрутам;
• пешеходный граф легче с точки зрения логики: там нет запрещённых манёвров и односторонних дорог.

В результате мы решили вернуться к тому, с чего начинали, и достать из-под сукна старую реализацию алгоритма А*, который работал с графическим представлением дорожных данных. И вот в течение недели хакатона команда из четырех человек была занята этой проблемой. В результате мы смогли сделать алгоритм пешеходного роутинга, который представили в новом обновлении программы MAPS.ME. Более того, оптимизировав и отладив алгоритм двухстороннего А*, мы смогли применить его в роутинге между картами, что ускорило постройку междугородних маршрутов.

Вариант 1. Простой однонаправленный алгоритм Дейкстры. Точками показано каждое десятое просмотренное при поиске маршрута ребро.



Вариант 2. Двунаправленный алгоритм А*. Точками показано каждое десятое просмотренное при поиске маршрута ребро.



Мы уже почти доделали нашу пешеходную навигацию, и скоро вы сможете увидеть её на своих смартфонах.

Выводы

Чему научила нас история с разработкой роутинга для нашего приложения? Первое, что хочется отметить: не выкидывать код. Нам очень помогло то, что в гите лежали прошлые версии алгоритмов роутинга. Они сохранились при переезде репозитория, на что в своё время были потрачены силы. Даже несмотря на то, что они увязли в истории и отстали от мастер-ветки, их получилось быстро восстановить, адаптировать к имеющимся интерфейсам и использовать для решения задачи. Искать и читать материалы по теме. Современные алгоритмы роутинга ушли далеко вперёд, а академические работы по оптимизации их работы выходят ежемесячно. Заново изобрести алгоритм уровня CH невероятно сложно. Использовать внешние библиотеки, когда это возможно и есть уверенность в их качестве. OSRM позволил нам не писать с нуля разбор OSM-карты и использовать уже отлаженный код сложного алгоритма CH.

Список литературы

Для интересующихся приведу несколько интересных работ, которые помогли нам разобраться в современных алгоритмах построения маршрутов:

1. Route Planning in Transportation Networks MSR-TR-2014-4. Сравнительный обзор от MS современных алгоритмов прокладки маршрутов.
2. Route Planning in Road Networks. Dominik Schultes. Диссертация по алгоритмам роутинга. Подробное описание принципов большинства современных алгоритмов
3. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. Robert Geisberger. Дипломная работа, полностью посвящённая алгоритмам Contraction Hierarchies.