Алгоритмы Relog и «Яндекс.Маршрутизация»: в чем их преимущества при доставке товаров?

В успешном планировании ежедневной доставки ключевую роль играет алгоритм программы маршрутизации. В этой статье я сравнил работу демо-версий Relog и «Яндекс.Маршрутизация», у каждого из которых есть свои преимущества.

Первый кейс. В случае с TMS «Яндекса» одним из них называют прогнозирование пробок при построении маршрута. Моделирую стандартную задачу, чтобы увидеть, как ее выполнит алгоритм в Москве. Дистрибьютор воды завтра должен доставить бутыли по 576 заявкам, у него 18 машин. При этом продолжительность рабочего дня курьеров составляет 8 часов. В среднем на каждого водителя приходится 35 точек. Планирую доставку в «Яндекс.Маршрутизация» для первого водителя. Программа рассчитала, что время курьера в пути составит 2 часа 28 минут. Теперь копирую его маршрут и вставляю в «Яндекс.Карты», сервис показал, что без пробок на него потребуется 2 часа 25 минут, а с пробками прогнозируемое время доставки воды может увеличиться до 5 часов, то есть разница составит 2 часа 35 минут.

При сравнении оставшихся 17 маршрутов по «Яндекс.Картам» оказалось, что «Яндекс.Маршрутизация» заложил на них от 2 часов 30 минут до 3 часов. Данные картографического сервиса «Яндекса» свидетельствуют, что с учетом заторов водители будут развозить бутыли 5-6 часов 30 минут.

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

Алгоритм Relog учитывает пробки на основе статистики, но не прогнозирует их.

Второй кейс. Я решил протестировать обе программы в Алматы (Казахстан), где нет такой загруженности на дорогах, как в Москве. Кроме того, увеличил число точек для доставки воды и численность автопарка дистрибьютора. Пусть у него будет 24 машины и на завтра сформировано 747 заявок от клиентов, день работы курьеров так же составляет 8 часов. В этой задаче TMS Relog и «Яндекс.Маршрутизация» проходили проверку по двум параметрам: оптимизация количества автомобилей, сокращение времени маршрута.

Маршрутизатор «Яндекса» решил ее следующим образом: каждый водитель доставит бутыли в среднем по 35 заявкам, правда последнему курьеру придется развести воду по 45 точкам. Для обслуживания всех заказов в этот день понадобится 21 машина. То есть алгоритм оптимизировал работу так, что 3 машины для выполнения плана оказались не нужны.

Планирование Relog потребовало 20 машин, нагрузка на каждого водителя будет такая же, как у «Яндекс.Маршрутизация» — 35 точек. В целом Relog оптимизировал доставку компании на 4 машины.

Посмотрим на то, как оба алгоритма проложили маршруты на карте.

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

И снова о пробках. Планирование «Яндекс.Маршрутизация», показало, что продолжительность первого маршрута по времени составит 20 мин 47 секунд. Картографический сервис «Яндекса» без учета пробок спрогнозировал 21 минуту, а с заторами — 24 минуты.

Итак, основные выводы сравнительного анализа. Первый — в смоделированной ситуации маршрутизатор «Яндекса» не учел пробки на дорогах. Второй – разница при оптимизации доставки двумя программами составила 1 машину (Relog – 20 машин, «Яндекс.Маршрутизация» — 21) за счет кучности маршрутов, выстроенных в Relog.

0
14 комментариев
Написать комментарий...
Яндекс.Маршрутизация

Спасибо, что выбрали именно Яндекс.Маршрутизацию для сравнения с вашей системой.

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

По сути материала хотелось бы прокомментировать два момента:
1. Перекладывать маршрут, полученный в результате работы маршрутизации на Яндекс Карты - заведомо неверный способ проверить выполнимость маршрута. Кажется, мы на этом уже останавливались в одном из комментариев, но повторимся - Яндекс Карты учитывают пробки на текущий момент. Для всех 35 сегментов маршрута. Алгоритм маршрутизации учитывает пробки гораздо более гибко, мы знаем среднюю скорость движения на каждом дорожном сегменте в течение всего дня на соответствующую дату доставки и учитываем скорость в соответствии с нужным временным интервалом.

