Как Waze рассчитывает маршруты

From waze
Jump to: navigation, search

Навигация на стороне клиента

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

Предположения

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

Запрос на маршрут

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

Результат запроса на расчёт маршрута зависит от настроек, установленных на вашем клиентском приложении Waze. В настройках навигации можно выполнить следующие установки:

  • Выбирать самый быстрый или короткий маршрут.
  • Разрешать участие грунтовых дорог в маршруте, никогда не разрешать или избегать длинных грунтовых дорог.
  • Выбирать маршруты с наименьшим количеством поворотов.
  • Избегать шоссе.
  • Сбор бонусов.

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

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

Отсутствующие дороги и неправильные соединения дорог

Waze пытается найти самый быстрый маршрут между вами и пунктом назначения. Естественно Waze может прокладывать маршруты только по тем дорогам, про которые знает. Это означает, что ваш маршрут может быть не оптимальным, если лучший путь содержит неправильные соединения дорог или не имеет на карте Live Map некоторых дорог вообще.

Текущие скорости дорог в режиме реального времени

Мы можем быть уверены в том, что данные о средней скорости дорог, полученные от пользователей в текущий момент времени, предпочтительней для вычислений Waze, чем данные, записанные ранее. Мы знаем, что Waze использует отчёты об автомобильных пробках, чтобы объезжать медленные дороги. Ранние версии клиентского приложения также сообщали о том, где в текущий момент времени скорости автомобильных потоков нормальные, но это было убрано, чтобы не загромождать карту. Тем не менее, Waze всё также получает эту информацию. Мы можем предположить, что скорость любого вэйзера, находящегося впереди вас на вашем маршруте, будет взята за основу при вычислении вашего маршрута.

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

Для вычисления скорости дорог вашего маршрута Waze использует именно то время, когда вы ориентировочно будете перемещаться по этим участкам дороги, поэтому Waze не использует текущие скорости дорог для тех участков, которые вы будете проезжать в среднем через 15 минут. Это означает, что в момент расчёта маршрута Waze не знает, что будет в реальности происходить на дорогах через 30 минут, и естественно для вычислений будет брать исторические данные о скоростях. Как только вы перейдёте в следующий временной интервал и Waze получит новые данные о текущих скоростях, может произойти пересчёт маршрута и/или времени до прибытия.

Самый быстрый маршрут

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

Хотя каждый запрос на маршрут рассчитывается в реальном времени на сервере, наблюдения показали, что иногда Waze кэширует некоторые маршруты. Это означает, что если клиентское приложение уже знает лучший маршрут из B в C, а необходимо проложить из A в C, то Waze может просто рассчитать лучший путь из A в B, естественно, если нет более оптимального маршрута без участия B. Поэтому после обновления карты некоторые маршруты могут быть менее оптимальны в течении дня по причине кэширования.

Изменения в маршрутах из-за разных стартовых мест

Представьте расчёт маршрута из А в Z. Предложенный маршрут может быть таким: A->B->C->D->Z. Теперь рассмотрим расчёт маршрута от B к Z: Waze может предложить маршрут B->C->E->Z. На первый взгляд этот маршрут кажется не оптимальным.

Но можно понять почему так происходит. Например, это может быть связано с кэшированием. Или проблемой временных интервалов: другое время прибытия к C может изменить лучший маршрут к Z. Или это некая оптимизация маршрута с целью, к примеру, минимизации количества поворотов. И поэтому исключение участка A->B позволяет участкам C->E->Z более не превышать какой-то определенный показатель и быть более лучшим путём.

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

Проблемы связанные со средними скоростями

Если средняя скорость дороги неправильная, значит маршрут будет не оптимальным. Далее рассмотрены ситуации, когда использование среднего времени для вычисления маршрута оказывается неправильным.

Разное время суток

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

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

Решение этой проблемы - большее количество вэйзеров.

Время на повороты

Представьте дорогу длиной 1км, по которой вы едете прямо, проезжая её и перекресток в конце на скорости 100км/час за 36 секунд. А теперь представьте, что на перекрестке вам необходимо повернуть налево, и это занимает целых 5 минут. В первом случае ваша средняя скорость будет 100км/час, во втором - всего 11км/час.

Если 9 из 10 вэйзеров проедут по такой дороге прямо, то средняя скорость дороги получится 91км/час. Waze будет рекомендовать эту дорогу, даже если в конце вам необходимо повернуть налево.

Или наоборот: 9 из 10 вэйзеров пытаются сделать этот пятиминутный поворот налево, формируя среднюю скорость для дороги равную 20км/час. И даже если вам в конце этой дороги необходимо ехать прямо (а значит, ваша скорость будет 100км/час), Waze будет пытаться объехать эту дорогу, так как знает, что её средняя скорость - 20км/час.

