«Лёгкие маршруты» в 2ГИС: рассказываем про алгоритмы и новую систему штрафов / Хабр

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

Недавно в дополнение к самому быстрому и оптимальному мы добавили ещё один вид маршрута — «лёгкий маршрут», наименее стрессовый для водителя. Минимум сложных перекрёстков, поворотов налево и перестроений.

В статье рассказываем, как мы строим лёгкий маршрут и как он вписывается в текущую архитектуру маршрутизации.

Как мы строим маршруты

Для начала рассмотрим наш общий подход к построению маршрутов.

Дорожный граф

Дорожная сеть моделируется направленным графом — структурой из узлов (точек) и рёбер (связей между ними). Для каждого направления движения на дороге создаётся отдельное ребро.

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

Рёбра и узлы дорожного графа. Рёбра раскрашены в разные цвета в соответствии с уровнем значимости дороги, узлы схематично изображены красными кружками. В реальных данных узлов больше, чем на картинке

Поиск кратчайшего пути

Поскольку мы имеем дело с графами, для поиска кратчайшего пути между точками, которые указал пользователь, можно использовать классические алгоритмы из теории графов, например, алгоритм Дейкстры.

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

При этом «кратчайшим» будет маршрут, сумма весов рёбер которого минимальна.

Веса рёбер

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

Алгоритм выбирает центральный путь как кратчайший по сумме весов

Но в реальной жизни далеко не всегда нужен именно такой маршрут — между 99 км по грунтовой дороге и 100 км по асфальту такой алгоритм предложит грунтовку. Кроме того, он не учитывает пробки, повороты и другие факторы. Предпочтительной метрикой является время проезда по ребру. На основе статистических данных и ML‑моделей мы можем оценить скорость движения на каждом ребре индивидуально. А далее на основе таких скоростей мы оцениваем время проезда по каждому ребру и используем его в качестве веса в алгоритме Дейкстры:

^{где — вес ребра e, — длина ребра e (например, в метрах), — скорость на ребре (соответственно, м/c).}

Если считать скорость постоянной и одинаковой на всех рёбрах, то мы вернёмся к поиску кратчайшего по расстоянию маршрута. Поэтому подход на основе времени является более общим.

Алгоритм выбирает верхний путь как «самый быстрый» по времени. Он отличается от кратчайшего по расстоянию пути

Штрафы

Одного учёта скоростей недостаточно. Навигатор 2ГИС стремится предлагать пользователям оптимальные маршруты, при построении которых учитывается множество факторов: левые повороты, движение по кольцам, дублёрам, съездам и так далее.

Реализация подобной логики возможна за счёт механизма штрафов (здесь сразу скажем, что в автомобильном навигаторе у нас внедрена более продвинутая ML‑модель, про которую мы рассказывали здесь, она заменяет часть штрафов).

Штраф — это искусственное завышение веса ребра при соблюдении определённых условий. Например, мы хотим избегать дублёров. Простым вариантом штрафа будет увеличение веса каждого ребра, соответствующего дороге‑дублёру, на величину, равную произведению длины этого ребра и некоторой константы (штраф за проезд):

^{где — вес ребра e, — длина ребра e в метрах, — скорость на ребре (м/с), — функция, возвращающая 1, если e является дублёром, и 0 в противном случае, — коэффициент штрафа за дублёр (дополнительное число секунд в вес ребра за каждый его метр), общий для всех рёбер.}

Поскольку при обработке узла в алгоритме Дейкстры легко узнать, по какому ребру мы пришли в узел, штрафы легко сделать зависимыми от предыдущего ребра. Например, можно добавить дополнительный штраф для ребра‑дублёра, если предыдущее ребро не было дублёром (штраф за въезд). Это позволит избегать кратковременных заездов на дублёры, для которых штрафа, зависимого от длины, может быть недостаточно.

Важно отметить, что из‑за таких искусственных завышений вес ребра перестаёт совпадать с реальным временем в пути по нему, поэтому после построения маршрута требуется перерасчёт времени проезда без учёта искусственных штрафов.

Построение маршрутов «точка‑точка» в реальной жизни

