Когда вы пользуетесь навигатором, вы указываете точку А и точку Б, и дальше навигатор как-то сам строит маршрут. Сегодня посмотрим, что лежит в основе алгоритма, который это делает. Просто ради интереса.
Графы и «задача коммивояжёра»
Ещё до появления навигаторов у людей была такая же проблема: как найти кратчайший путь из одного места в другое, если есть ограниченное количество промежуточных точек? Или как объехать ограниченное количество точек, затратив минимальные усилия. В общем виде это называется «задачей коммивояжёра», и мы уже рассказывали, в чём там идея:
- есть несколько городов, и мы знаем расстояния между двумя любыми городами;
- в классической задаче нельзя дважды заезжать в один и тот же город, но в жизни — можно;
- если городов мало, то компьютер справится с задачей простым перебором, а если их больше 66 — то уже нет;
- кроме расстояния, иногда важно учесть время, комфорт и общую длительность поездки;
- есть много приблизительных алгоритмов, которые дают более-менее точный результат.
Если взять просто города и расстояния между ними, то с точки зрения математики это называется графом: города будут вершинами графа, а дороги между ними — рёбрами графа. Если мы знаем длину каждой дороги, то это будет значением (весом) рёбер графа. Этой теории нам уже хватит, чтобы понять, как работает навигатор в машине.
MAPS.ME — бесплатные офлайн карты, навигация и маршруты.
Алгоритм Дейкстры — ищем самый быстрый путь
Как только появилось решение полным перебором, математики стали искать другой подход, который работал бы гораздо быстрее и не требовал бы вычисления такого огромного объёма данных. В 1959 году Эдсгер Дейкстра придумал свой алгоритм, которым пользуются до сих пор. Идея его в том, чтобы не перебирать все варианты, а находить самый короткий путь только между соседними графами — и так, шаг за шагом, продвигаться к конечной точке.
Допустим, у нас есть улицы, перекрёстки и мы знаем время пути между ними. Нарисуем это в виде графа, а чтобы было проще ориентироваться — сделаем визуально всё одинаковой длины:
Чтобы найти самый быстрый путь из А в Б, мы смотрим сначала, какие пути у нас выходят из точки А. Видно, что поехать вниз будет быстрее, чем поехать направо:
Значит, выбираем путь вниз. Теперь делаем то же самое для этой точки — смотрим, где быстрее: справа или внизу. Вниз быстрее (1 меньше, чем 4), поэтому едем по ней:
КАК СДЕЛАТЬ АНИМИРОВАННУЮ КАРТУ МАРШРУТА?
При этом мы не отбрасываем уже сделанные вычисления (всё равно уже посчитали), а запоминаем их на всякий случай. Из нижней точки есть только одна дорога — направо, поэтому едем по ней:
А теперь у нас получилась интересная ситуация: в центральную точку мы можем попасть как сверху, так и снизу, при этом и там, и там у нас одинаковое время — 3 минуты. Значит, посчитаем оба варианта — вдруг сверху будет быстрее и нам нужно будет перестроить маршрут заново:
Оказывается, снизу ехать до центра быстрее, чем сверху — 4 минуты вместо 6, поэтому оставляем нижний маршрут. Наконец, из центральной точки до точки Б всего один путь — направо, поэтому выбираем его:
Как видите, нам не пришлось считать все варианты со всеми точками, а до некоторых мы просто не добрались. Это сильно сэкономило время и потребовало меньше ресурсов для вычисления.Такой алгоритм и лежит в основе автомобильных навигаторов — с вычислениями справится даже бюджетный смартфон.
Что ещё учитывает навигатор
Чтобы алгоритм оставался простым и работал только со временем, все остальные параметры дорог тоже привязывают ко времени. Покажем, как это работает, на паре примеров.
Комфорт. Если нам нужно построить не самый быстрый, а самый комфортный маршрут, то мы можем отдать предпочтение автомагистралям и дорогам с несколькими полосами — на них обычно и асфальт получше, и резких поворотов поменьше. Чтобы навигатор выбирал именно такие дороги, им можно присвоить коэффициент 0,8 — это виртуально сократит время на дорогу по ним на 20%, а навигатор всегда выберет то, что быстрее.
С просёлочными и грунтовыми дорогами ситуация обратная. Они редко бывают комфортными, а значит, им можно дать коэффициент 1,3, чтобы они казались алгоритму более долгими и он старался их избегать. А лесным дорогам можно поставить коэффициент 5 — навигатор их выберет, только если это единственная дорога то точки назначения.
Сложность маршрута и реальное время. Маршрут из А в Б почти никогда не бывает прямым — на нём всегда есть повороты, развороты и съезды, которые отнимают время. Чтобы навигатор это учитывал, в графы добавляют время прохождения поворота — либо коэффициентом, либо отдельным параметром. Из-за этого алгоритм будет искать действительно быстрый маршрут с учётом геометрии дорог.
Пробки. Если есть интернет, то всё просто: навигатор получает данные о состоянии дорог и добавляет разные коэффициенты в зависимости от загруженности. Иногда навигатор ведёт дворами, когда трасса свободна — это не ошибка навигатора, а его прогноз на время поездки: если через 10 минут в этом месте обычно собираются пробки, то там лучше не ехать, а заранее поехать в объезд.
Если интернета нет, то алгоритм просто использует усреднённую модель пробок на этом участке. Эта модель скачивается заранее и постоянно обновляется в фоновом режиме.
Как построить маршрут по всей России
Если нам нужно построить маршрут из Брянска в Тулу, то с точки зрения компьютера это безумно сложная задача: ему нужно перебрать десятки тысяч улиц и миллионы перекрёстков, чтобы понять, какой путь выбрать. С этим плохо справляется даже обычный компьютер, не говоря уже о телефоне.
Если мы в Яндекс Картах построим такой маршрут, то навигатор нам предложит сразу 4 варианта:
Но мы не ждали полчаса, пока сервер на той стороне посчитает все перекрёстки, а получили результат через пару секунд. Хитрость в том, что алгоритм использует уже заранее просчитанные варианты маршрутов и подставляет их для ускорения.
Например, если мы поедем в Тулу не из Брянска, а из Синезёрок, то поменяется только начальный маршрут по трассе М3, а всё остальное останется прежним:
Получается, что навигатору не нужно всё пересчитывать — он находит только ключевые точки пути, а маршрут между ними уже просчитан до этого. Этот приём работает и при перестроении маршрута во время движения: навигатор смотрит, как нужно поменять путь, чтобы вернуть вас на уже известную дорогу.
Что дальше
Следующий этап — напишем алгоритм Дейкстры сами и посмотрим, как он работает по шагам.
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Источник: thecode.media
Как это работает? Маршрутизация на Яндекс.Картах
Вчера мы объявили о масштабном обновлении Яндекс.Карт — на них появились подробные схемы большинства стран мира. За этим проектом стоит не просто нанесение на карту новых объектов, но прежде всего технологическая основа, которая позволяет хранить, быстро обрабатывать и обновлять эти данные. В Яндекс.Картах вообще немало интересных технологий, и сегодня мы хотим рассказать об одной из них — технологии построения маршрутов.
Десять-пятнадцать лет назад в бардачке каждого водителя лежал атлас дорог. Он и был главным помощником при планировании маршрута. Сейчас вместо атласа люди всё чаще открывают электронные карты и мобильные приложения. И умные алгоритмы сами строят для человека наилучший маршрут.
Яндекс помогает людям планировать поездки на сервисе maps.yandex.ru, в мобильных приложениях Навигатор и Яндекс.Карты. Технология построения маршрута везде одна и та же, различаются только интерфейсы.
Главные составляющие маршрутизации — это дорожный граф и алгоритм, который рассчитывает маршрут.
Что такое граф
Дорожный граф — это сетка дорог. Она состоит из множества фрагментов, которые состыкованы между собой. Например, дорожный граф города Саратова (население — около 840 тысяч человек) состоит из 7592 фрагментов. Каждый из них несёт информацию о своём участке дороги: географические координаты, направление движения, средняя скорость, с которой машины обычно едут на этом участке, и другие параметры. Каждый фрагмент содержит также данные о том, как он стыкуется с соседними участками — есть ли в этом месте поворот направо или налево, можно ли там развернуться в обратную сторону или разрешается ехать только прямо.
Само собой, дорожный граф нельзя сделать раз и навсегда. Транспортная система города имеет обыкновение меняться. Появляются новые дороги и развязки, меняется направление движения. А там, где ещё недавно был поворот, может висеть «кирпич». Чтобы не отставать от жизни, Яндекс регулярно обновляет данные.
Во-первых, постоянно обрабатываются сообщения о неточностях в графе, которые пользователи присылают с помощью мобильных Яндекс.Карт, Навигатора и веб-сервиса Яндекс.Карты. С этими сообщениями работают эксперты Яндекса, которые используют также открытые источники информации о транспортной системе (например, сайты местных администраций).
Во-вторых, для определения неточностей на карте дорог существует специальная система. Она фиксирует все случаи, когда данные о движении машин, которые анонимно передают водители, не совпадают с имеющейся сеткой дорог. Если это не случайный нарушитель, который выехал на газон или развернулся в неположенном месте, возможно, на этом участке изменилась схема движения. Все такие случаи разбираются, и потом изменения вносятся в граф.
Дорожный граф хранится на серверах Яндекса в нескольких экземплярах — если какой-то из серверов будет временно недоступен, маршрутизация все равно будет работать.
Как строится маршрут
Маршрут рассчитывается по алгоритму Дейкстры. С его помощью система вычисляет самый быстрый вариант проезда — исходя из длины каждого отрезка графа и скорости движения на этом участке. Если пользователь строит маршрут проезда без учёта пробок, то алгоритм использует среднюю скорость движения на участке. А если пользователь хочет знать, как быстрее всего добраться до места с учётом ситуации на дороге, то алгоритм задействует данные о текущей ситуации на дороге.
Как это происходит, можно разобрать на примере. Представим, что нужно проложить маршрут из точки А в точку B. Алгоритм начинает методично перебирать все возможные варианты. Первым делом он прокладывает маршрут на один шаг (фрагмент графа) во все стороны от точки А. И затем вычисляет, сколько времени потребуется на преодоление этих участков (тут все просто — расстояние делится на скорость). Дальше он выбирает точку, до которой удалось бы добраться быстрее всего. Это точка С.
Затем алгоритм строит маршрут ещё на один шаг — во все стороны от точки С. И снова анализирует, в какую из точек можно было бы попасть быстрее всего. На этот раз это точка D. На следующем шаге алгоритм будет строить маршрут уже от неё.
Продолжая в том же духе, маршрутизатор находит вариант проезда, который оказывается самым коротким по времени.
Особая тема — дворы. Как известно, сквозной проезд через дворы запрещён. Кроме того, на петляния по дворам зачастую уходит больше времени, чем на проезд по прямой. Чтобы сервис не строил маршруты через дворы, за них начисляются дополнительные минуты (они не влияют на время в пути, которое видит пользователь).
Поэтому в большинстве случаев алгоритм выбирает другие варианты проезда — они занимают меньше времени. Однако если конечная точка маршрута находится во дворе, алгоритму в любом случае придётся туда «въехать».
Построение маршрута происходит очень быстро. Пока вы читаете эти несколько абзацев, сервис уже несколько раз успел бы оплести паутиной маршрутов всю Россию. Чтобы добиться такой скорости, всю карту автоматически поделили на множество областей, для каждой из которых можно посчитать оптимальные варианты её пересечения. Такой областью может быть, например, небольшой городок, через который проходит всего одна междугородняя трасса — въехать и выехать из города можно только по ней. Это значит, что Яндекс может заранее рассчитать оптимальный вариант проезда через этот город.
Если на пути пользователя лежат несколько таких областей, Яндекс просто складывает маршрут из уже готовых кусочков.
Всевозможные варианты проезда внутри каждой области и между ними Яндекс строит заранее — при каждом обновлении графа. Дальше, когда пользователь просит построить маршрут, сервис просто вытаскивает его из памяти. Правда, это срабатывает, только если человеку нужен маршрут без учёта пробок — заранее построенные маршруты рассчитаны на основе средней скорости движения, которая заложена в графе. Если же пользователь хочет построить маршрут с учетом ситуации на дороге и внутри области в данный момент есть пробки, Яндекс построит для него маршрут заново.
Источник: yandex.ru
Программы для планирования маршрута
Найдите лучшие приложения для планирования маршрута для вашего бизнеса. Сравните отзывы о продукте и функции, чтобы построить свой список.
Что такое приложения для планирования маршрута
Программное обеспечение для планирования маршрутов используется диспетчерами транспорта и обслуживания, менеджерами автопарков и водителями курьерских служб для оптимизации их многократных поездок.
Похожие категории
11 результатов
11 результатов
Тарифы
Бесплатно
С тестовым периодом
Подписка на месяц
Подписка на год
Разовая покупка
Возможности
Диспетчерское управление
Перенос мероприятий
Управление водителем
Отслеживание устройств в режиме реального времени
Показатели производительности
Управление территорией
Операционная система
Windows
Mac
Web-Based, Cloud, SaaS
iPhone / iPad
Android
Сортировать по рекомендациям
рекомендациям
Адвантум.Маршрутизация
от Адвантум
Адвантум.Маршрутизация позволяет диспетчеру и логисту управлять автопарком, планировать маршруты, учитывая временные окна, особенности подъездных путей, тарифы и геозоны, данные о транспорте и водителях. Использует постоянно обновляемый OSM граф дорожных сетей. Подробнее о Адвантум.Маршрутизация
Maxoptra
от ООО «НПК «Маджента Девелопмент»
Система управления транспортной логистикой Maxoptra позволяет планировать маршруты курьеров доставки с экономией времени. Здесь можно контролировать перемещение онлайн и формировать план-факт отчетность. Подробнее о Maxoptra
Okdesk
Хелп деск система Okdesk позволяет управлять выездным техническим обслуживанием, планировать маршруты специалистов и видеть их местонахождение на карте. Есть отдельное полнофункциональное мобильное приложение для инженера. Подробнее о Okdesk
SABY Мобильные сотрудники
от Компания «Тензор», ООО
Онлайн-сервис для управления выездным персоналом: больше заказов в день, контроль качества, автоматизация, мобильное приложение с маршрутами и отметками о прибытии, онлайн-касса, работа офлайн, связь с офисом и клиентами через чат и звонки, список задач, инструкции, расходные материалы, фотоотчеты. Подробнее о SABY Мобильные сотрудники
Услуги по внедрению продуктов
Выбери IT-компанию исполнителя для своей задачи
Доступно 1 интегратор
ANTOR LogisticsMaster
от ГК АНТОР
Планирование оптимальных маршрутов доставки и грузоперевозок Подробнее о ANTOR LogisticsMaster
Haul Infinity
от Alastri
Haul Infinity позволяет проектировать маршруты транспортировки в 3D с помощью интуитивно понятных инструментов САПР. Подробнее о Haul Infinity
Planado
от Планадо, ООО
от 499₽/месяц за пользователя
Онлайн-сервис для управления мобильными сотрудниками. Подробнее о Planado
INIT
от Innovation In Traffic Systems
Решение позволяет оптимизировать расписание, график дежурств и нарядов, вести список личного состава и учёт транспортных средств. Подробнее о INIT
Speedy Route
от Speedy Route
от 46.5$/месяц за пользователя
Инструмент планирования, который помогает водителям доставки и разъездным продавцам планировать маршруты и направления при посещении нескольких мест. Подробнее о Speedy Route
YaCu
от Jacurier
YACU — это программа мониторинга логистических перевозок для планирования и оптимизации маршрутов, а также для автоматизации доставки. Подробнее о YaCu
Radaro
SaaS-платформа на базе технологии API, оптимизирующая доставку на расстояние до конечных пунктов. Наш передовой UI/UX создает инновационный клиентский опыт. Подробнее о Radaro
Смежные категории к Программы для планирования маршрута
Сравнить 0 продукта категории Программы для планирования маршрутаПрограммы для планирования маршрута
Остались вопросы?
Ускорьте путь Вашей команды к принятию лучших решений о покупке технологий — благодаря ведущим экспертам pickTech и мнениям коллег.
О компании
- Наша история
- Юридические документы
- Для инвесторов
Пользователям
- Категории ПО
- IT-решения
- Системные интеграторы
- Оставить отзыв
- Блог и исследования
115419, г.Москва, ул.Шаболовка, д.34, стр.5
Все сведения, содержащиеся на страницах сайта (информационные материалы, каталоги, статьи и пр.), носят ознакомительный характер. Информация не является исчерпывающей. Информация на сайте не является публичной офертой, определяемой положениями Статьи 437 Гражданского кодекса РФ. Все права интеллектуальной собственности принадлежат компаниям — производителям программного обеспечения, как и товарные знаки и логотипы. Все ссылки на дистрибутивы, а так же выложенные статьи, товарные знаки и логотипы носят в себе только ознакомительный характер и не претендуют на интеллектуальную собственность, а так же ее нарушение
Источник: picktech.ru