О приоритете маршрутизации и "засыпающих" типах дорог

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

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

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

Как конкретно организован этот процесс внутри - два прохода, или больше, с рекурсией, или без - трудно установить. Говорят, для маршрутов свыше 1000 км пытается склеивать из нескольких, но сверхдлинные маршруты это отдельный вопрос. 

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

На эту тему есть статья: "Оптимизация маршрутов в Waze." http://shomgoon.blogspot.com/2016/11/waze.html 

Приведу табличку из неё. Откуда бы Влад её не взял, на неё можно ориентироваться для общего понимания происходящего.

Есть ещё одна его статья на тему "О логике маршрутизации Waze" http://shomgoon.blogspot.com/2014/10/waze.html

По сути в них написано всё то же самое, что и тут, но нужно сделать несколько важных замечаний. То, что Waze использует систему штрафов - это такое общее знание. В конкретном применении это может проявиться в том, что более быстрый маршрут окажется в списке не первым из-за накинутого на него штрафного времени, но всё же он будет просчитан. Но для оптимизации процесса построения лишние маршруты надо откидывать не считая. Это не оптимизация в смысле поиска лучшего маршрута. Это оптимизация самой процедуры построения, чтобы снизить затраты и считать быстрее. Как побочный эффект, маршрут в результате может оказаться хуже. Для того и приходится погружаться в вопрос, чтобы знать, как избегать этих побочных эффектов.

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

В современной Wiki на данный момент написано "Major Highway is never pruned", как и про Ramp и про Freeway, и что нет смысла поднимать тип до Freeway из одних лишь соображений неразрывности.

Если отбросить оговорки о штрафах, статьи хороши и очень ценны. Наличие конкретных примеров позволяет сделать самое важное - проверить, что всё работает именно так, как описано. Либо, если механизмы когда-нибудь изменятся, увидеть, что что-то изменилось.

Проверим на маршруте Иваново-Москва. Около Плещеева озера есть объезд по мажору и есть более короткий прямой проезд по минору. 

Прямой участок может в какое то время суток оказаться не только короче, но и быстрее, чем объезд

Но на дальнем маршруте он будет выпадать всегда. Из-за дальности работает только объезд по мажору.

Попробуем прощупать, в каком месте эффект будет пропадать. 

Сдвигаем точку старта. Ростов, Московское шоссе - эффект ещё есть

Двигаем точку старта чуть ниже, где Песочное - эффект пропадает.

Ссылка на маршрут

Специально для руспид-диссидентов, проверяю в мобильном приложении. Лишняя проверка не повредит, хотя, если делать это сидя на диване, то  принципиальной разницы нет. Другой вопрос, если проверять в клиенте в движении, насколько отрабатывается перестроение в динамике, "просыпаются" ли при этом низшие типы. Это отдельный вопрос.

 

Можно найти на карте такие места, где засыпающей и просыпающейся перемычкой окажется Primary street. Город Великий Новгород. Объезд по мажору, который можно срезать.

 

Маршрут покороче, Воробейка - Ямно, срезает по Primary Street

Немного растягиваем маршрут, начинает объезжать

Эффект снижения типа может привести и к гораздо более длинному объезду.

Сейчас можно сравнить между собой маршруты Рамцы - Фралёво и Рамцы - Ям-Тёсово. В дальнейшем эту ситуацию придётся исправить, но сейчас это выглядит так: участок Вдицко - Апраксин Бор опущен до Primary street. Там грунтовка, и что с ними делать это отдельная тема. Раньше приходилось понижать тип, поскольку не существовал отдельный признак для грунтовок.

Видим, что до какого-то предела маршрут строится через короткий участок, где Primary street, оказывается втрое короче и на час с лишним быстрее, но оптимальным признаётся объезд, поскольку мы избегаем грунтовки. Это добавляет больше часа штрафного времени, поскольку чередуются несколько участков грунта и асфальта. Грунтовки это отдельная тема, пока что смотрим на типы дорог.

Более длинный маршрут перестаёт видеть и оценивать primary street

Это по сути всё, чем является "приоритет маршрутизации", routing priority. Дальность, и только дальность. Непроверенные выдумки про штрафы, или какой-то другой, отдельный от описанного тут, приоритет типа дороги - ничего из этого практикой не подтверждается. Однако, из-за этих непроверенных предположений в некоторых городах совершенно не по назначению и в большом количестве назначен тип major highway.

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