Привет, меня зовут Абай Баймуканов, я работают алгоритмистом в ИТ-компании Relog, разрабатывающей облачный сервис для оптимизации городской доставки.
Для решения транспортных задач в логистике нужны лучшие алгоритмы, поэтому мы решили провести собственное исследование и выбрали для него два самых популярных открытых алгоритма - Vroom и Jsprit.
Нужно было понять какой из них лучше не только по качеству, но и выдает решение (построение маршрутов с учетом различных транспортных задач) за короткое время.
Какую задачу решали
Есть разные виды VRP-задач, например, CVRP (учет весогабаритных параметров), VRPTW (учет временных окон), MDVRP (задача с несколькими складами) и PDVRP(задача с забор-доставка). Для теста мы взяли CVRPTW (CVRP+VRPTW), поскольку это самая актуальная для наших клиентов задача.
Про сами алгоритмы. В чем их разница и преимущества
Для решения задач мы использовали два солвера Vroom и Jsprit. Оба они являются движками с открытым исходным кодом и решают CVRPTW, а также имеют много звезд Github.
VROOM
Vroom — это движок оптимизации с открытым исходным кодом, написанный на C++17, предназначенный для поиска эффективных решений разных реальных задач маршрутизации транспортных средств (VRP) за небольшое вычислительное время. Он решает задачу в 2 этапа: