Как Google Maps строит маршруты за секунды

Как дорожная сеть превращается в математический граф

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

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

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

От классического алгоритма Дейкстры к направленному поиску A*

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

Для глобальной карты чистый алгоритм Дейкстры работает слишком медленно. Если нужно построить маршрут из Москвы в Санкт-Петербург, классический метод изучит дороги на юг в сторону Воронежа и на восток в сторону Казани с тем же усердием, что и дорогу на северо-запад. Радиус поиска разрастается концентрическими кругами, вовлекая миллионы лишних перекрёстков.

Для ускорения навигаторы используют алгоритм A* (А-звезда), разработанный в 1968 году. Этот алгоритм добавляет к пройденному расстоянию эвристическую функцию. Эвристика оценивает оставшееся расстояние от текущего перекрёстка до цели по прямой линии.

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

Иерархия дорог и предварительные вычисления

Даже оптимизированный алгоритм A* не успеет за доли секунды обработать маршрут протяжённостью в тысячу километров на сыром графе планеты. Дорожная сеть содержит сотни миллионов узлов. Решение задачи в реальном времени строится на технике Contraction Hierarchies (иерархия сжатия) и многоуровневых графах.

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

• Карта заранее разбивается на несколько иерархических слоёв от локальных улиц до магистралей федерального значения.
• Серверы заранее рассчитывают и сохраняют сокращённые пути (shortcut edges) между ключевыми транспортными развязками.
• Алгоритм быстро находит выезд из начальной точки на ближайшую крупную трассу в нижнем слое графа.
• Основная часть пути рассчитывается исключительно по скелетному графу скоростных магистралей с минимальным числом узлов.
• У цели алгоритм спускается обратно на детальный уровень дворовых дорог.

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

Учёт рельефа и типа транспорта

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

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

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

Динамические пробки и прогнозирование машинным обучением

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

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

Для предсказания будущего состояния графа Google Maps использует графовые нейросети (GNN), созданные совместно с лабораторией DeepMind. Графовая нейросеть анализирует топологию дорог, день недели, время суток, прогноз погоды и исторические данные о трафике за много лет. Это позволяет рассчитать вес ребра на момент, когда автомобиль физически доедет до него через полчаса или два часа.