{"id":4725,"title":"\u041c\u0430\u0441\u0442\u0435\u0440-\u043a\u043b\u0430\u0441\u0441: \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0432 \u043a\u043e\u043c\u0430\u043d\u0434\u0435 \u0438 \u0432\u0435\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u0433\u043e\u0432\u043e\u0440\u044b","url":"\/redirect?component=advertising&id=4725&url=https:\/\/vc.ru\/promo\/269679-korotko-interaktivnyy-master-klass-o-komandnoy-rabote-i-masterstve-peregovorov&hash=10609550b909bb5be9e2454a472e95a790a4f1279029e657ec1c7baeac51ec09","isPaidAndBannersEnabled":false}

Алгоритмы 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.

{ "author_name": "Кирилл Константинович", "author_type": "self", "tags": [], "comments": 13, "likes": 11, "favorites": 4, "is_advertisement": false, "subsite_label": "transport", "id": 257092, "is_wide": true, "is_ugc": true, "date": "Thu, 10 Jun 2021 14:11:23 +0300", "is_special": false }
(function(w, d, id) { var h = 5000; var a = d.querySelector('#volvo-head'); var b = d.querySelector('[data-content-id="'+id+'"]'); var i = []; if (a && b) { a.style.display = 'block'; startSlideShow(); } var c = 0; var id = 0; function startSlideShow() { i = [].slice.call(a.querySelectorAll('.volvo-head__text span')); nextSlide(); }; function changeSlide() { var p = c; c += 1; if (c >= i.length) { c = 0; } if (i[p]) { i[p].classList.remove('volvo-head__active'); } if (i[c]) { i[c].classList.add('volvo-head__active'); } }; function nextSlide() { id = setTimeout(function() { var a = d.querySelector('#volvo-head'); if (a) { changeSlide(); nextSlide(); } }, h); }; }(window, document, 137185));
0
13 комментариев
Популярные
По порядку
Написать комментарий...
9

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

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

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

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

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

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

Ответить
11

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

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

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

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

Ответить
7

Добрый день,

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

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. Что касается конкретно пробок и как они считаются в Яндекс.Маршрутизации —  кажется, это тема отдельного разговора, мы планируем выпустить подробный материал на этот счет — уже совсем скоро.

Ответить
7

И отдельно про параметр кучности. Ссылки на документацию, где описано применение параметра кучности маршрутов:
- маршруты, устойчивые к изменениям - 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

Ответить
1

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

Ответить
10

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

Ответить
7

cool stuff

Ответить
6

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

Ответить
5

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

Ответить
4

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

Ответить
3

nice result 

Ответить
2

Its getting hot in here!

Ответить
2

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

Ответить
Читать все 13 комментариев
Какие агро-стартапы получили больше всего инвестиций за июль 2021

Общая сумма финансирования проектов из подборки почти $800 млн.

На конференции «B Word» Илон Маск в очередной раз поменял свою позицию по биткоину

В ходе конференции где также присутствовали Джек Дорси и Кэти Вуд, Маск отметил, что он является владельцем биткойнов не только через баланс Tesla и SpaceX, но и лично владеет биткойнами, эфиром и Dogecoin.

Тинькофф хитрит со спецпредложением по кэшбеку во Вкусвилл

В июле доступно спецпредложение - кэшбек 10% во Вкусвилл. Тинькофф деактивировал его и перенес дату окончания.

Восточная Техника успешно автоматизирует процессы управления складами на базе решения Columbus-WMS
Возможности, как в корпорации, а гибкость, как у стартапа. Что думают о своей работе сотрудники DiDi

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

«Стартап-полка»: Самокат набирает производителей альтернативных продуктов

Онлайн-ритейлер Самокат совместно с Ассоциацией Производителей Альтернативных Пищевых Продуктов объявляют сбор заявок от инновационных производителей продуктов для участия в «стартап-полке» Самоката. Лучшие продукты попадут в постоянный ассортимент Самоката в раздел «Супермаркет» уже этой осенью.

LTE на даче

Небольшой очерк без лишних технических деталей о подключении дачи к 4G интернету.

Карьерный путь IT-инженера: от Долины к стабильной британской компании через стартапы и психотерапию

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

Пластиковый «дом будущего» должен был решить проблему нехватки жилья, а стал аттракционом в Диснейленде Статьи редакции

В конце 50-х архитекторы в США построили здание из пластмассы и «оснастили» его бытовыми предметами грядущих десятилетий — атомной микроволновкой, ультразвуковой посудомойкой, движущимися проекторами, гигантским экраном, пластиковой мебелью и посудой.

У Дома будущего Monsanto было четыре крыла Iconichouses
NASA и SpaceX отправят научный зонд для поиска жизни на спутнике Юпитера в 2024 году Статьи редакции

Запуск миссии Europa Clipper обойдётся в $178 млн — столько NASA выделяет компании Илона Маска по условиям контракта.

Где идеи обретают форму: как устроены мастерская прототипов и тестовая лаборатория IKEA Статьи редакции

Отрывок из книги «Дизайн ИКЕА. Искусство создания продуктов, которые продаются сами», которая вышла в издательстве «Бомбора».

Пункт повышения качества продукции, где проводятся испытания
null