вторник, 15 ноября 2016 г.

Оптимизация маршрутов в Waze.

Сегодня коснемся вопросов on-line  оптимизации маршрутов вейз в том числе некоторых недокументированных возможностей программы.
Вспомним механизм прокладки маршрутов с учетом типов дорог и длины маршрута:


Для маршрутов до 15 километров используются все транзитные типы: Дорога/Street - далее "Стрит", Важная дорога/Primary Street - далее "Праймари", Магистраль/Minor Higway - далее "Минор", Важная магистраль/Major Higway - далее "Мажор" и Автострада/Freeway - далее "Фривей". Для более длинных маршрутов происходит последовательное накладывание пенальти на низшие типы дорог, начиная со стритов, праймари и до миноров. Таким образом, из маршрутов длиной в 15-30 км. из-за пенальти исключаются стриты. В 30-160км. - добавляются пенальти на праймари и после 160-ти - на миноры, что затрудняет их использование в дальней навигации.

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

Приведем пример - маршрут  Иваново-Москва:



Маршрут больше 160-ти километров и построен с использованием мажоров и фривеев.
Теперь посмотрим частные моменты маршрута: обход Гаврилов Яма построен по мажору.

Через город идет минор. На маршруте в 160+ километров она предсказуемо игнорируется.
Похожая ситуация наблюдается на маршруте в районе Переславля-Залесского:


Теперь посмотрим - что будет с маршрутом, если проложить его не от начального пункта, а непосредственно перед этими городами:

Гаврилов Ям:
Переславль-Залесский:


Посмотрим подробнее на последний пример.

Здесь видна разница между синим и красным маршрутами  в 8,12 км и 2 минуты.
Почему же вейз в одном случае строит маршрут в обход, а в другом - через город?

Сразу отмечу пост на официальном форуме от manzareck для тех, кто захочет самостоятельно разбираться в хитросплетениях алгоритмов расчета маршрута, в том числе во взаимодействиях серверов вейза и гугла.

Здесь же отметим, что  маршрут через город был бы предложен, если бы альтернатива экономила не менее 10% оставшегося времени и не меньше чем 4е минуты. Это, так называемое, “правило спящих миноров”. В процессе следования по маршруту возможно “нахождения” более выгодных путей при соблюдении вышеозначенных условий. В тоже время, перестроение маршрута вручную, даст реальную картину альтернатив.
Этот механизм навигации вейз можно и нужно учитывать в повседневных поездках. Конечно это особенно касается длинных (более 160 км.) дистанций.

Таким образом, существует определенная интрига в определении местных и транзитных маршрутов. Последние учитывают “высшие” типы дорог и “не размениваются” на частности (местные возможности оптимизации). Все местные же трассы не могут и не должны учитываться при дальней навигации.

Представляется, что механизм “спящих миноров” является некоторым связующим звеном между этими двумя типами навигации: маршрут строится сначала в первом приближении (и нужно следить, чтобы это “приближение” было адекватным  через присвоение нужным трассам высших типов дорог). Однако в движении вейз своими алгоритмами постоянно отслеживает “местные” трассы и при необходимости предлагает новый - “лучший” маршрут. И уже от вейзера зависит полагаться на встроенный механизм, или при необходимости, “принимать управление на себя”-  прокладывая маршрут заново.


Еще момент - процесс актуализации данных (через каждые 8 минут) для пересчета маршрута происходит только в случае выбора маршрута “по умолчанию”. Если же был выбран какой-нибудь альтернативный вариант маршрута, то он останется без изменений до своего завершения. Только в случае съезда с маршрута или опять же - ручной перестройки возобновится периодическое отслеживание онлайн данных для целей оптимальной маршрутизации.


Всем удачи на дорогах с Waze!