До текущего момента в статье в качестве алгоритма построения маршрутов рассматривался алгоритм Дейкстры, но в реальной жизни для построения маршрутов типа «точка‑точка» в навигаторе его сложно назвать подходящим.

Основная причина заключается в том, что в нём рёбра просматриваются во всех направлениях с одинаковым приоритетом, а не преимущественно в направлении финишной точки, что неэффективно. Самый простой алгоритм, подходящий для построения маршрутов «точка‑точка» в навигаторе — алгоритм A*. Он является модификацией алгоритма Дейкстры, и в его основе лежит подход, при котором вес каждой вершины в очереди складывается из стоимости достижения этой вершины от точки А (как в алгоритме Дейкстры) и оценки времени проезда от этой вершины до точки Б. Для простоты получения такой оценки в качестве расстояния можно использовать расстояние по прямой — в реальности же используется кратчайшее расстояние по поверхности Земли между двумя точками; скорость при этом считается постоянной.

Таким образом, алгоритм начинает перемещаться преимущественно в сторону точки Б (поскольку веса вершин в этом направлении повышаются слабее), что серьёзно сокращает количество перебираемых рёбер.

Иллюстрация работы алгоритма A*. Из-за изменения весов по сравнению с алгоритмом Дейкстры вершины, в которые ведут рёбра E8 и E9, больше не достигаются алгоритмом. В вершинах отображены их веса в очереди (т.е. суммы времени проезда от точки А до вершины и оценки времени проезда до точки Б по прямой) — Иллюстрация работы алгоритма A*. Из‑за изменения весов по сравнению с алгоритмом Дейкстры вершины, в которые ведут рёбра E8 и E9, больше не достигаются алгоритмом. В вершинах отображены их веса в очереди (то есть суммы времени проезда от точки А до вершины и оценки времени проезда до точки Б по прямой)

Но и A* считается недостаточно эффективным алгоритмом для построения маршрутов по дорожному графу по современным меркам, особенно для маршрутов на большие расстояния.

Предварительная обработка графа и идея шорткатов

Дальнейшие оптимизации времени построения маршрутов по сравнению с классическим A* во многом возможны за счёт использования свойств дорожной сети и предварительной подготовки дорожного графа.

Дорожный граф иерархичен — в нём явно выделяются более значимые дороги (федеральные трассы, магистрали, основные улицы города) и менее значимые (внутриквартальные проезды, лесные дороги, прочие улицы города). Попадая на дорогу высокой значимости, дороги низкой значимости, как правило, можно не рассматривать вплоть до окрестностей точки Б. Более того, если два разных пользователя построят разные маршруты, например «Москва — Новосибирск», то эти маршруты будут отличаться только начальным и конечным фрагментами (внутри городов), а весь промежуточный путь будет одинаковым.

Опираясь на эти наблюдения, можно заранее подготовить фрагменты маршрутов, которые можно будет переиспользовать для ускорения поиска. Эти фрагменты далее мы будем называть «шорткатами». При таком подходе, «честно» путь ищется только от точек А и Б до ближайших шорткатов, а «середина» маршрута формируется из шорткатов.

Шорткаты похожи на обычные рёбра, но сильно укрупнённые. На практике хорошие результаты даёт построение иерархии шорткатов. На первом уровне иерархии находятся обычные рёбра, уровнем выше — слегка укрупнённые, уровнем выше — ещё более укрупнённые.

Рёбра (шорткаты) уровней 1, 3, 5. Разные рёбра (шорткаты) раскрашены в разные цвета. Видно, что на уровне 1 рёбра совсем короткие, в то время как на уровне 5 длина шорткатов может достигать нескольких километров

Маршрут одновременно строится от точки А к точке Б и от точки Б к точке А, переход на шорткаты более высокого уровня производится при первой возможности. В какой‑то момент маршруты от А к Б и от Б к А встречаются, и итоговый маршрут считается найденным.

Описанный подход ускоряет построение маршрутов, но у него есть несколько недостатков:

