Что такое дорожный граф и как строятся маршруты на Яндекс.Картах

Команда Яндекс.Карт рассказала, как работает маршрутизация на Яндекс.Картах.

Напоминаем, вчера было объявлено масштабное обновление Яндекс.Карт — на них появились подробные схемы большинства стран мира:

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

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

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

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

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

Подробнее о построении маршрутов читайте в блоге Яндекса

Журналист, новостной редактор, работает на сайте с 2009 года. Специализация: интернет-маркетинг, SEO, поисковые системы, обзоры профильных мероприятий, отраслевые новости рунета. Языки: румынский, испанский. Кредо: Арфы нет, возьмите бубен.