Как работают алгоритмы Яндекс Карт для построения оптимального маршрута?

Алгоритмы Яндекс Карт для построения оптимального маршрута работают на основе дорожного графа — сетки дорог, состоящей из множества фрагментов, которые состыкованы между собой. yandex.livejournal.com yandex.ru Каждый фрагмент несёт информацию о своём участке дороги: географические координаты, направление движения, среднюю скорость движения и другие параметры. yandex.livejournal.com yandex.ru

Процесс построения маршрута происходит в несколько этапов: nplus1.ru

1. Пользователь указывает начальную точку и конечную, а далее в дело вступает маршрутизатор. nplus1.ru
2. Маршрутизатор использует алгоритм Эдсгера Дейкстры — классический метод поиска кратчайших путей в графах. nplus1.ru С его помощью система вычисляет самый быстрый вариант проезда — исходя из длины каждого отрезка графа и скорости движения на этом участке. yandex.livejournal.com yandex.ru
3. Учитываются пользовательские настройки (например, избегать ли грунтовых дорог, ехать ли по платным) и вся актуальная информация, использованная для подготовки «эталонного» графа. nplus1.ru
4. Маршрутизатор строит несколько вариантов маршрутов, и для каждого из них выбирает наиболее быстрый путь. nplus1.ru
5. Чтобы понять, какой из вариантов пути оптимальный, маршрутизатор обращается к модели машинного обучения — CatBoost. nplus1.ru Каждая поездка описывается набором признаков: временем суток, днём недели, типом дороги, средней скоростью в похожих условиях. nplus1.ru Эти признаки сопоставляются со временем, которое пользователи тратили на проезд по этому маршруту. nplus1.ru Так модель находит закономерности и учится предсказывать, сколько займёт дорога в схожей ситуации. nplus1.ru
6. Уже при движении по маршруту алгоритм каждые пару минут пересматривает свой прогноз. nplus1.ru Он учитывает новые треки от других пользователей, сопоставляет их с дорожным графом и пересчитывает время в пути. nplus1.ru

Часть факторов нельзя просчитать заранее: аварии, внезапные перекрытия дорог или участки с редким движением, где сложно определить реальную скорость. nplus1.ru Всё это вносит отклонения в математический прогноз. nplus1.ru Однако даже с учётом таких непредсказуемых факторов точность расчёта остаётся высокой — отклонения от реального времени в пути составляют не более 12 процентов. nplus1.ru