История роутинга в проекте MAPS.ME



    Прокладка маршрутов из одной точки в другую стала обязательной функцией для электронных карт, даже если они не используются как навигатор. В этой статье я расскажу историю создания роутинга в проекте 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.

    Mail.ru Group
    1,140.58
    Building the Internet
    Share post

    Similar posts

    Comments 37

      0
      и скоро вы сможете увидеть её на своих смартфонах
      Ну, а кому интересно иметь навигацию для пешеходов, машин и транспорта прямо сейчас, советую обратить внимание на HERE maps.

      Скриншот тут

        0
        коллега, судя по положению :D
          0
          Нас тут немало, судя по всему…
          +1
          работает офлайн?
            0
            да
            0
            Вот в Берлине оно более менее нормально и работает.
            Хотя возможные способы доехать все равно бывает пропадают, линии наземного транспорта отрисованы похабно, плохой полнотекстовый поиск (+ нет часов работы предприятий) и не всегда удается быстро сориентироваться если нужно не куда-то конкретно, а понять положение дел с транспортом в общем.
              0
              Попробовал: у MAPS.ME маршрут как я сам и хожу. У HERE длинный и по проезжей части
              Скриншоты



              P.S. Я работают в MAPS.ME
              0
              С масштабами отображения карты еще бы разобрались, а то временами наблюдать чистое поле задалбывает.
                0
                Когда я прокладываю маршрут — стрелка моего положение двигается нормально — достаточно точно, но вот когда стрелка заходит за видимую область «то есть за экран» — приходится руками двигать карту что бы увидеть куда ехать.
                Когда будет функция автоматического смещения карты?
                А то в дороге не хочется отвлекаться от руля на карты.
                  0
                  После прокладки маршрута Вы нажимаете кнопку «Go»? После нажатия кнопки «Go» двигаете ли карту руками?
                    0
                    Да после того как нажимаю GO, карта не двигается сама. Приходится ручками.
                  0
                  aik а что Вы подразумеваете под чистым полем? Опишите, пожалуйста, подробнее и мы попробуем разобраться.
                    0
                    При масштабировании карты (например в сторону увеличения масштаба) детализация не загружается, бывало секунд по 30-40 даже. Раньше такого не наблюдалось. Nexus 5 (Android 5.1.1 stock)
                      0
                      Ну вот, к примеру: dl.dropboxusercontent.com/u/4765967/Screenshot_2015-07-10-23-18-48.png
                      Детали появятся только тогда, когда дойду до 5км.
                      0
                      Что-то я не совсем понял — пешеходные маршруты вы строите по имеющимся автомобильным?
                      Если так, то тогда это будут плохие пешеходные маршруты:
                      — не по каждой автодороге можно идти
                      — не по каждой дороге, по которой можно идти, можно еще и ехать
                      А OSRM выкидывает лишние дороги из графа (согласно выбранному профилю).
                        0
                        Пешеходные маршруты мы строим независимо от автомобильных.
                          0
                          А как же
                          пешеходная навигация не должна занимать дополнительное место, сравнимое с автомобильным графом, а должна максимально использовать уже имеющиеся данные;

                          ?
                            +1
                            Пешеходная навигация работает только на данных карты, которые уже хранятся для отрисовщика. Если бы мы использовали для этого OSRM, то нам бы понадобилось собрать граф с отдельным профилем и положить его рядом с картой. Это бы и было использованием дополнительного места, сравнимого с автомобильным графом.
                              +1
                              А, понял. Я думал вы дошли до того, что один граф OSRM для обоих типов маршрутов используете :)
                        0
                        Алгоритмы в maps.me фееричны. В последнюю поездку, ткнул на карте в кемпинг, примерно 100 метров от дороги (про которую maps.me знал). maps.me подумало подумало и нарисовало машрут на другой берег острова, со словами «вот до туда дорогу знаю, а дальше к вашему кемпингу 30км топайте пешком»).
                          0
                          Так, может, «феерия» алгоритмов как раз и связана с отсутствием конкретных данных, нет?
                            0
                            OSMAnd маршрут показал нормально. Вроде бы, один источник данных, не?

                            ЗЫ Отсутствие голосовой навигации делает maps.me №3 в списке вариантов. Если бы была, я бы интерфейс OSMAnd забыл как страшный сон. (№1 — это Лимассол-специфик, 2GIS, потому что он организации тут знает).
                            0
                            А можно ссылку на конкретное место, чтобы всё было более похоже на багрепорт и менее похоже на нытьё? :)
                              0
                              34.92015
                              32.33514

                              Маршрут из Лимассола. Почему-то отправило через другой край, по другому побережью.
                            0
                            Пользуюсь MAPS.ME более года. В последнее время стал замечать, что согласно встроенной программе мониторинга батареи значительно повысился её расход.

                            Расход батареи, раздел "Батарея"
                            image


                            Однако я не уверен что приложение вообще работает в фоновом режиме, так как в разделе «Батарея» MAPS.ME есть, а в разделе, где показаны работающие в данный момент процессы — нет. Когда нажимаю на MAPS.ME в разделе «Батарея», то перехожу в меню «Use details». Кнопка «Force stop» активна, но когда её нажимаешь, то она просто становится неактивной, а MAPS.ME из раздела «Батарея» не пропадает.

                            Модель телефона и ОС
                            Jiayu G3
                            Android" 4.0.4
                            Kernel version: 3.0.13


                            Стоит заметить, что в реальности, батарея, кажется, не расходуется быстрее. Однако всё равно неприятно то, что посмотреть нормальный график без перезагрузки смартфона никак не получится, так как MAPS.ME оттуда никак не убрать.
                              0
                              Вы просто не разобрались на что смотрите… Эта информация о батарее собирается с момента загрузки устройства и данные о потреблении приложениями там только аккумулируются (!), они не показывают текущее потребление батареи процессами.
                                0
                                Понял вас. Спасибо за разъяснение!
                              0
                              Ребята из Maps.me. Когда же вы уже сделаете ночной режим то??? Уже три года прошу наверное. Достаточное количество народа использует в авто как основной навигатор, ночью ездить нереально. Приходится Motion X GPS HD использовать с ночной подложкой космоснимков, но это же тайлы и онлайн (кешировать тайлы в нескольких зумах там можно сутками)
                                +1
                                NickyX3 ночной режим скоро появится в нашем приложении официально, а пока можно его потестировать, если ввести в поиске ввести «mapstyle:dark». Обратно можно переключиться вводом «mapstyle:light». Переключение находится в тестовом режиме, поэтому могут быть сбои, падения и прочие напасти =)
                                  0
                                  Ой, крутяк! Спасибо! Еще бы кнопки тоже темные становились
                                0
                                Установил приложение в автомобильный навигатор под управлением Android 4.2.2.
                                Вижу в руководстве пользователя есть пункт «Хранилище карт» в настройках программы. У меня его нет.
                                Флешка монтируется по пути /mnt/extsd/. Приложение хранит файлы в папке /mnt/sdcard/MapsWithMe/. Не могу закачать карты, т.к. свободной памяти в /mnt/sdcard/ нет.
                                Как быть?
                                  0
                                  Иногда помогает вынуть/вставить флешку. В навигаторах часто внешняя флешка по-особому подключается к Android API, и приложение её не видит.
                                  0
                                  маршруты желательно также строить и оффлайн, раз они есть уже скаченные
                                  сейчас при попытке построить маршрут — долгий тап на карте, прога говорит «не могу определить текущие GPS»
                                  а оно и не надо, я не от текущей моей позиции хочу строить маршрут, а по 2м точкам как в яндексе или гугле
                                  2 долгих тапа — начало маршрута и конец
                                    0
                                    Поддерживаю, часто бывает, что хочешь прикинуть маршрут заранее, сидя в помещении (во-первых, без gps, во-вторых вообще не в том месте, откуда собираешься потом ехать). Нужна возможность указать старт маршрута вручную.
                                      0
                                      Под «оффлайн» имелось ввиду «без сигнала GPS», я так понимаю, потому что маршруты и так строятся без подключения к интернету
                                        0
                                        Следите за нашими обновлениями. В ближайшее время такая возможность появится.
                                      +1
                                      Забавно. Почему на LOR'е есть новость про опенсорсизацию maps.me, а от вас тишина?

                                      Only users with full accounts can post comments. Log in, please.