Ответить
Виктория Райнеш
август 2015.
478

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

Ответить
Комментировать
0
Подписаться
1
1 ответ
Поделиться

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

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

Иногда учёт пробок в навигаторах приводит к курьезным результатам. Например, прошлым летом Яндекс-навигатор предложил мне доехать из Митина в Соколово не напрямую по Пятницкому шоссе (yandex.ru), а в объезд пробок по скорейшему маршруту. Скорейшим по мнению Яндекса был такой маршрут: Митино — МКАД — Волоколамское шоссе до Красногорска — Ильинское шоссе до Новорижского — Новорижское шоссе до поворота на Павловскую слободу — оттуда на А107 («малую бетонку») до пересечения с Пятницким шоссе, далее прямо до Соколова. То есть проехать 73 километра за 1:47 было лучше, чем 38 километров за 2 часа.