Привет, меня зовут Абай Баймуканов, я работают алгоритмистом в ИТ-компании 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 для своих задач.

Сравниваем open-source решения VRP задачи