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