2. Кучные маршруты, как в вашем случае, можно получить и в Яндекс.Маршрутизации - такая опция есть и доступна всем клиентам. Какое бы решение получилось с учетом кучности? Вопрос, на который не видя задачи мы ответить не можем.

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

Судя по скриншотам с карт, решения сравнивались в ноябре, вероятно, прошлого года. Если вдруг они сохранились, с удовольствием посмотрим на исходные данные и полученные результаты.

Ответить
Развернуть ветку
Кирилл Константинович
Автор

Коллеги, спасибо за отклик и конструктивный диалог. Что касается первого пункта, то хотел бы обратить ваше внимание на то, что в статье речь идет о прогнозировании пробок при построении маршрута на следующий день в Москве. «Яндекс.Карты» позволяют пользователю установить время выезда водителя на маршрут на будущий период. К слову, вы этого не знали? Таким образом, перекладывая маршрут из «Яндекс.Маршрутизация» (ЯМ) в «Яндекс.Карты», мы установили одни и те же параметры выезда водителей по дате и времени, то есть сделали все условия в двух системах одинаковыми. В итоге ЯМ решил задачу таким образом, что время водителя в пути при обслуживании всех заказов составит 2 часа 28 минут, а при переложении маршрута в «Яндекс.Карты», как я сказал выше, в режиме без учета пробок время водителя в пути составит 2 часа 25 минут. То есть прогнозное время выполнения маршрута в двух сервисах практически одинаковое. Тогда как с учетом пробок, по расчетам «Яндекс.Карты», водитель в пути проведет 5 часов 15 минут.

При моделировании данного кейса были тщательно изучены все параметры планирования в ЯМ. Сделали несколько планирований в разных режимах и выбрали наиболее оптимальный с точки зрения общего пробега автопарка. Скриншоты прикрепляем.

Все-таки, мы хотели бы понять, как и где включить этот «прогноз пробок» в ЯМ, потому что мы не смогли найти эту функцию и не смогли убедиться, что прогноз действительно есть. Хотя допускаем, что эта опция есть и возможно это мы не разобрались. Просим вас раскрыть эту тему досконально.

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

Ответить
Развернуть ветку
Яндекс.Маршрутизация

Добрый день,

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

1. Почему маршрут с выездом в 08:00 с учетом пробок показывает 5 ч.15 минут, а в Яндекс.Маршрутизации та же последовательность точек показала 2ч 28 мин?

Здесь все просто. Яндекс Карты действительно умеют показывать расчетное время в зависимости от даты и времени старта. Но также надо понимать, что для карт, которые как правило являются инструментом обычного горожанина объезд более 10 точек - довольно нетипичный сценарий. И карты при расчете времени проезда маршрута берут пробки на 08:00 и считают что они будут одинаковыми для всех точек в маршруте. Утренние пробки, как мы знаем, довольно плотные. Поэтому на картах и получается 5 часов 15 минут, как если бы тот же уровень пробок сохранялся на протяжении всего маршрута.
С этим, кажется, разобрались. Давайте перейдем к следующему вопросу.

2.  Почему Яндекс.Карты говорят, что без пробок ехать 2 ч 25 минут, а в Яндекс.Маршрутизации та же последовательность точек показала 2 ч 28 минут? Означает ли это что Яндекс.Маршрутизация не учитывает пробки?

Ответить на вопрос "почему так получилось?" имея только скриншоты, которые вы предоставили, довольно сложно. Не очень ясно, какие были настройки параметра выезда машин - вероятно они выехали раньше 08:00, например в 07:00 или в какое-то другое время, и в это время пробочный профиль был совсем другим. 
Но есть предложение не оперировать старым скриншотом, а сделать подобный расчет прямо сейчас.

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

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

Результаты такие:

- Яндекс.Маршрутизация - 2 ч 47 минут
- Яндекс.Карты с пробками на 08 утра - 3 ч 42 минуты (так как пробки в 8 утра больше)
- Яндекс.Карты без пробок - 2 ч 22 минуты

Разница в полчаса заметна. Чтобы уж точно проверить лучше всего взять секундомер и проехать.

3. Что касается конкретно пробок и как они считаются в Яндекс.Маршрутизации —  кажется, это тема отдельного разговора, мы планируем выпустить подробный материал на этот счет — уже совсем скоро.

