Как это работает? Маршрутизация на Яндекс.Картах

13 ноября 2013, 12:59

Вчера мы объявили о масштабном обновлении Яндекс.Карт — на них появились подробные схемы большинства стран мира. За этим проектом стоит не просто нанесение на карту новых объектов, но прежде всего технологическая основа, которая позволяет хранить, быстро обрабатывать и обновлять эти данные. В Яндекс.Картах вообще немало интересных технологий, и сегодня мы хотим рассказать об одной из них — технологии построения маршрутов.

Десять-пятнадцать лет назад в бардачке каждого водителя лежал атлас дорог. Он и был главным помощником при планировании маршрута. Сейчас вместо атласа люди всё чаще открывают электронные карты и мобильные приложения. И умные алгоритмы сами строят для человека наилучший маршрут. Яндекс помогает людям планировать поездки на сервисе maps.yandex.ru, в мобильных приложениях Навигатор и Яндекс.Карты. Технология построения маршрута везде одна и та же, различаются только интерфейсы.

Главные составляющие маршрутизации — это дорожный граф и алгоритм, который рассчитывает маршрут.

Что такое граф

Дорожный граф — это сетка дорог. Она состоит из множества фрагментов, которые состыкованы между собой. Например, дорожный граф города Саратова (население — около 840 тысяч человек) состоит из 7592 фрагментов. Каждый из них несёт информацию о своём участке дороги: географические координаты, направление движения, средняя скорость, с которой машины обычно едут на этом участке, и другие параметры. Каждый фрагмент содержит также данные о том, как он стыкуется с соседними участками — есть ли в этом месте поворот направо или налево, можно ли там развернуться в обратную сторону или разрешается ехать только прямо.

Само собой, дорожный граф нельзя сделать раз и навсегда. Транспортная система города имеет обыкновение меняться. Появляются новые дороги и развязки, меняется направление движения. А там, где ещё недавно был поворот, может висеть «кирпич». Чтобы не отставать от жизни, Яндекс регулярно обновляет данные.

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

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

Дорожный граф хранится на серверах Яндекса в нескольких экземплярах — если какой-то из серверов будет временно недоступен, маршрутизация все равно будет работать.
 

Как строится маршрут

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

Как это происходит, можно разобрать на примере. Представим, что нужно проложить маршрут из точки А в точку B. Алгоритм начинает методично перебирать все возможные варианты. Первым делом он прокладывает маршрут на один шаг (фрагмент графа) во все стороны от точки А. И затем вычисляет, сколько времени потребуется на преодоление этих участков (тут все просто — расстояние делится на скорость). Дальше он выбирает точку, до которой удалось бы добраться быстрее всего. Это точка С.


Затем алгоритм строит маршрут ещё на один шаг — во все стороны от точки С. И снова анализирует, в какую из точек можно было бы попасть быстрее всего. На этот раз это точка D. На следующем шаге алгоритм будет строить маршрут уже от неё.


Продолжая в том же духе, маршрутизатор находит вариант проезда, который оказывается самым коротким по времени.

Особая тема — дворы. Как известно, сквозной проезд через дворы запрещён. Кроме того, на петляния по дворам зачастую уходит больше времени, чем на проезд по прямой. Чтобы сервис не строил маршруты через дворы, за них начисляются дополнительные минуты (они не влияют на время в пути, которое видит пользователь). Поэтому в большинстве случаев алгоритм выбирает другие варианты проезда — они занимают меньше времени. Однако если конечная точка маршрута находится во дворе, алгоритму в любом случае придётся туда «въехать».

Построение маршрута происходит очень быстро. Пока вы читаете эти несколько абзацев, сервис уже несколько раз успел бы оплести паутиной маршрутов всю Россию. Чтобы добиться такой скорости, всю карту автоматически поделили на множество областей, для каждой из которых можно посчитать оптимальные варианты её пересечения. Такой областью может быть, например, небольшой городок, через который проходит всего одна междугородняя трасса — въехать и выехать из города можно только по ней. Это значит, что Яндекс может заранее рассчитать оптимальный вариант проезда через этот город.

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

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

 

24 комментария
Подписаться на комментарии к посту

А маршрут не проверяет первоначально более дорогие маршруты?

 

То есть если бы от точки А направо было 2 минуты и дальше на право ещё раз 1, то вариант привёл бы в конечную точку за 4, что дешевле, чем всегда дешевые переходы.

 

"Лучше день потерять, потом за пять минут долететь."

Проверяет, посмотрите на предпоследний кадр анимации.

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

2GIS еще не думали купить?
©ШвЕц АрTёМ
13 ноября 2013, 18:25
А что нужно, что бы появился подробный граф в населенном пункте? Мог бы сам нарисовать! ;-)
©ШвЕц АрTёМ,


тут можно нарисовать самому
https://n.maps.yandex.ru

Можно ли строить маршрут с учётом пробок не текущих, а на _момент прибытия туда_ ? Иными словами исходя из предсказанных пробок.
 
В Новосибирске ехали - было два варианта поездки через два моста. Один красный, другой зелёный. К моменту, когда подъехали к зелёному мосту, он тоже стал красным - лучше бы ехали через первый, не делали бы значительный крюк по пробкам и на мосте и на подъездах/съездах с него. Дело было вечером около 18 часов, без ДТП на мосту. Это типичная ситуация на мосту вечером - и яндекс.пробки это знали, если посмотреть нужный час и день недели.


