Куда и по каким дорогам могут заезжать грузовые автомобили, регламентируется отдельными правилами дорожного движения. Разрабатывая режим построения грузовых маршрутов, мы решали главную задачу — научить алгоритм работать с этими правилами, чтобы пользователи получали наиболее точные результаты.

Я расскажу, как в 2ГИС устроен алгоритм построения маршрутов в целом и как мы адаптировали его под грузовики — например, учили его строить неоптимальные по времени маршруты.

Грузовики такие же, как легковушки, но есть нюанс

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

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

Во‑вторых, в Москве и Санкт‑Петербурге для грузовиков действует пропускная система, въезд в некоторые части городов для них ограничен.

В‑третьих, передвижение грузовиков по городу регулируют дорожные знаки 3.4 «Движение грузовых автомобилей запрещено».

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

Сложная жизнь грузовиков в городе

Знак 3.4 нужен, чтобы грузовики не мозолили постоянно глаза горожанам и не портили дороги по всему городу. Например, знак позволяет им въезжать в определённые части города, только если они обслуживают предприятия, которые там находятся:

3.4 «Движение грузовых автомобилей запрещено»

Запрещается движение грузовых автомобилей и составов транспортных средств с разрешённой максимальной массой более 3,5 т (если на знаке не указана масса) или с разрешённой максимальной массой более указанной на знаке, а также тракторов и самоходных машин.

Но и это ещё не всё. Даже если грузовику можно быть в этой части города, знак разрешает въезжать и выезжать из неё только особым образом:

3.4 «Движение грузовых автомобилей запрещено»: пояснение

Знак 3.4 не запрещает движение грузовых автомобилей <...>, которые обслуживают предприятия, находящиеся в обозначенной зоне. В этих случаях транспортные средства должны въезжать в обозначенную зону и выезжать из неё на ближайшем к месту назначения перекрёстке.

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

Нельзя просто так взять и войти в грузовую зону

Знаки 3.4 расположены близко друг к другу — они очерчивают в городе специальную зону, куда грузовики могут попасть, только соблюдая определённые условия. Попасть в грузовую зону можно только через «ближайший перекрёсток» — ближайший к месту назначения въезд в зону или выезд из неё.

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

Как это требование должно влиять на результат построения, проще всего показать наглядно. Вот как будет построен грузовой маршрут при указанном параметре разрешённой максимальной массы ниже 3,5 тонн:

А вот маршрут для грузовиков массой больше 3,5 тонн — на них распространяются ограничения по знаку 3.4:

Почему возникает это различие? Виновата грузовая зона, ограничивающая проезд автомобилям с максимальной массой свыше 3,5 тонн:

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

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

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

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

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

Грузовые маршруты: вариант первый

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

Как заставить алгоритм поиска забыть о том, что он должен искать оптимальный маршрут, пока поисковая волна находится внутри грузовой зоны?

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

Какое‑то время мы использовали этот подход, но выявили в нём несколько недостатков.

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

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

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

Поисковая волна и система штрафов

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

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

Например, из участка выходят два ребра длиной 1 км, но на одном скорость 20 км/ч, а на другом — 60 км/ч. К следующему ребру волна быстрее придёт по второму участку, следовательно, при установке на поиск оптимального маршрута по времени этот участок попадает в конечный маршрут.

Волна живёт и работает в своём виртуальном таймлайне. Например, если мы начинаем строить маршрут в 12:00, первое ребро имеет длину 1 км, а скорость движения на нём равна 20 км/ч, то в конце ребра волна окажется в 12:03. Если из этого ребра исходят два ребра, длины которых также равны 1 км, но на первом скорость по‑прежнему 20 км/ч, а на втором — уже 60 км/ч, то в конце первого волна окажется в 12:06, а в конце второго — в 12:04. Весом ребра, который алгоритм использует для определения того, какое ребро будет рассмотрено следующим, как раз является время с момента старта маршрута до момента прохождения по данному ребру.

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

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

Вот так распространяется волна, когда штрафов нет (вес рёбер одинаковый и равен 1):

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

Если на поворот направо наложить штраф в 3 единицы, а на поворот налево — в 4 единицы, то выигрывает прямой маршрут:

Второй вариант построения маршрутов

Вернёмся к грузовикам.

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

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

Какие величины штрафов использовать?

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

Однако с таким подходом мы получаем только две категории проездов: ближайший к маршрутной точке и все остальные. Если ближайший к маршрутной точке проезд оказался неудачным, мы хотим, чтобы в выдаче «победил» второй по удалённости. Если остальные варианты никак не ранжированы между собой, то волна продолжит из них поиск одновременно, и в итоге победит проезд, от которого быстрее доехать до финиша. Такое в грузовой зоне не прокатит. Вот как распространяется волна, если всем нежелательным проездам назначить одинаковые штрафы (тонкими серыми линиями показана граница зоны, а в граничных вершинах (выездах из зоны) указаны значения штрафов; для простоты и наглядности веса самих рёбер не приводятся, длина рёбер говорит сама за себя):

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

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

Вот какая ситуация наблюдается при этом подходе:

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

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

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

Завершающие штрихи и повышающий коэффициент

Вот на какой системе подсчёта штрафов мы остановились. Для каждого выезда из зоны считаем время проездов до всех остальных выездов, запрещая при этом двигаться по рёбрам зоны. Временны́е показатели, умноженные на некоторый повышающий коэффициент, и будут штрафами, накладываемыми на соответствующие нежелательные выезды. То есть для каждого выезда Ek хранится отображение остальных выездов E0,..., Ek-1, Ek+1,... , EN на время, которое занимает проезд от EK до соответствующего выезда. С въездами в зону всё почти так же, за исключением того, что штрафом является не время проезда от ближайшего к финишной точке въезда до нежелательного, а, наоборот, время проезда от нежелательного въезда до ближайшего.

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

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

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

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

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

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

Как в итоге работает алгоритм

Мы научили алгоритм учитывать требования знака 3.4., и теперь он работает так:

• берём заранее вычисленный ближайший к маршрутной точке проезд;

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

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

Эта версия алгоритма показала значительный рост скорости построения маршрутов, в некоторых случаях вплоть до 10 раз. Что ж, это был долгий путь (маршрут?), но мы справились!

А если вы хотите делать такие же крутые штуки (а может, ещё круче), у нас в сервисе транспорта открыты вакансии.