Как работают системы построения маршрутов в навигаторах?

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

Некоторые этапы построения маршрута:

1. Получение актуальных данных. 1 Для этого используются отзывы пользователей и анонимные отчёты о их геолокации. 1 Полученные сведения сверяют с открытыми источниками: сводками ГИБДД, публикациями на сайтах администраций. 2 Если информация подтверждается, в карту вносят изменения. 1
2. Оценка дорожной ситуации. 2 Обобщённые данные о движении автомобилей на одной дороге сравниваются с данными графа, чтобы сделать вывод о наличии пробок. 1 Загруженность дорог обычно обозначают цветами: зелёный — движение свободное, красный — многокилометровые пробки. 1
3. Проложение пути. 1 После того как пользователь вводит в навигатор точку от пункта А до пункта Б, маршрутизатор прокладывает путь, опираясь на алгоритм Эдсгера Дейкстра — поиска кратчайшего пути в графах. 12 Навигатор строит оптимальный путь, учитывая множество факторов, например, хочет ли человек ехать по платной дороге или будет избегать грунтовых дорог. 1
4. Расчёт времени. 1 Для этого используется модель машинного обучения — CatBoost. 1 Все данные о выбранном пути, включая день недели, наличие пробок и среднюю скорость движения, сравниваются с временем, которое тратили другие люди, двигавшиеся по этому маршруту. 1
5. Постоянное обновление информации. 1 Во время движения система постоянно обновляет информацию, собирая данные о пробках, авариях и других событиях. 1 Поэтому навигатор на ходу может изменить маршрут, чтобы пользователь добрался до места назначения быстрее. 1

Часть факторов нельзя просчитать заранее: аварии, внезапные перекрытия дорог или участки с редким движением, где сложно определить реальную скорость. 2 Даже с учётом таких непредсказуемых факторов точность расчёта остаётся высокой — отклонения от реального времени в пути составляют не более 12%. 2