Как быстро составить маршрут

До отпуска остались считанные дни, есть четкое понимание куда Вы хотите поехать, то есть конечная точная маршрута, но дорога то не близкая, а ехать с детьми, где остановиться покушать, как спланировать маршрут так чтобы поездка была в радость, а не превратилась в кошмар на яву? На эти вопросы мы отвечаем в этой полезной заметке. Максимально коротко и только по делу!

Последние события в мире…

Все мы вынуждены привыкать жить в современных реалиях. Последние события в мире, стране вносят свои коррективы в наши планы на отпуск. В связи с этим все больше путешественников выбирают в качестве приоритетного способ путешествия именно на автомобиле. В этой заметке подробно расскажем о том как правильно, легко и удобно спланировать свой маршрут.

Планирование поездки на автомобиле

Итак, Вы уже определились с тем откуда Вы выезжаете, когда и во сколько. Кроме того – Вы точно знаете конечную точку маршрута, осталось дело за малым – спланировать поездку, так чтобы не было накладок.

Для этого я рекомендую использовать Google Maps. Почему именно их? А потому что только они собрали лучшую базу всех мест и достопримечательностей с фотографиями и комментариями посетителей. Дело в том, что Яндекс Карты, не говоря о других менее известных картах, к сожалению на данный момент не имеют такой возможности (или же мы не смогли ее обнаружить). Имеется ввиду возможность нажать практически на любое здание, и в удобном виде получить реальные фотографии и комментарии. В Яндексе немного по другому, он подставляет свои панорамы, что не всегда удобно.

Начну с того что планировать удобнее всего за столом с ноутбуком или ПК. Кроме того Вам понадобится блокнот, это обязательно. Нет ничего удобнее и нагляднее своих записей, которые потом уже можно будет перенести в таблицу.

Кстати, еще одним плюсом Google Maps является, то что из-за наглядного представления фотографий достопримечательностей, можно легко и быстро скорректировать свой маршрут, исключая/включая в него наиболее интересные места.

Итак, открываем сайт. И ищем место нашего конечного маршрута. Пусть это будет Крымский полуостров. Далее, вверху в строке поиска вводим “достопримечательности”. И в результате получаем полный список (слева) и отметки на карте всех достопримечательностей в выбранном районе.

Кликнув на любую из достопримечательностей, мы увидим подробное описание, ссылку на официальный сайт, контактный телефон, а самое главное фотографии людей, которые уже успели там побывать. Часто присутствуют еще и комментарии.

Теперь когда мы знаем какие места хотим посетить в каждом из городов на нашем маршруте, переходим к расчету расстояний между пунктами посещения.

По своему опыту, можем сказать что комфортное расстояние (и время) в пути около 500-700 км (время 7-9 часов) за сутки. Если больше, то становится уже тяжело и поездка начинает превращаться в кошмар на яву. Конечно, есть исключения. Знаем товарищей, которые могут проехать 1500 км с одной остановкой. Но, думаю таких не много. Если говорить о безопасной поездке, то лучше планировать маршрут исходят из приведенных цифр.

Подведем итог

Все что Вам потребуется для планирования поездки:

• ПК или ноутбук (сойдет и смартфон)
• блокнот и ручка
• распечатка карты или просто бумажная карта (атлас)

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

Предположим, что у вас возникло желание поехать посмотреть (например) исток Волги. У вас есть телефон или планшет с отличной программой Offline навигации (например) Maps.me. Что значит offline? Это программы работающие там, где нет не только интернета, но и вообще связи. Единственное что им нужно – прием сигналов спутников GPS. И так, у вас есть устройство, на нем есть программа. Осталось внести точки, куда ехать.

Я состряпал небольшое видео – инструкцию о том, как самим создавать точки маршрута и готовить для программы навигатора. Прошу не судить строго, так как я не большой спец по видеомонтажу 🙂
Надеюсь сие творение окажет вам пользу при планировании ваших поездок в будущем.