Иерархию шорткатов необходимо поддерживать в актуальном состоянии с учётом постоянных изменений на дорогах. Для этого требуется частое перестроение шорткатов, и время вычислений при этом не должно быть слишком долгим;
Поддерживать несколько наборов весов для рёбер становится сложнее. Вспомним, что кратчайшие и оптимальные маршруты отличаются весами рёбер, а поэтому для них нужно поддерживать разные наборы шорткатов, держать их в памяти, тратить время на обновление;
Ограничиваются возможности кастомизации маршрутов под пользователя. Любая возможность кастомизации приводит к необходимости поддержки новых шорткатов, что резко повышает себестоимость такой кастомизации.

Несмотря на перечисленные недостатки подхода, как правило, его достоинства всё же перевешивают. Конечно, здесь мы только кратко рассмотрели идею алгоритмов подобного класса. Хороший обзор современных алгоритмов построения маршрутов «точка‑точка» есть в статье H. Bast, D. Delling, A. Goldberg, M. Müller‑Hannemann, T. Pajor, P. Sanders, D. Wagner, R. F. Werneck Route Planning in Transportation Networks. А про алгоритм, реализованный у нас, расскажем в отдельной статье. Отметим, что в настоящее время область построения эффективных алгоритмов «точка‑точка» для реальных дорожных сетей продолжает активно развиваться.

Теперь, когда мы разобрали всё необходимое, можно переходить к лёгким маршрутам.

Логика построения лёгкого маршрута

У нас уже есть два типа маршрутов: кратчайший (без искусственных штрафов) и оптимальный (маршрут, по нашему мнению лучший для большинства водителей). Для построения новых маршрутов мы решили поддержать тип, который так и назвали — «лёгкий».

В качестве основы для лёгких маршрутов мы взяли наш текущий оптимальный маршрут. Сохранив всё, что в нём есть (в том числе ML‑модели), мы добавили дополнительную логику, которая избегает сложных участков:

многополосных дорог (3 полосы и более),
высокоскоростных дорог (с ограничением скорости выше 60 км/ч),
колец,
левых поворотов,
манёвров на второстепенную дорогу, при которых главная дорога уходит направо (то есть левых относительно главной дороги манёвров),
разворотов на нерегулируемых перекрёстках.

Для этого мы добавили (или в некоторых случаях увеличили) штрафы за рёбра, обладающие перечисленными свойствами. Штрафы сделали аддитивными — вычисляем штраф за каждую особенность ребра по отдельности и впоследствии всё суммируем. Таким образом, для каждого ребра:

1. Вычисляется его вес для оптимального маршрута;

2. Вычисляются штрафы из п.1–6 и добавляются к весу для оптимального маршрута.

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

Многополосные дороги

Для многополосных дорог подходит комбинированная модель штрафов за въезд и за проезд. Накладываем штраф в некоторое число секунд при перемещении на многополосное ребро с не многополосного, а также штрафуем каждый метр движения по многополосной дороге на несколько миллисекунд. Точные значения параметров штрафов зависят от значимости дороги. Чтобы сделать штраф зависимым от числа полос, каждая полоса направления движения ребра штрафуется отдельно:

$m(e) = [\,m_{entry}(e)\,(1 - p_m(e_{prev})) + l_e\,m_{cont}(e)\,]\,p_m(e)\,w_e$

^{где ) — значение штрафа за многополосную дорогу для ребра e, — штраф за въезд, зависящий от значимости текущего ребра (значение из таблицы штрафов для каждого уровня значимости — федеральные трассы, магистральные улицы, основные улицы и так далее), в секундах, — индикаторная функция, принимающая значение 1, если e является многополосным, и 0 в противном случае, — ребро, с которого переходим на e, — длина ребра e в метрах, — коэффициент штрафа за проезд, зависящий от уровня значимости e (значение из таблицы коэффициентов для каждого уровня значимости), — количество полос на ребре e.}

Высокоскоростные дороги

Штраф за высокоскоростные дороги немного проще. Он не зависит от числа полос и значимости ребра, в остальном используется тот же самый подход, что и для многополосных дорог (штраф за въезд и штраф за проезд):

$h(e) = [\,h_{entry}\,(1 - p_h(e_{prev})) + l_e\,h_{cont}\,]\,p_h(e)$

^{где — фиксированный штраф за въезд (в секундах), — индикаторная функция, принимающая значение 1, если e является высокоскоростным, и 0 в противном случае, — фиксированный коэффициент штрафа за проезд.}

Кольца

