Возможности маршрутизатора Veeroute: конфигурации планирования
Введение
Оптимизационный движок Veeroute - это универсальный инструмент для решения задач маршрутизации из разных сфер бизнеса, таких как доставка последней мили, дальнемагистральные перевозки, сервисные инженеры, гиперлокальная доставка и так далее, подробнее о его работе можно почитать в нашей статье. Критерии оценки качества решения отличаются в зависимости от сферы бизнеса и его специфики, а для того, чтобы результат решения задачи максимально точно соответствовал требованиям клиента, в оптимизационном движке Veeroute предусмотрен выбор конфигурации.
В этой статье мы рассмотрим, что такое конфигурация, какие они бывают, чем друг от друга отличаются и как выбрать подходящую.
Материал данной статьи будет полезен тем, кто хочет подробнее узнать о возможностях нашего оптимизационного движка и погрузиться в детали его работы.
Какую задачу решает оптимизационный движок Veeroute
Прежде чем перейти к описанию конфигураций, ознакомимся с задачей маршрутизации в общем виде. Решение задачи маршрутизации заключается в составлении расписания выполнения заказов, которое удовлетворяет всем заданным ограничениям. Ниже рассмотрим компоненты задачи маршрутизации.
Заказ - это своего рода задача, которую должен выполнить один исполнитель. Заказ включает в себя список заявок - это связанные подзадачи, которые необходимо сделать исполнителю, чтобы заказ считался выполненным. Заявка, в свою очередь, содержит в себе список событий, которые конкретизируют возможные способы её выполнения. Такая структура позволяет описать как простые заказы (например, забрать документы из локации А во временной промежуток с 8:00 до 10:00), так и сложные, состоящие из нескольких заявок и возможных событий (например, взять накладную в начале маршрута, затем загрузиться на одном из двух складов, доставить одну часть груза клиенту, другую - на точку самовывоза, забрать на точке самовывоза оборотную тару, доставить оборотную тару на склад).
Исполнитель - это тот, кто выполняет заказы. У каждого исполнителя есть список смен. Смена описывает следующие характеристики работы исполнителя: время, когда он доступен, место, откуда он начинает маршрут и где его заканчивает, режим труда и отдыха, стоимость его работы, а также различные ограничения при наличии.
Помимо исполнителей в задаче маршрутизации используются транспортные средства. Для них также указывается список смен со временем доступности, локациями старта и финиша и затратами. Помимо смен для транспортных средств задаётся информация об их вместимости.
Ещё один важный компонент таких задач - это совместимости. Они указывают, какие заказы могут быть запланированы вместе в одном маршруте, какие заказы может выполнить конкретный исполнитель, какие локации может посещать конкретное транспортное средство и так далее. Совместимости могут быть "мягкими", это значит, что их требования разрешается нарушать, но за такое нарушение предусмотрен штраф.
Решение задачи - это список маршрутов, каждый из которых включает в себя смену исполнителя, смену транспорта и упорядоченный список событий с временной разметкой (например, перемещение, выполнение заказа, перерыв, ожидание начала временного окна на локации и так далее). Использование оптимизационного движка Veeroute позволяет гарантировать отсутствие нарушений заданных изначально ограничений в запланированных маршрутах.
Что такое конфигурация
При решении любой оптимизационной задачи требуется определить критерии оценки качества решения. Конфигурация планирования - это упорядоченный список таких критериев. Например, конфигурация optimize_cars_then_distance
задает следующие критерии:
максимальное количество раставленных заказов,
минимальное количество маршрутов,
минимальный пробег.
Другими словами, при использовании в планировании конфигурации optimize_cars_then_distance
в первую очередь будет расставлено как можно больше заказов, при этом задействовано как можно меньше транспорта, а при прочих равных будет минимизирован пробег.
Далее подробнее остановимся на том, какие есть конфигурации и в каких случаях их можно использовать.
Обзор конфигураций оптимизационного движка Veeroute
В таблице приведен список конфигураций, которые в данный момент уже используются при планировании в Veeroute. Однако список постоянно обновляется и расширяется, в том числе создаются новые конфигурации по запросу и потребностям наших клиентов.
В первом столбце таблицы указано название конфигурации, а в остальных - критерии оптимизации, которые она задаёт. При планировании в первую очередь учитывается Критерий 1, во вторую - Критерий 2, в последнюю очередь учитывается Критерий 3.
Таблица с описанием конфигураций
Название конфигурации | Критерий 1 | Критерий 2 | Критерий 3 |
---|---|---|---|
optimize_money | ↑ прибыль | ||
optimize_distance | ↑ заказы | ↓ расстояние | |
optimize_cars_then_distance | ↑ заказы | ↓ маршруты | ↓ расстояние |
optimize_duration или optimize_time | ↑ заказы | ↓ общее время | |
optimize_cars_then_duration или optimize_transports или optimize_cars_then_time | ↑ заказы | ↓ маршруты | ↓ общее время |
optimize_visual_grouping | ↑ заказы | ↑ кучность1* | |
optimize_locality_grouping | ↑ заказы | ↑ кучность2* | |
optimize_cars_then_locality_grouping или visual_grouping | ↑ заказы | ↓ маршруты | ↑ кучность2* |
optimize_single_location_grouping | ↑ заказы | ↑ кучность3* | |
optimize_cars_then_single_location_grouping | ↑ заказы | ↓ маршруты | ↑ кучность3* |
optimize_cars_then_single_location_grouping_sequenced | ↑ заказы | ↓ маршруты | ↑ кучность4* |
*подробнее про кучности будет описано ниже
Рассмотрим подробнее, чем отличаются друг от друга некоторые конфигурации. Возьмем для примера две конфигурации: optimize_distance
и optimize_cars_then_distance
. Критерием качества обеих этих конфигураций является минимзация пробега, но в конфигурации optimize_cars_then_distance
более приоритетным является критерий минимизации количества маршрутов, тогда как в конфигурации optimize_distance
этого критерия нет. Выбор между двумя этими конфигурации зависит от того, что важнее клиенту: сократить количество маршрутов, даже если это приведет к увеличению пробега, либо получить решение с минимальным пробегом.
В конфигурациях optimize_time
и optimize_cars_then_time
в отличие от рассмотренных выше вместо пробега минимизируется суммарное время работы исполнителей. Использование этих конфигураций может быть полезно, если требуется максимально эффективно использовать время работы исполнителей, в том числе с учетом пробок. Конфигурации optimize_time
и optimize_cars_then_time
также используются, когда затраты на время работы исполнителей значительно превышают затраты на пробег (например, инкасация, велокурьеры, сервисные инженеры).
Критерии оптимизации пробега или времени работы исполнителей не всегда удовлетворяют потребностям наших клиентов, иногда возникает необходимость строить "кучные" маршруты. "Кучный" маршрут - это маршрут, в котором точки находятся на относительно небольшом расстоянии друг от друга. У таких маршрутов есть преимущество - в случае переноса заказа его всё ещё возможно выполнить в тот же день, но в другое время, а в случае отмены заказа маршрут изменится незначительно, так как все заказы расположены рядом друг с другом. По-другому такие маршруты называются "надежными". Мы часто сталкиваемся также и со стереотипом, что "маршруты должны быть кучными для сокращения пробега". Однако "кучность", вопреки расхожему мнению и, возможно, интуиции, достигается за счет увеличения пробега и суммарных затрат.
Мы предоставляем конфигурации для разных видов "кучности", чтобы у клиентов была возможность выбрать подходящий вариант. Рассмотрим их ниже. Конфигурации, в которых расставляется как можно больше заказов с максимальной кучностью:
optimize_visual_grouping
optimize_locality_grouping
optimize_single_location_grouping
Конфигурации, в которых помимо кучности минимизируется количество маршрутов:
optimize_cars_then_locality_grouping
optimize_cars_then_single_location_grouping
optimize_cars_then_single_location_grouping
optimize_cars_then_single_location_grouping_sequenced
Разберем подробнее конфигурацию optimize_money
. Главный критерий этой конфигурации - это максимизация прибыли, которая состоит из суммы наград за выполненные заказы за вычетом затрат на выполнение маршрутов. В качестве награды может использоваться оценка упущенной прибыли в случае невыполнения заказа. Затраты включают в себя:
стоимость выхода исполнителя на смену,
стоимость времени работы исполнителя,
стоимость использования транспорта,
стоимость пробега,
стоимость перемещения грузов,
штраф за нарушение мягких совместимостей.
Эта конфигурация подходит для следующих случаев:
в задаче есть заказы с разными приоритетами,
у заказов есть альтернативные события с разной наградой,
в задаче есть исполнители и/или транспорт с разной стоимостью,
в задаче есть мягкие совместимости.
При использовании этой конфигурации следует помнить, что выполнение некоторых заказов может оказаться невыгодным с точки зрения описанной экономической модели, поэтому они не будут запланированы.
Для планирование с конфигурацией optimize_money
требуется максимально точное описание экономической модели, в которой указываются все награды и затраты. В случае если результаты получаются не такие, как ожидается, то велика вероятность того, что есть проблема в описании экономической модели, а не в качестве планирования.
Пример использования различных конфигураций при решении одной задачи
Рассмотрим влияние выбора конфигурации на решение на примере синтетической задачи. Описание задачи:
236 заказов,
временное окно доставки у всех заказов одинаковое и составляет 10 часов,
время на выполнение заказа 30 минут,
награда за заказ 500 рублей,
20 исполнителей и транспортных средств с общей точкой старта,
стоимость одного километра составляет 36 рублей,
стоимость одного часа работы исполнителя 400 рублей,
роутинг по OSRM с пробками.
Результаты запуска задачи на разных конфигурациях представлены в таблице ниже.
Название конфигурации | Заказы, шт | Маршруты, шт | Пробег, м | Общее время, ЧЧ:ММ:СС | Прибыль, руб |
---|---|---|---|---|---|
optimize_money | 161 | 10 | 799153 | 101:53:18 | 10975 (1) |
optimize_cars_then_distance | 236 (1) | 15 (2) | 1308318 (3) | 153:09:02 | 9640 |
optimize_duration или optimize_time | 236 (1) | 16 | 1408510 | 151:32:00 (2) | 6680 |
optimize_cars_then_single_location_grouping | 236 (1) | 15 (2) | 1534741 | 155:08:35 | 692 |
Примеры, приведенные в статье, подробно описаны в нашей документации. Если вы хотите глубже изучить аналитику и получить тестовый доступ, просто обратитесь в Service Desk.
Как следует из данных таблицы, при использовании конфигурации optimize_money
расставился только 161 заказ из 236, но было получено решение с наибольшой прибылью, которая составила 10975 рублей.
Использование конфигурации optimize_cars_then_distance
позволило получить решение с наименьшим расстоянием (130 8318 метров) и количеством маршрутов (15) при условии выполнения всех 236 заказов.
При использовании конфигурации optimize_time
суммарное время на выполнение маршрутов составило 151 час и 32 минуты, что на 1 час, 37 минут и 2 секунды меньше, чем при использовании конфигурации optimize_cars_then_distance
, что было достигнуто за счет увеличения количества маршрутов и пробега.
В конфигурации optimize_cars_then_single_location_grouping
были получены "кучные" маршруты, что привело к увеличению пробега на 17.3% относительно конфигурации optimize_cars_then_distance
. Ниже приведена визуализация полученных маршрутов на конфигурациях optimize_cars_then_distance
и optimize_cars_then_single_location_grouping
.
Выводы
Задача маршрутизации является сложной комбинаторной задачей, решение которой требует значительных ресурсов, но оказывает положительный экономический эффект. Качество решения зависит от точности постановки задачи. Оптимизационный движок Veeroute позволяет описать и решить задачи маршрутазиции клиентов из разных сфер бизнеса благодаря использованию различных конфигураций. Широкий выбор доступных конфигураций дает возможность нашим клиентам выбрать ту, которая максимально точно описывает особенности их деятельности. При этом список наших конфигураций постоянно обновляется и расширяется, а у наших клиентов есть возможность запросить новую конфигурацию под их специфические требования.
Если вас заинтересовала тема автоматической оптимизации, то вы сможете больше узнать о возможностях платформы оптимизации и компаниях, которые успешно используют продукт.