Маршрутизатор что Это

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

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

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

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

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

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

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