Ответить
Развернуть ветку
Яндекс.Маршрутизация

И отдельно про параметр кучности. Ссылки на документацию, где описано применение параметра кучности маршрутов:
- маршруты, устойчивые к изменениям - https://yandex.ru/routing/doc/vrp/concepts/planning-proximity.html
- географическая группировка маршрутов - https://yandex.ru/routing/doc/vrp/concepts/global-proximity-factor.html

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

Мы взяли одну и ту же задачу и решили ее с базовыми настройками (без кучности) и с разными значениями параметра кучности. А затем сравнили полученные решения с точки зрения метрик.

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

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

Без учета кучности  - https://yadi.sk/i/idqCrWqY0xBe5A
Более кучные маршруты - https://yadi.sk/i/MH5x2Se1qVdG-g
Еще более кучные маршруты - https://yadi.sk/i/eP3hfofDxY9jAA
Сравнение решений - https://yadi.sk/i/YxbCPpv4j502cA

Ответить
Развернуть ветку
Кирилл Константинович
Автор

Я также проверил результаты планирования на свежих данных, запланировав маршруты на 24 июня и установил время выезда водителей со склада в 9.00. Обращаю ваше внимание на то, что за основу взял параметр «время в пути»».
Результаты получились такими:
Маршрут -1:
- "Яндекс.Маршрутизация" - 1 ч 29 минут
- ​ "Яндекс.Карты" без пробок - 1 ч 42 минуты
- "Яндекс.Карты" с пробками - 2 ч 30 минуты
Маршрут -2:
- "Яндекс.Маршрутизация" - 3 ч 50 минут
- "Яндекс.Карты" без пробок - 3 ч 57 минуты
- "Яндекс.Карты" с пробками - 6 ч 21 минуты
Таким образом, "Яндекс.Маршрутизация" выдает те же результаты, что и "Яндекс.Карты" без пробок, а в некоторых случаях они оказались даже излишне оптимистичными по продолжительности маршрутов. Файлы и скриншоты прикрепил.

Ответить
Развернуть ветку
Мухтар Лекеров

Действительно, при тесте явного параметра кучности и учета пробок не нашел. Есть фича отображения пробок на карте, что прикольно. Результат планирования не сохраняется, если закрыть вкладки, что было очень неудобно. Аналитика очень простая. Можно ли сделать в ЯМ параметр маршрута, чтобы определенные водители везли только определенные маршруты или параметр температурного режима при распределения заявок?

Ответить
Развернуть ветку
Almabek Mamedaliyev

cool stuff

Ответить
Развернуть ветку
Beltelecom

Ждём комментария от Яндекс Маршрутизации))

Ответить
Развернуть ветку
Ablay Adilbek

Интересный результат! Классная статья! 

Ответить
Развернуть ветку
Dmitriy

Кхм, обошёл гиганта)

Ответить
Развернуть ветку
Bola TT

nice result 

Ответить
Развернуть ветку
Turdiyev Robert

Its getting hot in here!

Ответить
Развернуть ветку
Магжан Сулейманов

Классная статья!

Ответить
Развернуть ветку
Artem Mironov

Релог кинул мою компанию на 300000 рублей) Взались за интеграцию модуля на 1С Битрикс и обделались в прямом смысле слове, тех поддержка банально не справилась с битриксом , тянули 2 месяца при изначальном сроке 1 неделя, а потом просто перестали реагировать на тикеты и заявки. Признали , что справиться не могут , но и деньги вернуть не могут, так как время потратили. Руководство компании ни разу по запросу не вышло на контакт, менеджеры извинялись и кидали трубки в лучшем случае.
Я работаю в e-commerce 16 лет, у меня онлайн гипермаркет (более 100000 заказов в год), сеть ресторанов с Дарк Китчен, 4 собственных айти компании, диджитал агенство. Я знаю весь ай-ти рынок, но за все время таких г»»но подрядчиков еще не встречал. Колхозная контора, которая на обертке пытается выстроить пиар компанию, а сервиса - 0. Я вам покажу обратную сторону пиара. За полгода игнора мой пиар отдел даст вам полгода про»»»ться)

Ответить
Развернуть ветку
11 комментариев
Раскрывать всегда