2ГИС с самой первой версии навигатора умеет строить разные виды маршрутов — автомобильные, пешеходные, маршруты на общественном транспорте — на мобильных устройствах без доступа к интернету, но только внутри городов.
С 2019 года 2ГИС также умеет строить маршруты между городами, но только при наличии интернета.
Уже давно наши пользователи просили дать возможность строить междугородние маршруты без доступа к сети. И вот, мы наконец сделали это.
Специфика межрегиональных маршрутов
Исторически сложилось © так, что дорожный граф в 2ГИС разбит на регионы. Регион — это обычно город, несколько небольших смежных городов, область/край или часть большой области/края. Например, Новосибирск или Москва являются отдельными регионами, Новосибирская область — тоже отдельный регион, а вот Красноярский край в силу своих гигантских размеров разбит на несколько регионов.
До появления бесшовки (так мы в команде Транспорта называем фичу построения междугородних маршрутов, т.е. маршрутов, проходящих через несколько регионов), такое разбиение было само собой разумеющимся: маршруты строились только в пределах одного региона. Пользователь скачивал интересующий его город и получал в приложении все возможности: карту, справочник, построение разных типов маршрутов — и всё это в том числе без доступа к сети. Регионы были самодостаточными и не знали ничего о друг друге на уровне алгоритма.
Когда мы делали бесшовку, мы не стали трогать разбиение на регионы, — слишком многое в компании на него было завязано, — а решили научить алгоритм поиска маршрутов перепрыгивать через границы регионов.
Такой подход хорошо подходит для построения бесшовных маршрутов на серверах, но на реалии мобилки он не ложился. Всё упирается в ресурсы: чем длиннее маршрут, тем больший объём данных нужно постоянно держать в оперативной памяти в процессе построения (причём зависимость эта нелинейна), да и время поиска фатальным образом увеличивается. Кроме того, региональная разбивка и изначальный подход «маршрут только в пределах региона» привели к определённым архитектурным решениям, которые также препятствовали прямому переносу серверного подхода на клиентские устройства.
Например, для работы с данными региона нужно поднять его в память (конечно, не целиком, но некоторый контекст нужно держать горячим), а особенности работы алгоритмов поиска маршрутов предполагают постоянные перескакивания между регионами. Ну и не стоит забывать, что мы не можем завязываться только на флагманские устройства — нам нужно, чтобы приложение работало также на устройствах среднего и даже начального уровня.
Сервер обходил все озвученные ограничения в лоб — он просто поднимал в оперативную память вообще все регионы разом и не выгружал их. И это оправданно: сервер обрабатывает запросы из разных регионов и разной дальности, например, он одновременно может искать маршруты Москва-Владивосток, Новосибирск-Алтай и маршрут внутри Иркутска.
Организация данных
В мобильном приложении для поиска маршрутов используется классический A* (эта же реализация, кстати, изначально была и на серверах, но на данный момент там уже несколько раз всё коренным образом поменялось). В очередной раз пересказывать его описание здесь нет смысла, интересующиеся могут пройти по ссылке. Интереснее поговорить про организацию данных.
Весь наш дорожный граф разбит на тайлы. Тайл представляет собой квадратную область, хранящую все данные обо всех объектах, которые в неё попали. Поскольку мы говорим о задаче поиска маршрутов, данные здесь — это всё, что так или иначе касается решения этой задачи:
узлы и рёбра графа с различными атрибутами: например, дорожные знаки, камеры, светофоры, тип покрытия, количество полос;
геометрии рёбер;
предрассчитанные инструкции проезда: «Плавно поверните налево», «Развернитесь» и т.д.
В общем, всё, что требуется непосредственно при построении маршрутов или просто полезно будет показать пользователю.
В процессе построения маршрута поисковая волна распространяется от исходного ребра, пока не встретит целевое. Чтобы понять, на какие рёбра можно перейти с текущего, а также о прочих свойствах рёбер, важных для поиска, в процессе распространения волне нужно постепенно загружать в память тайлы, на рёбрах которых она оказывается. Конечно, когда тайл полностью обработан (все его рёбра рассмотрены волной), его можно выгрузить из памяти, но постепенно фронт волны (рёбра, которые лежат в очереди и ждут, пока волна их извлечёт и обработает) становится всё шире, а значит, всё больше тайлов должно одновременно находиться в памяти.
Ниже приведён пример маршрута в Москве. Красная линия — сам маршрут, синяя «сетка» — рёбра, просмотренные волной в процессе его построения. Маршрут состоит всего из 339 рёбер, но просмотрено было аж 167 524 ребра. При этом волной было загружено 973 тайла, а максимальное количество одновременно загруженных тайлов составило 554 штуки.
А вот на маршруте Москва-Хабаровск (приводить его волну нет смысла — будет каша из рёбер) волна обошла уже 4 935 381 ребро! Маршрут при этом проходит через 44 региона и насчитывает 32173 ребра, а вот волна побывала в 77 регионах, посетила в общей сложности 207306 тайлов, а в пике было одновременно загружено 28865 тайлов.
Из примеров выше видно, насколько отличаются метрики для маршрута внутри региона и длинного междугороднего маршрута с тем же началом. Ясно, что не каждое мобильное устройство справится с таким объёмом данных.
Макрограф
Одно из классических решений вышеописанных проблем — предрасчёт.
Если что-то долго или дорого выполнять при каждом запросе, разумнее сделать это один раз и использовать готовый результат. Этим путём пошли и мы.
Однако в лоб в задаче маршрутизации предрасчёт использовать не получится. Конечно, было бы здорово заранее вычислить маршруты между всеми возможными комбинациями стартовой и финишной точек и потом вытаскивать готовый маршрут из хеш-таблицы за O(1). Но такая хеш-таблица едва ли поместится на конечное устройство… Она вообще едва ли поместится на всю доступную сейчас человечеству память (а если и поместится, то займёт существенную её часть).
Если предрассчитывать маршруты целиком не получается — значит, нужно предрассчитывать части маршрутов, а уже потом из этих частей составлять готовый маршрут. Фактически, если взять все эти заранее вычисленные кусочки маршрутов и собрать вместе, мы получим граф, рёбрами которого и будут эти кусочки. Этот граф мы называем макрографом, потому что он более грубый, более крупного масштаба, чем базовый граф. Рёбра этого графа мы называем макрорёбрами. Обычно подобные сущности принято называть shortcuts — шорткатами — но у нас устоялась такая терминология.
Построение макрографа
Так как вся поддерживаемая нами территория разбита на регионы, которые пользователь может скачивать по отдельности, то макрограф мы также будем строить с учётом этой разбивки.
На первом этапе мы берём все въезды в регион (вершины графа, в которые входят рёбра, не принадлежащие данному региону) и все выезды из него (вершины, из которых исходят рёбра, не принадлежащие региону) и строим маршруты между каждой парой таких точек. Здесь отлично подойдёт алгоритм Дейкстры, поскольку за один вызов поиска мы можем найти все маршруты от одного въезда в регион до всех выездов из него.
После того, как все такие маршруты построены, нужно выделить из них макрорёбра. Если упростить, то мы рассматриваем подграф базового графа, который включает только рёбра построенных маршрутов. Каждая непрерывная последовательность рёбер без развилок (то есть такая, по которой прошёл один или несколько маршрутов) объединяется и становится макроребром. Точки разветвлений становятся узлами макрографа (для общности мы называем их макроузлами).
Для последующего поиска маршрутов макрорёбра, как и обычные рёбра базового графа, должны иметь веса. С этим тоже всё просто: сумма весов базовых рёбер, составляющих макроребро, является весом этого макроребра.
Запреты на переходы
Стоит упомянуть одну особенность нашего представления дорожного графа. Обычно для задания структуры графа достаточно тем или иным образом указать для каждого ребра, какие вершины оно соединяет. В случае с дорожным графом такая простая структура не всегда удобна. Например, на перекрёстке в одном направлении можно повернуть направо, а в противоположном налево, на ту же дорогу, нельзя.
В теории, эту проблему можно решить введением дополнительных промежуточных рёбер, которые будут соединять только разрешённые направления, но это существенно увеличит количество рёбер и вершин графа, что повлияет на скорость построения. Кроме того, такие графы значительно сложнее редактировать.
Поэтому мы используем запреты на переходы. Каждое ребро хранит список рёбер, которые исходят из его целевой вершины и переход на которые запрещён. И при построении макрографа эти запреты переносятся в макрорёбра.
Поиск межрегионального маршрута
Идея поиска межрегионального маршрута с использованием макрографа проста: строим маршрут по макрографу, затем перестраиваем голову и хвост маршрута в начальном и конечном регионах по базовому графу, после чего объединяем эти три кусочка — голову, хвост и транзитную часть — в результирующий маршрут.
При построении любого маршрута — как по макрографу, так и по базовому графу — в первую очередь нужно сопоставить пользовательские точки с рёбрами графа. Этот процесс мы называем притяжкой. В основе притяжки у нас лежит пространственный индекс на базе R-деревьев. Рёбра графа добавляются в индекс, после чего довольно быстро можно для заданной точки определить, какие рёбра к ней ближе всего.
Сам поиск по макрографу осуществляется алгоритмом A*. Это практически классическая реализация алгоритма, никакой сложной бизнес-логики, как в случае с тем же A* на базовом графе, здесь нет: просто распространяем поисковую волну от стартового макроребра, пока не встретим финишное, учитывая предрассчитанные веса макрорёбер. Из дополнений только проверка запретов на переходы, о которых сказано выше.
Макрограф разбит на тайлы. При распространении волны по мере движения по графу тайлы, на рёбра которых совершается переход, загружаются в память. Для управления набором загруженных тайлов мы используем простейший LRU-кэш, поскольку его семантика отлично ложится на поведение волны: фронт волны сосредоточен в ограниченном количестве тайлов и обычно волна, пока не просмотрит все (или почти все) рёбра в них, не идёт дальше. В тайлы же, все рёбра которых были обработаны, волна больше никогда не вернётся, поэтому постепенно они уходят в конец кэша и в конце концов вытесняются из него. При этом в качестве стратегии вытеснения мы используем не количество загруженных тайлов, как это делается обычно, а общий объём занимаемой ими памяти. Таким образом, мы можем гибко управлять балансом время/память — если нам остро необходимо экономить память, мы можем пожертвовать временем, которое тратится на повторное чтение тайла, если он был вытеснен раньше, чем волна полностью его обработала.
Для чего перестраивать кусочки маршрута в начальном и конечном регионе? Дело в том, что, как было сказано выше, макрограф довольно груб, довольно разрежен относительно базового графа. Большей части дорог, которые есть в базовом графе и по которым, скорее всего, и поехал бы реальный человек, в макрографе нет. Макрограф в большей степени рассчитан на транзитный проезд через регион целиком, а не на детальное перемещение в пределах региона. Поэтому начальную и конечную части маршрута по макрографу следует считать лишь набросками итогового варианта маршрута; по большому счёту они используются для определения точек выезда из региона — именно эти точки будут служить финишной/стартовой при перестроении этих частей маршрута по базовому графу, и в них будет происходить склейка трёх частей маршрута в одну.
Обогащение маршрута
После построения маршрута мы имеем всего лишь последовательность идентификаторов рёбер базового графа, из которых маршрут состоит. Пользователь же хочет видеть не набор из сотен 64-битных чисел, а геометрию маршрута, да ещё и с расставленными на ней точками интереса — ограничениями скорости, камерами контроля, искусственными неровностями и т.д.
Мы экспериментировали с тем, откуда брать эту информацию. Разумеется, она уже есть в данных базового графа, но у нас была идея продублировать её в данных макрографа и таким образом сделать макрограф полностью самодостаточным. Прототип был написан и работал, но в процессе стало понятно, что это не самый лучший вариант: слишком много всего приходится реализовать заново — как формат хранения этих данных, который не получилось бы взять напрямую из представления базового графа, так и способ доступа к ним в коде. Кроме того, добавление новых фичей в данные (новый флажок или свойство ребра, которое отражается на представлении участка дороги на карте) также будет требовать двойной работы.
Ещё одним преимуществом самодостаточного макрографа мы изначально считали то, что пользователю не придётся скачивать целиком регион для всего лишь транзитного проезда по нему, но и в этом случае не обходится без недостатков: что, если пользователь, находясь в транзитном регионе, захочет поискать что-то — заправку, придорожное кафе, туалет? А если по какой-то причине существенно отдалится от изначально проложенного маршрута, а затем захочет на него вернуться? В макрографе может не оказаться рёбер, которые проведут пользователя от его текущего местоположения обратно на трассу, и в макрографе точно нет и быть не может данных справочника, в которых можно найти ближайшее кафе или заправку.
В конечном итоге мы решили, что для построения маршрутов через несколько регионов пользователь должен будет скачать данные всех этих регионов. Так мы не ломаем пользовательский опыт — в любом регионе можно полноценно использовать все функции приложения, доступные в оффлайне, а также снимаем с себя задачу постоянной актуализации фичей, завязанных на данные.
Представление макрографа
Макрограф, как и базовый граф, мы разбиваем на тайлы, только размер их значительно больше, чем на базовом графе. Из-за разреженности макрографа делать тайлы слишком маленькими нет смысла, в этом случае в большинстве тайлов будет по 1–2 вершины, а многие вообще окажутся пустыми.
Поскольку в алгоритме построения маршрута по макрографу есть несколько чётко разделённых и непересекающихся шагов, тайлы мы также разбили на несколько секций, каждая из которых используется на своём шаге.
Мы выделили 4 секции: секцию притяжки, секцию поиска, секцию восстановления и секцию сшивки. Первые 3 секции чётко ложатся на 3 шага алгоритма построения маршрута — притяжка пользовательских точек к макрографу, поиск маршрута по нему и восстановление из последовательности идентификаторов макрорёбер последовательности идентификаторов базовых рёбер. Про секцию сшивки мы поговорим ниже.
Напомним, что в самом макрографе мы не храним ничего, что не нужно непосредственно для поиска по нему. В том числе, там не хранятся геометрии макрорёбер. Однако для притяжки к макрографу геометрии необходимы — без них не сформировать пространственный индекс. Но детальные геометрии макрорёбер (которые могут насчитывать десятки, а иногда и сотни базовых рёбер, каждое из которых само по себе имеет детальную геометрию, насчитывающую порой десятки координат) были бы очень тяжёлыми. Да и необходимости в них нет, ведь притяжка к макрографу нужна только для того, чтобы построить набросок маршрута по нему. Впоследствии начальная и конечная части (к которым и осуществляется притяжка) всё равно будут перестроены по базовому графу.
Поэтому мы выделяем секцию притяжки. В ней хранятся в значительной степени упрощённые геометрии макрорёбер. Для упрощения мы используем алгоритм Дугласа-Пекера с довольно большим допуском.
В секции поиска хранится информация о топологии макрографа — узлы с их координатами, списком исходящих рёбер и информацией о том, с каких рёбер на какие запрещён переход, и рёбра с их длиной и временем проезда по ним.
Секция восстановления каждому макроребру ставит в соответствие последовательность базовых рёбер, из которых состоит макроребро. На основе этой информации мы преобразуем маршрут по макрографу в итоговый маршрут на базовом графе, который уже можно обогащать различной полезной информацией, взятой из данных базового графа.
Секция сшивки — это то, благодаря чему работает межрегиональное построение маршрутов. Дело в том, что тайлы на границе региона могут (и часто будут) содержать рёбра, принадлежащие разным регионам. Однако из-за порегионального построения в каждом отдельном регионе каждый граничный тайл будет содержать только данные, принадлежащие этому региону. Чтобы восстановить исходную картину и собрать несколько кусочных граничных тайлов, загруженных из нескольких смежных регионов, в итоговый полный тайл, нужно произвести со всеми этими тайлами операцию, которую мы называем сшивкой; именно для этого и используется секция сшивки.
На этапе предрасчёта мы определяем тайлы, пересекающиеся с границей регионов, и формируем для них секцию сшивки, которая содержит:
информацию о том, в каких ещё регионах потенциально могут располагаться данные этого тайла;
и информацию, необходимую для сшивания узлов: в одном регионе мы знаем, какие рёбра этого региона входят в узел, в другом — какие рёбра уже этого региона исходят из него.
В итоге мы должны будем получить единый узел, связывающий два региона в единый граф.
На самом деле, сшить сами узлы несложно. Узел однозначно идентифицируется своими координатами, поэтому достаточно объединить все узлы с одинаковыми координатами в один. Основная сложность снова заключается в запретах на переходы между рёбрами: когда мы строим макрограф конкретного региона, мы знаем только идентификаторы макрорёбер, принадлежащих этому региону, но идентификаторы макрорёбер соседних регионов нам неизвестны. Поэтому для восстановления информации о запретах мы обращаемся к идентификаторам базовых рёбер: если запрещён переход с ребра A на ребро B, значит, запрещён и переход с макроребра, заканчивающегося ребром A, на макроребро, начинающееся с ребра B. В итоге секция сшивки содержит таблицу запретов на переходы между базовыми рёбрами, а при сшивке мы проставляем соответствующие запреты уже для макрорёбер, зная, какими базовыми рёбрами они начинаются или заканчиваются.
Всё описанное выше актуально для сшивки секции поиска. Секции притяжки и восстановления сшиваются элементарно: достаточно добавить в сшитый тайл данные из соответствующей секции всех региональных тайлов, поскольку ни для притяжки, ни для восстановления топология не важна, важно лишь получить по идентификатору макроребра его геометрию (для притяжки) или список его базовых рёбер (для восстановления).
Идентификаторы
Есть два вида сущностей, которые мы хотим идентифицировать в процессе работы с макрографом: тайлы и узлы/рёбра.
С тайлами всё крайне просто: в силу регулярности разбивки карты на тайлы можно считать сетку тайлов, покрывающую всю карту, двумерным массивом (который для простоты можно сплющить в одномерный, в котором строки следуют одна за другой); индекс в этом массиве и является идентификатором тайла. Таким образом, зная размеры тайла и количество тайлов в строке, для любой произвольной точки на карте можно однозначно определить, в каком тайле она находится, то есть чисто арифметически восстановить из координат точки идентификатор тайла.
Рёбра и узлы имеют более сложный составной идентификатор. Он включает в себя идентификатор тайла, которому принадлежит ребро или узел, идентификатор региона, а также локальный идентификатор сущности в тайле (просто последовательный счётчик).
Для чего нужен идентификатор региона? Ведь в результате сшивки тайлы должны терять свою региональную принадлежность. Почему бы не ограничиться идентификатором тайла?
На самом деле, на момент запроса ребра или узла тайл ещё может быть не загружен, а сшивка производится по запросу, в момент загрузки тайла. Поэтому нам нужен начальный регион, с которого мы начнём считывать тайл; после загрузки тайла из конкретного региона мы можем выяснить, является ли он граничным и требует ли сшивки, и, если это так, на основе данных из секции сшивки догрузить оставшиеся части тайла из соседних регионов.
Ограничения реализации
Первая версия реализации имеет ряд ограничений: сейчас мы не поддерживаем построение альтернативных маршрутов, промежуточные точки, различные фильтры (например, избегание платных дорог или грунтовок), а построение маршрутов доступно только на автомобиле. Какие-то из этих ограничений можно разрешить проще, какие-то потребуют дополнительных усилий. Мы будем следить за фидбеком и на основе него принимать решение о последующих улучшениях.
Новая возможность уже доступна всем пользователям в последней версии приложения 2ГИС.