На страничке в моем блоге есть много ссылок на координаты различных интересных мест как в России, так и некоторых других странах. По правилам данного сообщества я не имею права выкладывать сюда ссылку, так что желающие найдут сами. Надеюсь они вам пригодятся.

Мы составили шорт-лист десяти облачных сервисов для оптимизации городской логистики, которые вызвали самый большой интерес бизнеса. В качестве источника данных использовали статистику wordstat.yandex.ru, собирали ее в течение года. При чем выбирали только те программы, запросы по которым в поисковике Яндекс растут (выражаются четырех и трехзначными цифрами), что дает основания прогнозировать их популярность в 2023 году.

1. «Яндекс.Маршрутизация» – сервис автоматического построения оптимальных маршрутов для городской доставки. Учитывает большое количество параметров, среди которых габарит грузов, вместимость транспорта, время доставки, работа склада и другие. Состоит из двух сервисов: автоматическое планирование доставки и мониторинг выполнения заказов.

Программа подходит:

• дистрибьюторам;
• ретейлерам;
• e-commerce;
• курьерским службам;
• финансовым организациям;
• сервисным компаниям.

Функционал:

• быстро построение маршрутов для большого количества точек;
• учет прогноза пробок при маршрутизации и данных «Яндекс. Карты»;
• расчет времени приезда водителя на каждую точку;
• отслеживание в реальном времени движения водителей по построенным маршрутам;
• получатели видят статусы исполнения заказов;
• сокращение расходов компаний на логистику.

«Яндекс. Карты», которые используются в программе для маршрутизации, обновляются каждую неделю. Для мониторинга используется приложения «Яндекс.Курьер» или популярные GPS-трекеры. Стоимость зависит от количества машин, выбранной периодичности платежа и набора сервисов.

2. RELOG – облачный сервис для совершенствования внутригородской логистики. Алгоритмы системы выстраивают маршруты, используя машинное обучение. Кроме того, они учитывают большое 40 параметров доставки, среди которых временные окна, объемно-массовые характеристики товара, грузоподъемность машин, платные дороги, график работы водителей и т.д. У сервиса есть всесторонняя аналитика Relog BI, а так же модуль аналитики Relog Census, который помогает дистрибьюторам увеличивать их долю на рынке.

Программа подходит:

• FMCG-компаниям;
• ретейлерам;
• дистрибьюторам фармацевтики;
• компаниям e-commerce;
• мебельным компаниям;
• производителям хлебобулочных изделий;
• компаниям по доставке воды.

Функционал:

• автоматическое создание эффективных маршрутов (радиальные, линейные) с помощью искусственного интеллекта
• алгоритмы программы создают маршруты в соответствии с конкретными транспортными задачами компаний;
• оптимальная загрузка авто товарами для доставки с учетом 40+ параметров;
• сиюминутный мониторинг движения водителей, а так же их пребывания в разных точках;
• снижение транспортных расходов до 50%;
• количество опозданий водителей сокращается в 6-7 раз;
• сокращение численности автопарка для доставки до 20%;
• уменьшение числа отказов клиентов от заказов до 75%;
• повышение утилизации транспорта до 30%;
• оповещение клиентов о приезде водителей;
• сохранение истории передвижения курьеров;
• модуль аналитики app.relog помогает понять, как работают водители, какие клиенты являются выгодными, правильно ли осуществляется доставка;
• аналитика Relog BI помогает сравнить работу каждого водителя/торгового представителя/филиала за разные периоды.

Сервис использует для работы 6 видов карт: 2ГИС, Google Maps, «Яндекс.Карты», Relog Maps, OSM и Here WeGo. Так же программа работает с векторными картами

3. Maxoptra – система транспортного планирования полного цикла, позволяет оптимально распределять заказы между водителями в автоматическом режиме. Сервис использует ГЛОНАСС/GPS-мониторинг и учитывает пробки.

Программа подходит:

• дистрибьюторским компаниям;
• курьерским службам;
• сервисам, работающим в доставке готовых блюд;
• ретейлерам;
• мебельными компаниям;
• транспортным компаниям;
• производителям алкоголя.

Функционал:

• автоматическое планирование маршрутов, можно вручную их корректировать;
• планирование затрат на топливо;
• контроль работы водителей, что позволяет видеть, когда они отклоняются от сформированных маршрутов;
• сокращение суммарного пробега автопарка и рабочего времени сотрудников;
• оповещение получателей о статусах заказов с помощью автоматических SMS/Email;
• сбор отзывов клиентов о работе курьеров.

Сервис предоставляет пользователям аналитические отчеты в Excel файле. Для работы сервис использует Google Maps, «Яндекс.Карты», OSM, Here WeGo.

4. «1С:Предприятие 8. TMS Логистика. Управление перевозками» – программа для планирования грузоперевозок с использованием собственного и привлеченного транспорта. Помимо автоматической маршрутизации в системе можно делать ручное планирование доставок.

Программа подходит:

• компаниям, занимающимся мультимодальными перевозками;
• компаниям с доставкой по регионам и внутри городов.

Функционал:

• автоматическое планирование региональной/местной доставки для большого количества заявок;
• выбор исполнителя перевозки по каждому звену перевозки;
• контроль за выполнением рейсов;
• управление тарифной политикой компании;
• аналитика эффективности доставок.

5. SAP TM – система управления логистикой с учетом различных сценариев транспортировки. Позволяет планировать доставку автоматически и вручную, контролировать выполнение маршрутов, снижать транспортные расходы. Программу можно использовать как компонент SAP S/4HANA или как отдельное решение.

Программа подходит:

• компаниям внутригородской доставки;
• компаниям, которые занимаются региональными перевозками.

Функционал:

• автоматическое планирование доставки и выбор экспедиторов;
• мониторинг движения водителей по маршрутам;
• бронирование транспорта (морской, авиа) и грузов;
• интеллектуальная перепланировка маршрутов;
• контроль за доставкой грузов на каждом этапе;
• расчет транспортных расходов.

6. ANTOR LogisticsMaster – сервис для автоматического построения оптимальных маршрутов. Может рассчитать точные дистанции между точками доставки с учетом дорог (матрица расстояний), а логист имеет возможность визуально оценить оптимальность распределения заявок.

Программа подходит:

• торговым компаниям, доставляющим товары покупателям и партнерам (прямая дистрибуция);
• транспортным и логистическим компаниям;
• сервисным компаниям;
• фармдистрибьюторам:
• компаниям FMCG;
• интернет-магазинам.

Функционал:

• планирование маршрутов с учетом дорожной сети и временных окон доставки;
• автоматическая фиксация времени, когда водитель приехал на каждую точку;
• онлайн-мониторинг движения транспорта и мобильных сотрудников;
• снижение затрат на доставку на 30%;
• повышение загруженности автопарка на 15%;
• формирование аналитических отчетов;
• sms-рассылка клиентам о времени приезда водителя, переносе/отмене.

7. ITOB – программа для формирования оптимальных маршрутов с учетом типа авто, графика работы водителей, веса и объема грузов, временных окон. Входит в сеть «1С:Франчайзи». Система состоит из модулей, каждый из которых решает определенный набор задач.

Программа подходит:

• транспортно-экспедиторским компаниям;
• игрокам в сфере мультимодальных перевозок;
• компаниям с городской и межрегиональной доставкой.

Функционал:

• оптимизация городской логистики,
• рациональная загрузка транспорта;
• оперативный контроль выполнения маршрутов;
• сокращение простоев автомобилей;
• экономия затрат на топливо;
• контроль затрат на содержание автопарка;
• спутниковый мониторинг транспорта через систему ГЛОНАСС.

Система умеет формировать оперативные план-фактные отчеты о разных показателях доставки.

