Привет, меня зовут Абай Баймуканов, я работают алгоритмистом в ИТ-компании Relog, разрабатывающей облачный сервис для оптимизации городской доставки.
Для решения транспортных задач в логистике нужны лучшие алгоритмы, поэтому мы решили провести собственное исследование и выбрали для него два самых популярных открытых алгоритма - Vroom и Jsprit.
Нужно было понять какой из них лучше не только по качеству, но и выдает решение (построение маршрутов с учетом различных транспортных задач) за короткое время.
Какую задачу решали
Есть разные виды VRP-задач, например, CVRP (учет весогабаритных параметров), VRPTW (учет временных окон), MDVRP (задача с несколькими складами) и PDVRP(задача с забор-доставка). Для теста мы взяли CVRPTW (CVRP+VRPTW), поскольку это самая актуальная для наших клиентов задача.
Про сами алгоритмы. В чем их разница и преимущества
Для решения задач мы использовали два солвера Vroom и Jsprit. Оба они являются движками с открытым исходным кодом и решают CVRPTW, а также имеют много звезд Github.
VROOM
Vroom — это движок оптимизации с открытым исходным кодом, написанный на C++17, предназначенный для поиска эффективных решений разных реальных задач маршрутизации транспортных средств (VRP) за небольшое вычислительное время. Он решает задачу в 2 этапа:
поиск изначального решения, для которого он применяет 5 видов эвристик и regret coefficient;
поиск локального минимума для этого решения, Vroom использует 14 видов операторов.
Vroom использует 32 вида заранее подготовленных настроек (типы эвристики и regret coefficient) поиска изначального решения.
JSPRIT
Jsprit – движок для решения VRP-задач, написанный на Java. Он имеет открытый исходный код, использует идею симуляции отжига, а именно идею ruin and recreate.
Так же как и Vroom, Jsprit находит изначальное решение и итеративно оптимизирует его в 2 этапа:
на этапе ruin он ломает собственное изначальное решение;
на стадии recreate этот солвер его восстанавливает.
Как тестировали
Для исследования мы обезличили данные наших клиентов – запланированные маршруты - стандартизировали их, привели к задаче CVRPTW. Взяли для планирования ~700 маршрутов, у которых количество заявок составляло с 50 до 3 000.
Метрики:
Количество назначенных заявок;
Суммарная время и дистанция;
Количество назначенных водителей;
Вычислительное время.
Что показало исследование
В процессе эксперимента было выявлено, что Jsprit решает задачи медленно (для получения такого же результата как у Vroom он решал задачу в 10 раз дольше), поэтому мы решили сократить количество итерации до 128 и продолжили эксперимент.
При таких условиях Jsprit выдает результаты в среднем хуже, при этом вычислительное время у него оказалось больше.
Для сравнения результатов использовали метрику: a - b / max(a, b), что показывает долю отклонения от лучшего результат (далее del-max).
График по дистанции:
delmx_distance = del-max(voom_distance, jsprit_distance)
nu_services = количество заявок
График по количеству назначенных заявок:
delmx_assigned = del-max(voom_assigned, jsprit_assigned)
nu_services = количество заявок
Сравнение гибкости
Так же мы сравнили насколько легко реализовывать новые фичи в этих алгоритмах.
Jsrpit имеет готовые интерфейсы hard/soft constraints, они могут быть на уровне подбора транспорта для заявки или при вставке заявки в определенную часть маршрута.
Что бы реализовать ограничение во Vroom нужно дописывать логику ограничения во все операторы (их 15) и это не просто copy-paste, поскольку у каждого оператора своя логика, т.е. нужно иметь хорошую экспертность в написании кода движка.
Также в Jsprit можно реализовать свою целевую функцию, для этого есть интерфейс ObjectiveFunction или решать задачу Time Dependent VRP, в которой меняются дистанция/время проезда относительно времени и т.д.
Выводы
Для решения наших задач Jsprit более гибкий, чем Vroom, и позволяет решать больший спектр задач. Что же касается других алгоритмистов, то придется решать, готовы ли они ждать дольше, чтобы получить лучшее решение и потестить Vroom для своих задач.