Разбить карту на несколько областей от точки старта до точки финиша. И в эти области подставлять статистические данные от пробок,  обычная ситуация на это время в этот день недели. 0-15 мин - текущая ситуация. 15-30 мин , 30-45 мин и т.д.- предсказанная ситуация. В первом приближении первая область это круг, последующие области это кольца. Если по вершинам графа рассчитывать точное время доставки, то форма областей более сложная и просчитывается на ходу прокладывания маршрута по графу.

Учитывать, что если обычно в этом месте в это время зелёная дорога, но на данный момент красная, скорее всего там ДТП не предусмотренное статистикой - и считать ситуацию в будущем на этом участке по текущему состоянию (если не превышается среднее время, за которое последствия аварии обычно исчезают).

яндекс мне не ответил :-(

По-прежнему не вижу в прокладке маршрута варианта "пешком" :(

Ну вон у конкурентов есть — а толку, если оно не очень понимает, как человек пешком переходит улицу?

Слава богу, переходить недавно научилось )

Как не понимает? Есть переходы, подземные и наземные. Разумеется, не стоит учитывать "перебежать где попало".

Вот мне абсолютно не интересны автомобильные маршруты, а пешковые - очень даже. А нету.

Да я сам, в общем-то, пешеход )

А понимает — через раз. Попробуйте, например, проложить маршрут от Новинского, 7, до Новинского, 12. Либо, наоборот, он уверен что Тверскую можно перейти на Триумфальной на внутренней стороне кольца, а на деле там крюк через всю площадь надо заложить

В целом, конечно, лучше, чем полгода назад, но до юзабельной системы далеко.

Оно и понятно — актуально картографировать переходы — то еще развлечение )

если у МЯК и навигатора отличаются только интерфейсы, то зачем было делать две разные программы? не проще было в главном меню предложить выбрать, какой интерфейс открыть - карт или навигатора?

Так вот почему маршрут так коряво строится!

Надо не скорость учитывать, а время. Разница между скоростями 1 и 2 км/ч - гигантская, а разница между скоростями 90 и 100 км/ч - незначительная.
Если рассчитывать время, а не скорость, то точность данных будет выше там, где она нужна выше. Да, всего лишь обратная величина, но результат поразительный.

Кроме того, среднее время проезда ребра зависит от некоторых параметров, которые вы, похоже, не учитываете:
1. Время и направление движения по ребру. Если нет данных о пробках надо брать статистические значения с учётом времени, направления, возможно погоды и данных по пробкам на некоторых других рёбрах графа. У вас, похоже, это не реализовано.
2. Следующее ребро графа (так называемые пробки 3.0 у СитиГида). Это моё личное изобретение. У СитиГида оно работает не идеально в виду малого количества датчиков. Но всё же оно существенно улучшило прокладку маршрута.
Поясню: иногда одно ребро графа в одном и том же направлении в одно и то же время автомобили проезжают за существенно различное время.
Например если вы проезжаете по МКАД прямо со скоростью 110 км/ч, ваше время на нём существенно отличается от времени того человека, который стоит в очереди на съезд с МКАДа. Более того, он подъезжал к повороту с заведомо меньшей скоростью, то есть даже на свободном повороте ехал по ребру дольше.

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

И так далее. Математики у вас - отличные. Но в команде обязательно нужен кто-то, кто додумается как адаптировать абстрактные мат. модели к реальной жизни, чтобы задачи решались действительно красиво!
Шевнин Владимир
21 ноября 2013, 22:29

Всегда было интересно как вы строите маршруты.

Примерно догадывался, но вот что меня интересует - учитываете ли вы повороты.

В комментариях уже предложили "плясать" от времени. Очень часто система неучитывает время на повороты.

Грубо говоря - если у вас левый поворот а в обе стороны пробка - то влияние поворота сильно увеличивается. Я надеюсь идея понятна.

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

По сути у в ваш граф добавляется еще количество поворотов и их весовая оценка, а на оценку может влиять тип повортота/перекрестка и загруженность дорог на подъезде к перекрестку

Не учитывают они ничего такого. Вообще. Просто жирным трассам добавлен коэффициент, чтобы по мелочам не объезжали.
В этом можно легко убедиться, на практике. Меня, например, Яндекс почти всегда ведёт не оптимальным путём из-за пробок, которые собираются из-за поворачивающих. В результате Яндекс просто объезжает "пробку", которой для моего ряда почти нет.

Я уж не говорю о том, что при маршрутизации Яндекс почти не различает красный и "совсем красный" цвета ))))
вопрос немного не по теме: а почему это колесо мышки теперь крутит карту в обратном направлении? это можно как то поменять? я уже привык крутить как раньше - вперед - приближение, назад - отдаление.
Возможно ли прокладывать маршрут сразу через несколько точек ? ( Две как то маловато)
не могу скачать полную карту Москвы на 1,91Гб.
пишет - ошибка сервера или подобное.
обычную карту скачал, но там нет того дома куда надо ехать сегодня, на сайте карт яндекса дом указан, в навигаторе нет.
Можно ли где-то скачать полную версию через компьютер и затем загрузить в смартфон?
По народной карте маршрут строится?
Было бы удобно строить маршрут через несколько адресов точки АБСДЕ столько сколько надо
как построить маршрут пешком?