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

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

Для чего нужны комбинированные маршруты

Большая часть маршрутов в крупных городах, в первую очередь в Москве и Санкт‑Петербурге, включает в себя поездку на метро. Так, в Москве подземкой ежедневно пользуется больше 6 миллионов человек. Это легко объяснить: в метро понятное расписание, минимальные интервалы и нет пробок. Кроме того, многие популярные городские объекты находятся недалеко от станций.

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

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

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

Ближайшая станция не всегда самая подходящая

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

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

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

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

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

Варианты проезда и точки высадки

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

Но и это ещё не всё. Дело в том, что у большинства станций метро несколько входов. Поэтому порой довольно сложно определить точку высадки. Рассмотрим несколько примеров.

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

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

Третий, самый показательный пример — проекция входа на станцию попадает на дорогу на другом уровне высоты. Такое часто бывает в случае с многоуровневыми развязками, например вблизи станций МЦК.

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

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

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

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

Факторы выбора лучшего маршрута

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

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

Но что именно может влиять на выбор пользователя? Самое очевидное — суммарное время поездки. Мысль, что поездка на такси — это в первую очередь экономия времени, лежит в основе идеи, над которой мы изначально начинали работать.

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

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

Когда мы определились со всеми факторами, осталось обучить модель. Мы попробовали разные алгоритмы машинного обучения и остановились на том, точность которого составила порядка 60%. Это значит, что в 60% случаев наш алгоритм ранжирования корректно определил, какой именно маршрут понравится пользователю. У нас получился, безусловно, хороший результат, но мы верим, что его можно улучшить.

Немного о будущем

В сентябре мы раскатили возможность строить комбинированные маршруты на всех пользователей Android‑приложения Карт в Москве и Санкт‑Петербурге, а в ноябре всё заработало и на iOS.

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