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

Меня зовут Антон Овчинкин, я руководитель разработки пешеходной и транспортной навигации в Картах. Я расскажу, как мы научили алгоритмы обходить промзоны, создали ML‑модель расчёта времени в пути с учётом светофоров и подъёмов, а ещё — как связана пешеходная маршрутизация и подсчёт калорий.

Зачем улучшать маршруты

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

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

Мы сформировали план действий и приступили к работе над проектом. Но обо всём по порядку.

Собираем данные о рельефе

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

С технической точки зрения рельеф важно учитывать:

• Для построения профиля рельефа. Он показывает, как меняется высота на всём протяжении маршрута — пользователь может оценить количество и величину спусков и подъёмов.

  

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

• Для оценки времени движения по маршруту. ETA — от английского estimated time of arrival.

Как используем рельеф, рассказали. Теперь разберёмся, откуда его можно взять. Есть несколько методов:

• Определить по спутниковым снимкам или аэрофотосъёмке.

• Использовать профессиональные геодезические данные.

• Рассчитать по данным о местоположении, которые приложение использует для позиционирования пользователя.

У каждого варианта есть свои плюсы и минусы, но наиболее точные и актуальные данные можно получить в последнем случае.

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

Данные о рельефе мы связываем с расположением улиц, велодорожек и других объектов транспортной инфраструктуры. Эта информация хранится в графе дорог.

Граф дорог

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

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

Привязка

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

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

Чтобы учесть все эти нюансы, необходимо точнее привязывать GPS‑сигналы к карте. Для этого мы разработали собственный алгоритм — матчер. Он анализирует текущий и соседние GPS‑сигналы вместе, чтобы найти наиболее вероятную позицию на дорожной сети.

Привязка работает следующим образом:

1. Для каждого сигнала определяются возможные позиции на графе дорог.

2. С помощью оценки вероятностей вычисляется, какие из них наиболее правдоподобны.

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

С помощью сложной математической модели матчер обрабатывает весь массив данных и определяет наиболее вероятную позицию для каждого GPS‑сигнала — даже в условиях шума и помех. Новый алгоритм матчинга вместе с дополнительной фильтрацией выбросов в процессе привязки снизил среднюю ошибку определения высоты на ~15%, а её дисперсию — более чем в шесть раз!

Приумножение данных и расчёт высоты

Итак, с привязкой разобрались, а что дальше? Иногда алгоритму не хватает данных, чтобы каждое ребро дорожного графа было покрыто нужным количеством сигналов. Такое бывает там, где редко ходят люди. Для этого мы аккуратно распределяем значения с ребра на соседние, не нарушая связанность. Это позволяет избежать проблем: например, «запрыгивания» на мост.

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

Профиль маршрута

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

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

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

Определяем сложность маршрута

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

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

Сначала мы хотели помочь пользователю найти маршрут без крутых подъёмов. Однако на этапе сборки прототипа столкнулись с проблемами:

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

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

3. Важно учитывать не только количество крутых подъёмов, но и их длительность, длину и взаимное расположение.

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

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

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

Формула содержит набор параметров‑коэффициентов — если изменим их значения, получим результат, который больше подойдёт под нашу задачу. Например, можно донастроить алгоритм на то, что резкий подъём на 10 метров хуже, чем лишние 200 метров по прямой. Чтобы настроить эти параметры, мы изучили кейсы, где ожидали наибольших различий между старым и новым алгоритмом, а затем сравнили результаты.

Получилось, что в некоторых регионах Карты могут построить маршрут полегче почти в 50% случаев. Существенная часть из них приходится на регионы со сложным рельефом — Сочи или Владивосток.

Ищем популярные маршруты

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

В начале статьи я упоминал, что мы проанализировали, чего не хватает в маршрутах пользователям. Один из самых популярных ответов — маршрутам не хватает «человечности». Бывало ли у вас такое, что вы строите маршрут и, возможно, он действительно самый короткий или самый быстрый, но вы бы так точно не пошли? Сюда можно отнести путь через тёмные дворы, промзоны, дороги с плохим покрытием. Нашей задачей было научить алгоритм предлагать приятные маршруты, по которым действительно ходят люди.

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

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

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

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

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

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

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

Учимся точно оценивать время

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

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

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

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

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

Среди фич этой модели мы решили оставить значение времени, полученного по средним скоростям проезда, а также добавили туда светофоры, повороты и другие факторы — например, регион и время дня. Наши исследования показали, что и эти факторы влияют на результат: геокодированная информация о городе и районе входит в топ-3 фич получившейся ML‑модели, а информация о текущем времени — в топ-10.

Также в расчёт времени маршрута мы добавили и учёт рельефа. При оценке времени пути, у которого есть существенная разница высот между точками А и Б, подъём всегда будет дольше спуска.

Сложив выбранные фичи в пулы для обучения, отдельно для велосипедистов, отдельно для пешеходов, мы обучили две ML‑модели оценки времени. Они получились довольно разными:

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

• Модели получились разного качества. Хотя больше всего ошибка предсказания снизилась у веломаршрутов, в сравнении с реальным временем проезда она всё ещё остаётся немного выше, чем у пешеходных. Это связано с тем, что вариативность скорости передвижения на велосипеде больше. Иначе говоря, мы почти всегда ходим с примерно одинаковой скоростью, будь то большая дорога или узкая тропинка. А когда едем на велосипеде, для нас становятся важнее ширина дороги, её покрытие и даже бордюры и пандусы.

После внедрения моделей средняя ошибка прогноза времени для велосипедных маршрутов снизилась на 45%. Для пеших маршрутов средняя ошибка сократилась не так сильно. Однако в регионах со сложным рельефом, таких как Сочи, она снизилась на 70–90%.

В итоге у нас получилось создать технологии, которые лучше строят маршруты под запрос пользователя и точнее оценивают время. Новые алгоритмы маршрутизации и ML‑модели используются не только в Картах, но и повышают эффективность работы курьеров: в Еде, Лавке и Доставке.

А вы можете попробовать их в приложении Яндекс Карт — это отличный повод выйти на улицу, покататься на велосипеде или прогуляться. Всем комфортного передвижения по городу!