Введение
Каждый сервис доставки рано или поздно сталкивается с трёмя загадочными буквами — VRP. На первый взгляд кажется, что эта аббревиатура обозначает какой-то корпоративный лозунг, использующий транслитерацию, например: VSE RADI PIZZY. Но на самом деле за ней скрывается сложная и крайне важная задача оптимизации. От того, насколько эффективно вы сумеете её решить, зависит не только удовлетворённость клиентов, но и реальные показатели бизнеса: скорость доставки, расходы на логистику.
Всем привет! Меня зовут Ринат Шарафетдинов. Я Senior ML Engineer в команде AI Lab, где мы разрабатываем проекты на основе искусственного интеллекта для развития и повышения эффективности бизнеса Додо.
В этой статье я расскажу, какие типы VRP-задач бывают, чем они отличаются друг от друга, и какие готовые решения вы можете протестировать в ваших кейсах уже сейчас. Также я поделюсь подходами и инструментами, обнаруженными во время исследования, опытом их использования и причинами, по которым я сразу отказался от некоторых из них.
Что такое VRP?
Vehicle Routing Problem (VRP) — это класс задач комбинаторной оптимизации, где требуется оптимально распределить маршруты между несколькими транспортными средствами, минимизируя общую стоимость (время, расстояние, издержки) при соблюдении ряда условий.
Основные виды:
CVRP (Capacitated VRP): задача, в которой у каждого курьера (или транспортного средства) есть ограничение на грузоподъёмность. При этом каждая точка маршрута (доставка) имеет фиксированный объём груза, и вся логика маршрутизации строится с учётом того, сколько заказов можно «унести за раз»;
VRPTW (VRP with Time Windows): задача, в которой каждая точка должна быть обслужена в определённое временное окно. Это очень похоже на доставку еды или экспресс-доставку, где важно не только привезти заказ, но и уложиться во временной интервал (например, с 18:00 до 18:30);
VRPPD (VRP with Pickup and Delivery): более сложная постановка задачи, в которой одно и то же транспортное средство должно забрать что-то в одном месте и доставить в другое. Классический пример — доставка между точками: забрать посылку у одного клиента и доставить другому. Здесь важно правильно согласовать пары «откуда — куда», не превысить вместимость курьера и минимизировать длину самого длинного маршрута.
Почему VRP актуальна для бизнеса
Рост конкуренции, ужесточение требований по срокам и качеству доставки, а также увеличение клиентских ожиданий делают логистику ядром операционного успеха. Быстрая, точная и экономичная доставка напрямую влияет на выручку, удовлетворённость клиентов и общий имидж бренда.
Успешное решение VRP даёт бизнесу целый набор ощутимых выгод:
cнижение затрат на логистику: правильное распределение заказов между курьерами позволяет минимизировать общее расстояние маршрутов, экономить топливо, рабочее время и даже сокращать количество необходимых курьеров в смене;
повышение удовлетворённости клиентов: когда курьеры приезжают вовремя и с минимальной задержкой, клиенты получают лучший сервис. Это напрямую влияет на повторные заказы и лояльность;
снижение стресса внутри команды производства: автоматизация маршрутизации уменьшает ручную нагрузку на операторов, делает работу курьеров предсказуемой и помогает избежать конфликтов из-за несправедливого распределения заказов.
Ограничения при решении задачи:
Компании, работающие в сфере доставки еды, особенно в условиях масштабирования, сталкиваются с рядом повторяющихся логистических проблем:
соблюдение 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‑обучение.
Примеры алгоритмов:
Инструменты
Фреймворки
Простые в использовании библиотеки для решения VRP с возможностью кастомизации:
Python/C++/Java/C# (OR-Tools): работа с разными языками, удобная реализация;
C++ (VROOM): высокая производительность, хорошо подходят для крупных задач;
Java (jsprit): гибкость и производительность;
Python (PyVRP): если нужная бОльшая гибкость и реализация строго на Python.
Про более детальное сравнение (VROOM и jsprit) можно прочитать тут.
Сервисы с открытым API
Удобные и быстрые API для решения небольших задач без глубокой кастомизации:
Научные статьи и книги для погружения в VRP
Если есть желание основательно понять, что такое VRP, то стоит почитать:
Vehicle routing problem: models and solutions — в этой статье обобщаются модели задачи маршрутизации транспортных средств, в том числе и варианты с временными окнами, сбором и доставкой и ограничениями по вместимости. Рассматриваются методы решения задачи — от точных алгоритмов на основе линейного программирования и guided local search до эвристических подходов;
What you should know about the vehicle routing problem — в этой работе обобщаются ключевые результаты по классической задаче маршрутизации транспортных средств с ограничениями по вместимости. Они сгруппированы в три блока: точные алгоритмы, классические эвристики и метаэвристики для построения m маршрутов минимальной стоимости через n клиентов.
Как выбрать подходящее решение?
При выборе стоит учитывать следующее:
размер и масштаб задачи. При большом количестве заказов задача может решаться достаточно долго;
ограничения по времени расчёта;
технологический стек команды;
бизнес-ограничения для алгоритма;
что важнее: гибкость или качество алгоритма?
Например, маленькой компании для решения задачи по маршрутизации подойдёт и сервис с API с одним запросом в день. Однако крупной QSR-компании, в которой алгоритм может вызываться каждые 30 секунд на 1200+ пиццерий, стоит смотреть в сторону OR-Tools или похожего фреймворка, который можно адаптировать под свои потребности. Ну и, конечно, всегда можно собрать свой алгоритм оптимизации и фреймворк, но и реализовать его сложнее.
Практические советы и «подводные камни»
Тщательно подбирайте формулировку задачи под свои ограничения и желания. Чётко фиксируйте все бизнес‑правила и технические ограничения — вместимость, временные окна, приоритеты клиентов —, чтобы формулировка VRP‑задачи полностью отражала реальные условия работы.
Осторожно работайте с расстоянием/временем. Используйте актуальные дорожные и транспортные данные — учёт пробок, пиковых нагрузок и типов дорог, сервисное время на то, чтобы отдать заказ клиенту —, иначе расчётные маршруты могут оказаться не очень функциональными на практике.
Интеграция с другими процессами (например, производством пиццы) существенно усложняет задачу. Синхронизация времени готовности и упаковки продукции с оптимизацией маршрутов требует учёта дополнительных параметров.
Предварительные результаты внедрения VRP в Додо Пицце
Мы решили отказаться от эмпирического алгоритма группировки в пользу фреймворка OR-Tools. Почему?
Во-первых, мы столкнулись с проблемами во время тестирования алгоритма. Во-вторых, OR-Tools прост в работе, имеет достаточную документацию и позволяет получить хорошее качество при решении нашей задачи маршрутизации заказов с ограничениями.
В дополнение к OR-Tools мы реализовали буфер для выдачи заказов, где заказы будут ждать своей очереди на приготовление. А ещё создали ML-модель для прогнозирования времени приготовления группы заказов, так как мы можем сгруппировать вплоть до 3-х заказов.
Мы находимся в активной стадии тестирования нашего решения, поэтому пока рано делать окончательные выводы. Однако уже сейчас мы наблюдаем первые положительные изменения:
группировка заказов показала хорошие результаты: сформировалось множество групп, а заказы без явных ошибок распределялись по географическому признаку корректно. Текущий уровень устойчивости и технической реализации алгоритма позволяет нам масштабировать тестирование на новые пиццерии;
буфер выдачи заказов с ML-прогнозом времени приготовления работает лучше, чем с константой;
метрики доставки в тестах не просаживаются при первичном внедрении системы.
Некоторые из наших первоначальных гипотез подтвердились. Другие же потребовали дополнительной проверки и доработки, но это естественная часть любого инновационного процесса.
Итоги и рекомендации
В VRP нет универсального решения, подходящего всем. Необходимо тщательно подходить к выбору решения, опираясь на конкретные потребности бизнеса. Надеюсь, эта статья поможет вам выбрать подходящий путь и избежать типичных ошибок.
Сталкивались ли вы с VRP? Какое из решений подошло именно вам? Обязательно делитесь в комментариях!
Спасибо, что дочитали эту статью! Ставьте плюсики, если материал показался вам интересным, и делитесь им с друзьями. А чтобы быть в курсе последних новостей Dodo Engineering, подписывайтесь на наш Telegram-канал.