В случае с кольцами нет необходимости делать штраф зависящим от расстояния, пройденного по кольцу — достаточно штрафа за въезд:

$r(e) = r_{entry} \cdot (1 - p_r(e_{prev})) \, p_r(e)$

^{где — штраф за проезд по кольцу, — фиксированный штраф за въезд (в секундах), — индикаторная функция, принимающая значение 1, если e принадлежит кольцу, и 0 в противном случае.}

Левые повороты

Для левых поворотов мы решили повторно использовать модель штрафа из оптимального маршрута. В случае правостороннего движения угол поворота при перемещении между рёбрами может варьироваться от -180 (включительно) до 180 (не включительно) градусов. Угол в -180 градусов означает левый разворот, 0 градусов — движение прямо, 179 — максимально возможный крутой поворот направо. Окружность разбивается на сектора, соответствующие различным манёврам (прямо, плавно налево, налево и так далее). Для каждого сектора задаётся свой фиксированный штраф.

Таким образом, в подобной модели можно сразу задать штраф и за левые повороты, и за развороты. Для лёгких маршрутов мы повысили эти значения. Но в процессе экспериментов мы решили этим не ограничиваться и дополнительно повысили штрафы и за правые повороты.

Нерегулируемые перекрёстки

На нерегулируемых перекрёстках (на перекрёстках без светофора) мы штрафуем съезд с главной или второстепенной дороги на второстепенную, если для этого нужно повернуть налево относительно направления главной дороги. Штраф фиксированный.

Например, штрафуются такие манёвры:

Поворот с главной дороги налево на нерегулируемом перекрёстке (на карте и местности)

Аналогичный штраф уже есть в оптимальном маршруте, в лёгком маршруте он накладывается повторно с другим значением.

Архитектурные сложности и ограничения

В итоге функциональность была реализована с учётом различных ограничений. Расскажем про несколько компромиссов, к которым пришли.

Настройки и фильтры

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

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

Сложные штрафы за многополосные участки

Можно было бы ввести более сложный штраф за многополосные участки. Например, особенно сильно штрафовать манёвры налево (направо) на небольшом расстоянии после въезда на многополосную дорогу через правый (левый) поворот, поскольку водителю потребуется перестраиваться.

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

Более простая схема — штраф за въезд и штраф за проезд по многополосной дороге — показала хорошие результаты в процессе тестирования, поэтому мы остановились именно на ней.

Пакетная обработка запросов

При включении опции лёгкого маршрута в результатах отображаются как оптимальный (основной с альтернативами), так и лёгкий маршрут. Нам хотелось избежать пересылки двух запросов и ответов по сети — одного для оптимального маршрута с альтернативами и второго для лёгкого, поэтому мы остановились на пакетах запросов. С мобильных устройств на балансировщик может приходить массив запросов, которые обрабатываются независимо друг от друга, и результаты по всем запросам возвращаются на клиент в одном ответе.

Далее клиент сам решает, как объединить результаты: когда лёгкий маршрут включить в выдачу, а когда не включать. Если лёгкий маршрут получился слишком длинным, то он не попадает в выдачу. Также исключается дублирование маршрутов (лёгкий маршрут может совпасть с оптимальным или его альтернативами). Ещё у нас есть маршрут «как обычно» — если он был найден и не совпадает с лёгким маршрутом, то размещаем его перед лёгким.

Результаты

Рассмотрим ситуации, где лёгкий маршрут, на наш взгляд, особенно полезен.

В примере слева один из альтернативных маршрутов проходит через выезд на ТТК (Третье транспортное кольцо, крупная автомагистраль) с последующим разворотом, а другой вариант предлагает движение по кольцу. Лёгкий маршрут выбирает другое решение — он немного дольше по времени, но заметно проще для неопытного водителя.

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

Итог

У нас получилось реализовать эффективный метод построения лёгких маршрутов, хорошо работающий с учётом имеющихся ограничений. При этом нам удалось сохранить текущие показатели SLA, совместимость API, избежать лишних пересылок данных по сети и чрезмерного роста объёма данных.

Надеемся, что эта функциональность окажется полезной для многих водителей в повседневной жизни.

«Лёгкие маршруты» в 2ГИС: рассказываем про алгоритмы и новую систему штрафов