8. «Мегалогист» – система автоматического планирования маршрутов, а так же вручную их корректировать в случае необходимости, позволяет контролировать доставку в режиме реального времени. Программа учитывает множество параметров, такие как временные окна, трудозатраты водителей, грузоподъемность автопарка и вместимость каждой отдельной машины, протяженность маршрутов и прочие.

Программа подходит:

• FMCG-компаниям;
• ретейлерам;
• дистрибьюторам;
• интернет-магазинам;
• курьерским службам;
• мебельным компаниям;
• компаниям в сфере доставки воды.

Функционал:

• оптимизация маршрутов;
• эффективная загрузка машин;
• учет затрат на каждый рейс и сокращение общих расходов на ГСМ;
• аналитические отчеты по ключевым показателям доставки;
• sms-уведомления для заказчиков о статусе доставки;
• своевременное уведомление об опозданиях курьеров.

9. Axelot TMS – программа предназначена для комплексной автоматизации управления транспортом и перевозками. Axelot TMS можно внедрять отдельно и совместно с другими компонентами платформы Axelot SCM.

Программа подходит:

• дистрибьюторским компаниям;
• курьерским службам;
• ретейлерам;
• FMCG-компаниям;
• производителям хлебобулочной продукции.

Функционал:

• автоматическое массовое планирование маршрутов, учитывает большое количество параметров;
• учет затрат на ГСМ, ремонт машин, зарплату водителей и прочих прямых, косвенных затрат;
• контроль состояния документов на ТС и водителей (страховка, водительские удостоверения и т.д.)
• расчет стоимости перевозок;
• управления работой водителей и экспедиторов в реальном времени;
• формирование аналитических отчетов по различным показателям доставки;
• спутниковый мониторинг автопарка с помощью ГЛОНАСС/GPS-трекеров.

Система работает с картографическими сервисами Axelot Maps, OSM, «Яндекс.Карты», Google Maps.

10. «ЯКурьер» – программа, позволяющая эффективно решать задачи внешней и внутренней логистики. Работает в связке с личным кабинетом компании-пользователя и мобильным приложением для водителей, либо с GPS/ГЛОНАСС-трекером, установленным в машине. Система аукционов, создание заявок и назначение водителей, учет ремонта и запчастей, а также модуль финансовой отчетности позволит сократить издержки.

Программа подходит:

• ретейлерам;
• курьерам;
• компаниям FMCG;
• интернет-магазинам; ● поставщикам различного оборудования.

Функционал:

• автоматическое формирование маршрутов таким образом, что заявки распределяются между штатными водителями, исходя из веса, грузоподъемности и временного интервала, в рамках которого нужно доставить товар клиенту;
• мониторинг перемещения автомобилей на карте с помощью GPS/ГЛОНАСС-трекера или установленного приложения «ЯКурьер Исполнитель» у водителя;
• снижение транспортных затрат;
• сокращение суммарного километража, пройденного автопарком при доставке.

Когда вы пользуетесь навигатором, вы указываете точку А и точку Б, и дальше навигатор как-то сам строит маршрут. Сегодня посмотрим, что лежит в основе алгоритма, который это делает. Просто ради интереса. 

Графы и «задача коммивояжёра»

Ещё до появления навигаторов у людей была такая же проблема: как найти кратчайший путь из одного места в другое, если есть ограниченное количество промежуточных точек? Или как объехать ограниченное количество точек, затратив минимальные усилия. В общем виде это называется «задачей коммивояжёра», и мы уже рассказывали, в чём там идея:

Если взять просто города и расстояния между ними, то с точки зрения математики это называется графом: города будут вершинами графа, а дороги между ними — рёбрами графа. Если мы знаем длину каждой дороги, то это будет значением (весом) рёбер графа. Этой теории нам уже хватит, чтобы понять, как работает навигатор в машине.

Алгоритм Дейкстры — ищем самый быстрый путь