Мы можем предположить, что Waze известно об этой проблеме. В крайнем случае вы можете выбрать опцию "Избегать поворотов" или же действовать на своё усмотрение. Хорошая новость заключается в том, что у Waze накапливается достаточно информации, чтобы решить эту проблему: есть средние скорости вэйзеров, которые едут налево, и тех, кто едет прямо. Эти данные могут применяться для вычисления вашего маршрута. Это сделает расчёт более сложным, но это возможно.

На текущий момент это не реализовано.

Правка дорог в редакторе Cartouche

Средняя скорость при редактировании дорог в Cartouche не изменяется, хотя время, за которое её проезжают, изменяется пропорционально длине. После изменения размера участка дороги, его средняя скорость может оказаться неправильной, например, по причине ограничений скорости или поворотов.

Светофоры и знаки "STOP"

Waze не сохраняет информацию о расположении светофоров. И хотя некоторые GPS навигаторы содержат эти данные, в большинстве случаев она далеко не полная, неправильная или устаревшая.

И хотя Waze не учитывает светофоры и знаки "STOP" это достаточно заметно влияет на скорость движения. Представьте светофор с очень большим интервалом красного света. Участок дороги ведущий к этому светофору будет иметь небольшую среднюю скорость. И если из-за светофора средняя скорость станет совсем маленькой, Waze предложит более длинный путь, но без светофора. Это было неоднократно замечено вэйзерами. Хотя навигация Waze не запрограммирована для объезда светофоров, она будет избегать медленных дорог. И если светофор делает дорогу медленной, Waze будет предлагать объехать её.

Некоторые водители часто ездят длинными объездными маршрутами, чтобы избегать любых остановок и светофоров. Было замечено, что Waze в таких случаях начинает предлагать другим водителям эти маршруты, но через некоторое время, когда более правильная средняя скорость "объездных улочек" становится доступной, Waze возвращает водителей на более оптимальную дорогу со светофорами.

Устаревшие или аномальные скорости дорог

Различные факторы могут повлиять на изменение средней скорости участка дороги, например, изменение качества дорожного покрытия или ремонт дороги; в один день вы ехали за грузовиком, в другой день ночью вы очень медленно транспортировали свою золотую рыбку в аквариуме, или же ваш GPS начал сбоить.

Средние скорости иногда могут изменятся на совершенно неправильные и оставаться такими на долгое время.

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

Временные интервалы средних скоростей

Если накапливается достаточное количество скоростей дороги, Waze начинает распределять скорости по временным интервалам, чтобы более оптимально рассчитывать маршруты в разное время суток. Waze использует тридцатиминутные интервалы для каждого из направлений. Значит, максимальное количество средний скоростей для обычной дороги - 96 штук. Мы можем предположить, что если количество скоростей недостаточно для отдельного временного интервала, будут выбраны сразу несколько интервалов, вплоть до целого дня. С увеличением количества записанных скоростей, будет выделятся всё больше временных интервалов.

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

Таким же образом Waze следует учитывать месяцы года, так как автомобильные потоки меняются в разное время года.

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

Именно благодаря временным интервалам Waze будет предлагать разные маршруты в разное время суток. Но всё зависит от количества записанных скоростей и времени их записи: если 1000 скоростей записано около 5 вечера и 2 скорости в 10 часов утра, то ваш маршрут утром скорее всего будет основан на вечерних данных.

Пенальти соединений

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

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

Данная проблема может иметь несколько решений. Например, пенальти может не применяться в следующих случаях:

  • Соединения не имеют реальных перекрестков.
  • Соединения между двумя дорогами с одинаковым названием.
  • Дорога, по которой вы перемещаетесь, старшего класса, чем примыкающие.
  • Или, когда вы едете по шоссе.

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

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

Что делать, если рассчитанный маршрут не оптимален

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

Во-вторых, если вы считаете, что есть лучший маршрут, перепроверьте все его соединения и разрешённые повороты.

В-третьих, оставьте сообщение на форуме или на форуме русскоязычного сообщества, в разделах навигации, не забудьте указать места старта и назначения, а также permalink в Cartouche. Свежий взгляд других вэйзеров может помочь найти ошибки на карте. Их исправление будет полезным и для остальных.

Изменения в маршруте

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

Может быть и так, что даже после получения информации об ухудшении скорости, Waze не предложит нового маршрута, потому что в данный момент лучше текущего нет.

Вы - водитель

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

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