Компания Яндекс — Технологии — Маршрутизация
Десять-пятнадцать лет назад в бардачке каждого водителя лежал атлас дорог. Он и был главным помощником при планировании маршрута. Сейчас вместо атласа люди всё чаще открывают электронные карты или мобильные приложения, и умные алгоритмы сами строят для них наилучший маршрут. Яндекс помогает людям планировать поездки на сервисе maps.yandex.ru, в мобильных приложениях Навигатор и Яндекс.Карты. Технология построения маршрута везде одна и та же, различаются только интерфейсы.Главные составляющие механизма маршрутизации — это дорожный граф и алгоритм, который рассчитывает путь.
Дорожный граф — это сетка дорог. Она состоит из множества фрагментов, которые состыкованы между собой. Например, дорожный граф Саратова (население — около 840 тысяч человек) состоит из 7592 фрагментов. Каждый из них несёт информацию о своём участке дороги: географические координаты, направление движения, средняя скорость, с которой машины обычно едут на этом участке, и другие параметры. Кроме того, каждый фрагмент содержит данные о том, как он стыкуется с соседними участками — есть ли в этом месте поворот направо или налево, можно ли там развернуться в обратную сторону или разрешается ехать только прямо.
Само собой, дорожный граф нельзя сделать раз и навсегда. Транспортная система города имеет обыкновение меняться. Появляются новые дороги и развязки, меняется направление движения. А там, где ещё недавно был поворот, может висеть «кирпич». Чтобы не отставать от жизни, Яндекс регулярно обновляет данные.
Во-первых, постоянно обрабатываются сообщения о неточностях в графе, которые пользователи присылают с помощью мобильных Яндекс.Карт, Навигатора и веб-сервиса Яндекс.Карты. С этими сообщениями работают эксперты Яндекса, которые используют также открытые источники информации о транспортной системе (например, сайты местных администраций).
Во-вторых, для определения неточностей на карте дорог существует специальная система. Она фиксирует все случаи, когда данные о движении машин, которые анонимно передают водители, не совпадают с имеющейся сеткой дорог. Если это не случайный нарушитель, который выехал на газон или развернулся в неположенном месте, возможно, на этом участке изменилась схема движения. Все такие случаи разбираются, и при необходимости в граф вносятся изменения.
Дорожный граф хранится на серверах Яндекса в нескольких экземплярах — если какой-то из серверов будет временно недоступен, маршрутизация все равно будет работать.
Маршрут рассчитывается по алгоритму Дейкстры. С его помощью система вычисляет самый быстрый вариант проезда — исходя из длины каждого отрезка графа и скорости движения на этом участке. Если пользователь строит маршрут проезда без учёта пробок, то алгоритм использует среднюю скорость движения на участке. А если пользователь хочет знать, как быстрее всего добраться до места с учётом ситуации на дороге, то алгоритм задействует данные о текущей ситуации на дороге.Как это происходит, можно разобрать на примере. Представим, что нужно проложить маршрут из точки А в точку B. Алгоритм начинает методично перебирать все возможные варианты. Первым делом он прокладывает маршрут на один шаг (фрагмент графа) во все стороны от точки А. И затем вычисляет, сколько времени потребуется на преодоление этих участков (тут все просто — расстояние делится на скорость). Дальше он выбирает точку, до которой удалось бы добраться быстрее всего. Это точка С.
Затем алгоритм строит маршрут ещё на один шаг — во все стороны от точки С. И снова анализирует, в какую из точек можно было бы попасть быстрее всего. На этот раз это точка D. На следующем шаге алгоритм будет строить маршрут уже от неё.
Продолжая в том же духе, маршрутизатор находит вариант проезда, который оказывается самым коротким по времени.
Особая тема — дворы. Как известно, сквозной проезд через дворы запрещён. Кроме того, на петляния по ним зачастую уходит больше времени, чем на проезд по прямой. Чтобы сервис не строил маршруты через дворы, за них начисляются дополнительные минуты (они не влияют на время в пути, которое видит пользователь). Поэтому в большинстве случаев алгоритм выбирает другие варианты проезда — они занимают меньше времени. Однако если конечная точка маршрута находится во дворе, алгоритму в любом случае придётся туда «въехать».
Построение маршрута происходит очень быстро. Пока вы читаете эти несколько абзацев, сервис уже несколько раз успел бы оплести паутиной маршрутов всю Россию. Чтобы добиться такой скорости, всю карту автоматически поделили на множество областей, для каждой из которых можно посчитать оптимальные варианты её пересечения. Такой областью может быть, например, небольшой городок, через который проходит всего одна междугородняя трасса — въехать и выехать из города можно только по ней. Это значит, что Яндекс может заранее рассчитать оптимальный вариант проезда через этот город.
Если на пути пользователя лежат несколько таких областей, Яндекс просто складывает маршрут из уже готовых кусочков.
Всевозможные варианты проезда внутри каждой области и между ними Яндекс строит заранее — при каждом обновлении графа. Дальше, когда пользователь просит построить маршрут, сервис просто вытаскивает его из памяти. Правда, это срабатывает, только если человеку нужен маршрут без учёта пробок — заранее построенные маршруты рассчитаны на основе средней скорости движения, которая заложена в графе. Если же пользователь хочет построить маршрут с учетом ситуации на дороге и внутри области в данный момент есть пробки, Яндекс построит для него маршрут заново.
yandex.ru
Пользоваться картой — Мобильные Яндекс.Карты. Помощь
На главной странице отображаются:
- Поисковая строка
Поле в нижней части экрана (Поиск мест и адресов).
Нажмите на строку, чтобы перейти к поиску по карте.
- — Голосовой поиск
Кнопка у правого края поисковой строки. Включает ввод информации голосом.
- — Меню
Кнопка слева от поисковой строки. Открывает меню перехода к выбору типа карты, к списку Мои места, к настройкам приложения и к операции добавления дорожного события.
- — Маршруты
Позволяет построить маршрут.
- Выдвижная панель
Выдвижная панель содержит меню быстрого поиска, расположена над поисковой строкой.
Сдвиньте панель вверх, и вы увидите блоки Где есть и пить, Где совершать покупки, Где отдыхать и развлекаться и т. п.
В каждом блоке отображаются превью объектов соответствующей категории. Нажмите на превью, чтобы перейти к карточке объекта.
В каждом блоке есть кнопки фильтрации; нажмите кнопку, и в списке останутся только те объекты, которые отвечают условию фильтрации. Например, по нажатию кнопки Бары и пабы в блоке Где есть и пить вы увидите список именно баров и пабов, расположенных недалеко от вас, а также рекомендуемых сервисом.
Сдвиньте панель вниз, чтобы открыть карту.
- Карта
На главной странице отображается карта вашего региона и кнопки:
Кроме того, вы можете:
Создать списки избранных мест на карте и использовать их при построении маршрутов.
- Перемещать карту. Чтобы посмотреть другой участок карты — сдвиньте изображение в нужном направлении.
Оценить расстояния между объектами с помощью линейного масштаба текущей карты (масштабной линейки):
yandex.ru
Двигаться по маршруту — Мобильные Яндекс.Карты. Помощь
После того как вы выбрали маршрут, нажмите кнопку Поехали.
Приложение начнет отслеживать ваше перемещение по маршруту, используя информацию о вашем местоположении и заданные вами настройки. Вы можете:
При движении приложение:
При движении по маршруту доступна кнопка Меню , которая открывает меню с пунктами:
Пробки — включает и выключает отображение автомобильных пробок;
Обзор — переключает изображение ближайшего участка маршрута на вид всего маршрута целиком. Чтобы вернуться к частичному отображению, нажмите кнопку Продолжить;
Со звуком — включает и выключает звуковое сопровождение маршрута;
Закладки — открывает список Закладки;
Дорожное событие — добавляет дорожное событие;
Настройки — открывает раздел Настройки.
О маневрах, дорожных событиях и камерах.
Для этого включите настройку Дорожные события.
Чтобы предупреждения не только показывались на экране, но и произносились вслух:
Нажмите кнопку Меню .
В открывшемся меню нажмите кнопку Со звуком .
Приложение станет вслух предупреждать о маневрах, дорожных событиях и камерах. Подробнее см. описание настройки Звук.
Чтобы выключить голосовое сопровождение поездки, повторите действия 1 и 2.
При движении приложение может «увидеть» более быстрый вариант маршрута. Оно сразу сообщит об этом.
Нажмите на сообщение, чтобы переключиться на новый маршрут.
Чтобы быстро найти на карте нужные места, которые встретятся по пути:
Нажмите кнопку Поиск .
Вы увидите самые полезные для водителей категории объектов. Выберите нужную.
Или нажмите значок микрофона и скажите вслух, что вы ищете.
Или нажмите значок Ещё… и введите нужное в открывшуюся строку поиска.
Найденные объекты отобразятся на карте значками .
Выберите подходящий объект и нажмите на него. Откроется панель с указанием расстояния до выбранного объекта и графика его работы.
На панели нажмите значок:
Заехать — и выбранная точка будет включена в ваш маршрут.
Сюда — и ваш маршрут будет перестроен до выбранной точки.
Если, построив маршрут, вы решили изменить начальную или конечную точку маршрута:
Нажмите и удерживайте на карте нужную точку — появится контекстное меню.
В контекстном меню выберите пункт:
- — Отсюда: маршрут будет перестроен так, что начнется в выбранной точке;
- — Сюда: маршрут будет перестроен так, что его конечной точкой станет выбранная точка.
yandex.ru