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

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

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

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

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

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

4

Спасибо! Все стало понятно! А может Вы еще знаете, учитывают ли навигаторы светофоры и время, затрачиваемое на ожидание зеленого?

0
Ответить

Трудно сказать. Если вес ребра графа измерять в среднем времени проследования этого ребра, то время на светофоре учтётся автоматически. Математически ведь пробок не существует, есть время, необходимое для преодоления пути.

Ещё есть вариант считать равновероятным встретить зелёный и красный сигнал светофора, посчитать количество светофоров на пути, поделить пополам и умножить на среднее время ожидания. Если предположить, что среднее время ожидания — 30 секунд, то каждые четыре светофора увеличат время в пути на минуту. Фазы светофоров непостоянны, а вероятность попасть к началу красного сигнала не равна единице, поэтому учитывать точное время ожидания трудно и незачем.

0
Ответить
Прокомментировать
Ответить