{"id":4859,"title":"\u0422\u0435\u0441\u0442 \u0434\u043b\u044f \u043f\u0440\u043e\u0434\u0430\u043a\u0442\u043e\u0432: vc.ru \u0432 \u0432\u0430\u0448\u0438\u0445 \u0440\u0443\u043a\u0430\u0445","url":"\/redirect?component=advertising&id=4859&url=https:\/\/vc.ru\/special\/bettervc&hash=06e04557a2c39e6c33fa846ba405896b7fed5804f421a1db543b59166c87d7da","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 комментариев
Банкомат «Альфа-банка» дал сбой и не зачислил деньги. Банк ничего не делает

Банкомат не вернул 50 300 рублей. А Банк дальше чат бота по обращению отвечает ориентировочно, когда-нибудь ответим на обращение.

«Ростелеком» подал на меня в суд после смены провайдера

Дело было в 2019 году. Мой провайдер в целом меня устраивал, но цена казалась слегка завышенной, да и просадки в скорости частенько бывали.
И тут как-то звонит мне человек с незнакомого номера, предлагает подключиться к Ростелекому, сэкономить 100 рублей в месяц, получить выше скорость и хороший роутер в аренду за рубль. Я заинтересовался, но мне…

Aleph расширяет присутствие на Ближнем Востоке: холдинг приобрел контрольный пакет акций Connect Ads

Aleph Holding, глобальный партнер крупнейших диджитал платформ и материнская компания Httpool, объявил о приобретении контрольного пакета акций Connect Ads. Компания является провайдером цифровых медиа и рекламных решений в странах Ближнего Востока и Африки.

Как (и зачем) мы полностью переделали интернет-банк. Опыт Альфа-Банка
План победы: как я получил 2.5 миллиона рублей в конкурсе Сбера

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

Морзе, резистор, стихотворный размер. Везде одна страница с визуальным выводом и длинный голосовой ввод.
Как мы сделали покупку «крипты» доступной даже для домохозяек

Добрый день! Меня зовут Александр Комаров, я руководитель проекта мобильного приложения MEW wallet. Наша компания разработала MyEtherWallet — первый в мире специализированный криптокошелёк для покупки и хранения криптовалюты Эфириум (Эфир, Ethereum, ETH). Им пользуются 3,5 млн человек по всему миру! В посте расскажу о том, как мы дошли до жизни…

Apple и Huawei ограничили российским пользователям доступ к приложениям компаний из «чёрного списка» ЦБ Статьи редакции

В общем компании запретили доступ 61 приложению.

Отчёт Mail.ru Group за квартал: треть выручки приходится на игры, растёт выручка от учебных сервисов Статьи редакции

Компания опубликовала финансовые результаты за второй квартал 2021 года на Лондонской бирже.

Как моё сообщество заработало 1,7 млн рублей на VK Donut

Больше шести лет назад Феликс Зинатуллин основал сервис таргетированной рекламы Церебро Таргет и запустил его сообщество ВКонтакте. Теперь там больше 200 тысяч маркетологов и предпринимателей. За год на донатах через VK Donut паблик заработал 1,7 млн рублей. Вот как это вышло.

Феликс Зинатуллин
От конкурентной разведки до настройки рекламы: как использовать прокси в бизнесе

Объясняем на простых примерах.

«Spotify: История продукта». Создание десктопного приложения

От десктопного приложения с серверами в шкафу до революционного нового формата потоковой передачи музыки. "Spotify: История продукта" — серия статей от команды Spotify в России, в которой читателям VC.ru расскажут о том, как создавался сервис, какие решения стояли за продуктовыми изменениями и кто повлиял на то, как музыкальные стриминги выглядят…

null