Решаем VRP-задачи, или Как мы в Додо доставку оптимизировали

Введение

Каждый сервис доставки рано или поздно сталкивается с трёмя загадочными буквами — VRP. На первый взгляд кажется, что эта аббревиатура обозначает какой-то корпоративный лозунг, использующий транслитерацию, например: VSE RADI PIZZY. Но на самом деле за ней скрывается сложная и крайне важная задача оптимизации. От того, насколько эффективно вы сумеете её решить, зависит не только удовлетворённость клиентов, но и реальные показатели бизнеса: скорость доставки, расходы на логистику.

Всем привет! Меня зовут Ринат Шарафетдинов ^[1]. Я Senior ML Engineer в команде AI Lab, где мы разрабатываем проекты на основе искусственного интеллекта ^[2] для развития и повышения эффективности бизнеса Додо.

В этой статье я расскажу, какие типы VRP-задач бывают, чем они отличаются друг от друга, и какие готовые решения вы можете протестировать в ваших кейсах уже сейчас. Также я поделюсь подходами и инструментами, обнаруженными во время исследования, опытом ^[3] их использования и причинами, по которым я сразу отказался от некоторых из них.

Что такое VRP?

Vehicle Routing Problem (VRP) ^[4] — это класс задач комбинаторной оптимизации, где требуется оптимально распределить маршруты между несколькими транспортными средствами, минимизируя общую стоимость (время, расстояние, издержки) при соблюдении ряда условий.

Основные виды:

• CVRP (Capacitated VRP): задача, в которой у каждого курьера (или транспортного средства) есть ограничение на грузоподъёмность. При этом каждая точка маршрута (доставка) имеет фиксированный объём груза, и вся логика ^[5] маршрутизации строится с учётом того, сколько заказов можно «унести за раз»;

• VRPTW (VRP with Time Windows): задача, в которой каждая точка должна быть обслужена в определённое временное окно. Это очень похоже на доставку еды или экспресс-доставку, где важно не только привезти заказ, но и уложиться во временной интервал (например, с 18:00 до 18:30);

• VRPPD (VRP with Pickup and Delivery): более сложная постановка задачи, в которой одно и то же транспортное средство должно забрать что-то в одном месте и доставить в другое. Классический пример — доставка между точками: забрать посылку у одного клиента и доставить другому. Здесь важно правильно согласовать пары «откуда — куда», не превысить вместимость курьера и минимизировать длину самого длинного маршрута.

Почему VRP актуальна для бизнеса

Рост конкуренции, ужесточение требований по срокам и качеству доставки, а также увеличение клиентских ожиданий делают логистику ядром операционного успеха. Быстрая, точная и экономичная доставка напрямую влияет на выручку, удовлетворённость клиентов и общий имидж бренда.

Успешное решение VRP даёт бизнесу целый набор ощутимых выгод:

• cнижение затрат на логистику: правильное распределение заказов между курьерами позволяет минимизировать общее расстояние маршрутов, экономить топливо, рабочее время и даже сокращать количество необходимых курьеров в смене;

• повышение удовлетворённости клиентов: когда курьеры приезжают вовремя и с минимальной задержкой, клиенты получают лучший сервис. Это напрямую влияет на повторные заказы и лояльность;

• снижение стресса ^[6] внутри команды производства: автоматизация маршрутизации уменьшает ручную нагрузку на операторов, делает работу курьеров предсказуемой и помогает избежать конфликтов из-за несправедливого распределения заказов.

Ограничения при решении задачи:

Компании, работающие в сфере доставки еды, особенно в условиях масштабирования, сталкиваются с рядом повторяющихся логистических проблем:

• соблюдение SLA: доставка должна быть быстрой и точной, иначе компания теряет доверие клиента и деньги на компенсации;

• нестабильный трафик: маршруты нужно постоянно пересчитывать, иначе легко попасть в пробки или приехать с опозданием;

• дисбаланс нагрузки между курьерами: кто-то перегружен, кто-то простаивает. Это снижает эффективность работы и демотивирует команду;

• синхронизация: важно учитывать время готовности блюда и время до приезда курьера, чтобы не накапливалось ожидание и не было опозданий.

Почему оказалось сложно найти единое решение

Когда я исследовал задачу распределения заказов по курьерам, у меня не было чёткого понимания, в какую сторону двигаться. Мне, как ML-инженеру, сначала показалось логичным группировать заказы по общим признакам, используя метод поиска ближайших соседей. Погрузившись в проблему глубже, я думал о географической кластеризации и даже пробовал библиотеку h3 по совету коллег. Однако мои возможности были ограничены технологическим стеком компании и собственной экспертизой: мой основной рабочий инструмент — Python.

После нескольких дней активного поиска информации и чтения научных статей я и узнал о VRP. Я начал изучать доступные решения в интернете, но полезной информации по моему запросу, учитывая реализацию на Python, было мало. Множество решений были созданы с использованием других языков программирования, таких как: C++ и Java, но я искал что-то простое, понятное и быстрое в освоении, чтобы оперативно внедрить эффективное решение на Python.

Обзор подходов и инструментов для решения VRP

Подходы

• Эвристика — быстро строят начальное решение, но качество может быть далеко от оптимального.

  Примеры алгоритмов:

  • Clarke–Wright savings (метод «сбережений»);

  • «Sweep» (сортировка клиентов по полярному углу).

• Метаэвристика — предлагают баланс скорости и качества для средних и больших задач.

  Примеры алгоритмов:

  • Локальный поиск и его расширения: 2‑opt, 3‑opt;

  • Tabu Search, Simulated Annealing, GRASP (Greedy Randomized Adaptive Search);

  • Genetic Algorithms, Ant Colony Optimization;

  • Large Neighborhood Search (LNS) / Adaptive LNS (ALNS).

• DL (Deep Learning) — подходят, если вы готовы инвестировать в сбор/симуляцию данных и GPU‑обучение.

  Примеры алгоритмов:

  • Reinforcement Learning for Solving the Vehicle Routing Problem ^[7];

  • Attention, Learn to Solve Routing Problems! ^[8]

Инструменты

Фреймворки

Простые в использовании библиотеки для решения VRP с возможностью кастомизации:

• Python/C++/Java/C# (OR-Tools ^[9]): работа с разными языками, удобная реализация;

• C++ (VROOM ^[10]): высокая производительность, хорошо подходят для крупных задач;

• Java (jsprit ^[11]): гибкость и производительность;

• Python (PyVRP ^[12]): если нужная бОльшая гибкость и реализация строго на Python.

Про более детальное сравнение (VROOM и jsprit) можно прочитать тут ^[13].

Сервисы с открытым API

Удобные и быстрые API для решения небольших задач без глубокой кастомизации:

• OpenRouteService ^[14];

• GraphHopper ^[15].

Научные статьи и книги для погружения в VRP

Если есть желание основательно понять, что такое VRP, то стоит почитать:

• Vehicle routing problem: models and solutions ^[16] — в этой статье обобщаются модели задачи маршрутизации транспортных средств, в том числе и варианты с временными окнами, сбором и доставкой и ограничениями по вместимости. Рассматриваются методы решения задачи — от точных алгоритмов на основе линейного программирования и guided local search до эвристических подходов;

• What you should know about the vehicle routing problem ^[17] — в этой работе обобщаются ключевые результаты по классической задаче маршрутизации транспортных средств с ограничениями по вместимости. Они сгруппированы в три блока: точные алгоритмы, классические эвристики и метаэвристики для построения m маршрутов минимальной стоимости через n клиентов.

Как выбрать подходящее решение?

При выборе стоит учитывать следующее:

• размер и масштаб задачи. При большом количестве заказов задача может решаться достаточно долго;

• ограничения по времени расчёта;

• технологический стек команды;

• бизнес-ограничения для алгоритма;

• что важнее: гибкость или качество алгоритма?

Например, маленькой компании для решения задачи по маршрутизации подойдёт и сервис с API с одним запросом в день. Однако крупной QSR-компании, в которой алгоритм может вызываться каждые 30 секунд на 1200+ пиццерий, стоит смотреть в сторону OR-Tools или похожего фреймворка, который можно адаптировать под свои потребности ^[18]. Ну и, конечно, всегда можно собрать свой алгоритм оптимизации и фреймворк, но и реализовать его сложнее.

Практические советы и «подводные камни»

• Тщательно подбирайте формулировку задачи под свои ограничения и желания. Чётко фиксируйте все бизнес‑правила и технические ограничения — вместимость, временные окна, приоритеты клиентов —, чтобы формулировка VRP‑задачи полностью отражала реальные условия работы.

• Осторожно работайте с расстоянием/временем. Используйте актуальные дорожные и транспортные данные — учёт пробок, пиковых нагрузок и типов дорог, сервисное время на то, чтобы отдать заказ клиенту —, иначе расчётные маршруты могут оказаться не очень функциональными на практике.

• Интеграция с другими процессами (например, производством пиццы) существенно усложняет задачу. Синхронизация времени готовности и упаковки продукции с оптимизацией маршрутов требует учёта дополнительных параметров.

Предварительные результаты внедрения VRP в Додо Пицце

Мы решили отказаться от эмпирического алгоритма группировки в пользу фреймворка OR-Tools. Почему?

Во-первых, мы столкнулись с проблемами во время тестирования алгоритма. Во-вторых, OR-Tools прост в работе, имеет достаточную документацию и позволяет получить хорошее качество при решении нашей задачи маршрутизации заказов с ограничениями.

В дополнение к OR-Tools мы реализовали буфер для выдачи заказов, где заказы будут ждать своей очереди на приготовление. А ещё создали ML-модель для прогнозирования времени приготовления группы заказов, так как мы можем сгруппировать вплоть до 3-х заказов.

Мы находимся в активной стадии тестирования нашего решения, поэтому пока рано делать окончательные выводы. Однако уже сейчас мы наблюдаем первые положительные изменения:

• группировка заказов показала хорошие результаты: сформировалось множество групп, а заказы без явных ошибок распределялись по географическому признаку корректно. Текущий уровень устойчивости и технической реализации алгоритма позволяет нам масштабировать тестирование на новые пиццерии;

• буфер выдачи заказов с ML-прогнозом времени приготовления работает лучше, чем с константой;

• метрики доставки в тестах не просаживаются при первичном внедрении системы.

Некоторые из наших первоначальных гипотез подтвердились. Другие же потребовали дополнительной проверки и доработки, но это естественная часть любого инновационного процесса.

Итоги и рекомендации

В VRP нет универсального решения, подходящего всем. Необходимо тщательно подходить к выбору решения, опираясь на конкретные потребности бизнеса. Надеюсь, эта статья поможет вам выбрать подходящий путь и избежать типичных ошибок.

Сталкивались ли вы с VRP? Какое из решений подошло именно вам? Обязательно делитесь в комментариях!

Спасибо, что дочитали эту статью! Ставьте плюсики, если материал показался вам интересным, и делитесь им с друзьями. А чтобы быть в курсе последних новостей Dodo Engineering, подписывайтесь на наш Telegram-канал ^[19].