Как только появилось решение полным перебором, математики стали искать другой подход, который работал бы гораздо быстрее и не требовал бы вычисления такого огромного объёма данных. В 1959 году Эдсгер Дейкстра придумал свой алгоритм, которым пользуются до сих пор. Идея его в том, чтобы не перебирать все варианты, а находить самый короткий путь только между соседними графами — и так, шаг за шагом, продвигаться к конечной точке.

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

Чтобы найти самый быстрый путь из А в Б, мы смотрим сначала, какие пути у нас выходят из точки А. Видно, что поехать вниз будет быстрее, чем поехать направо:

Значит, выбираем путь вниз. Теперь делаем то же самое для этой точки — смотрим, где быстрее: справа или внизу. Вниз быстрее (1 меньше, чем 4), поэтому едем по ней:

При этом мы не отбрасываем уже сделанные вычисления (всё равно уже посчитали), а запоминаем их на всякий случай. Из нижней точки есть только одна дорога — направо, поэтому едем по ней:

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

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

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

Что ещё учитывает навигатор

Чтобы алгоритм оставался простым и работал только со временем, все остальные параметры дорог тоже привязывают ко времени. Покажем, как это работает, на паре примеров.

Комфорт. Если нам нужно построить не самый быстрый, а самый комфортный маршрут, то мы можем отдать предпочтение автомагистралям и дорогам с несколькими полосами — на них обычно и асфальт получше, и резких поворотов поменьше. Чтобы навигатор выбирал именно такие дороги, им можно присвоить коэффициент 0,8 — это виртуально сократит время на дорогу по ним на 20%, а навигатор всегда выберет то, что быстрее. 

С просёлочными и грунтовыми дорогами ситуация обратная. Они редко бывают комфортными, а значит, им можно дать коэффициент 1,3, чтобы они казались алгоритму более долгими и он старался их избегать. А лесным дорогам можно поставить коэффициент 5 — навигатор их выберет, только если это единственная дорога то точки назначения.

Сложность маршрута и реальное время. Маршрут из А в Б почти никогда не бывает прямым — на нём всегда есть повороты, развороты и съезды, которые отнимают время. Чтобы навигатор это учитывал, в графы добавляют время прохождения поворота — либо коэффициентом, либо отдельным параметром. Из-за этого алгоритм будет искать действительно быстрый маршрут с учётом геометрии дорог.

Пробки. Если есть интернет, то всё просто: навигатор получает данные о состоянии дорог и добавляет разные коэффициенты в зависимости от загруженности. Иногда навигатор ведёт дворами, когда трасса свободна — это не ошибка навигатора, а его прогноз на время поездки: если через 10 минут в этом месте обычно собираются пробки, то там лучше не ехать, а заранее поехать в объезд.

Если интернета нет, то алгоритм просто использует усреднённую модель пробок на этом участке. Эта модель скачивается заранее и постоянно обновляется в фоновом режиме.

Как построить маршрут по всей России

Если нам нужно построить маршрут из Брянска в Тулу, то с точки зрения компьютера это безумно сложная задача: ему нужно перебрать десятки тысяч улиц и миллионы перекрёстков, чтобы понять, какой путь выбрать. С этим плохо справляется даже обычный компьютер, не говоря уже о телефоне.

Если мы в Яндекс Картах построим такой маршрут, то навигатор нам предложит сразу 4 варианта:

Но мы не ждали полчаса, пока сервер на той стороне посчитает все перекрёстки, а получили результат через пару секунд. Хитрость в том, что алгоритм использует уже заранее просчитанные варианты маршрутов и подставляет их для ускорения.

Например, если мы поедем в Тулу не из Брянска, а из Синезёрок, то поменяется только начальный маршрут по трассе М3, а всё остальное останется прежним:

Получается, что навигатору не нужно всё пересчитывать — он находит только ключевые точки пути, а маршрут между ними уже просчитан до этого. Этот приём работает и при перестроении маршрута во время движения: навигатор смотрит, как нужно поменять путь, чтобы вернуть вас на уже известную дорогу.

Что дальше

Следующий этап — напишем алгоритм Дейкстры сами и посмотрим, как он работает по шагам.