Vehicle Routing Problem

Vehicle Routing Problem (VRP, задача маршрутизации транспорта) — это класс оптимизационных задач комбинаторной математики, в которых требуется найти оптимальный набор маршрутов для парка транспортных средств, обслуживающих заданное множество пунктов (клиентов, точек доставки). Целью решения VRP является минимизация общих затрат (времени, расстояния, топлива, количества транспортных средств) при соблюдении набора ограничений, таких как грузоподъёмность, временные окна, приоритеты обслуживания и дорожные условия. VRP является обобщением классической «задачи коммивояжёра» (TSP) и относится к NP-трудным задачам, что означает отсутствие известного алгоритма точного решения за полиномиальное время для больших размерностей.

История

Первые формальные постановки задачи маршрутизации транспорта появились в 1950-х годах в связи с развитием логистики и операционных исследований. В 1959 году американские математики Джордж Данциг и Джон Рэмсер впервые описали задачу с несколькими транспортными средствами, которая получила название «задача маршрутизации автомобилей» (Vehicle Routing Problem). В 1964 году Кларк и Райт предложили эвристический алгоритм «сбережений» (Clarke-Wright savings algorithm), который до сих пор используется как базовый метод для приближённого решения VRP.

В 1970-е годы, с развитием вычислительной техники, началось активное исследование точных методов (ветвей и границ, динамическое программирование) и метаэвристик (генетические алгоритмы, имитация отжига). В 1980-х годах появились первые коммерческие системы оптимизации маршрутов, интегрированные с системами GPS и управления автопарком. В 1990-е годы VRP стала стандартной задачей в исследованиях операций и логистике, а в 2000-е — с появлением больших данных и облачных вычислений — получила широкое распространение в сервисах доставки, такси и курьерских службах.

Классификация

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

• CVRP (Capacitated VRP) — классическая задача с ограничением грузоподъёмности каждого транспортного средства. Каждый клиент имеет спрос (объём груза), который не может превышать вместимость машины.
• VRPTW (VRP with Time Windows) — задача с временными окнами: каждый клиент должен быть обслужен в определённый интервал времени (например, с 9:00 до 12:00). Нарушение окна может быть запрещено (жёсткое окно) или допускаться со штрафом (мягкое окно).
• VRPPD (VRP with Pickup and Delivery) — задача с одновременным забором и доставкой грузов. Транспортное средство может забирать груз в одном месте и доставлять в другое, причём забор должен предшествовать доставке.
• MDVRP (Multi-Depot VRP) — задача с несколькими депо (базами), откуда транспортные средства начинают и заканчивают маршруты. Каждое транспортное средство приписано к одному депо.
• VRP with Backhauls — задача, где клиенты делятся на две группы: доставка (linehaul) и забор (backhaul). Транспортное средство сначала выполняет доставки, затем — заборы.
• VRP with Heterogeneous Fleet — задача с неоднородным парком, где транспортные средства различаются по грузоподъёмности, скорости, стоимости эксплуатации.
• Dynamic VRP — задача, в которой заказы поступают в реальном времени, а маршруты могут перестраиваться по ходу выполнения.
• Stochastic VRP — задача с неопределёнными параметрами (время в пути, спрос клиентов), которые описываются вероятностными распределениями.

Математическая постановка

Классическая CVRP может быть формализована следующим образом. Пусть имеется граф \( G = (V, E) \), где \( V = \{0, 1, \dots, n\} \) — множество вершин, причём вершина 0 — депо, а вершины \( 1, \dots, n \) — клиенты. Каждому клиенту \( i \) приписан спрос \( q_i > 0 \). Каждому ребру \( (i, j) \) приписана стоимость \( c_{ij} \) (расстояние, время или топливо). Имеется \( K \) идентичных транспортных средств вместимостью \( Q \). Требуется найти набор маршрутов (циклов, начинающихся и заканчивающихся в депо), таких что:

• каждый клиент посещается ровно один раз;
• суммарный спрос на каждом маршруте не превышает \( Q \);
• суммарная стоимость всех маршрутов минимальна.

Математически это задача целочисленного линейного программирования с переменными \( x_{ij}^k \in \{0, 1\} \), обозначающими, проезжает ли транспортное средство \( k \) по ребру \( (i, j) \). Ограничения включают:

• потоковые: для каждого транспортного средства и каждой вершины количество входящих и исходящих рёбер равно 1;
• вместимость: сумма спросов на маршруте \( k \) не превышает \( Q \);
• исключение подциклов: маршруты не могут образовывать изолированные циклы, не включающие депо.

Методы решения

Из-за NP-трудности VRP для практических задач (с числом клиентов более 50–100) точные методы становятся неприменимы. Используются следующие подходы:

Точные методы

• Метод ветвей и границ (Branch and Bound) — рекурсивный перебор с отсечением неперспективных ветвей. Эффективен для задач малой размерности (до 50–100 клиентов).
• Метод ветвей и отсечений (Branch and Cut) — комбинация ветвления с добавлением отсекающих плоскостей (cutting planes) для усиления релаксации.
• Динамическое программирование — применимо для специальных случаев (например, VRP с малым числом транспортных средств).

Эвристические методы

• Алгоритм Кларка-Райта (Clarke-Wright) — построение маршрутов путём последовательного объединения пар клиентов, дающих наибольшую экономию (savings). Прост и быстр, но даёт неоптимальные решения.
• Жадные алгоритмы — построение маршрутов по принципу «ближайшего соседа» или «наименьшей стоимости».
• Метод «вставки» (Insertion Heuristic) — последовательное добавление клиентов в существующие маршруты по критерию минимального прироста стоимости.

Метаэвристики

• Генетические алгоритмы — эволюционный поиск с операциями скрещивания и мутации хромосом, кодирующих маршруты.
• Имитация отжига (Simulated Annealing) — стохастический поиск, допускающий ухудшение решения на ранних этапах для выхода из локальных оптимумов.
• Поиск с запретами (Tabu Search) — итеративный локальный поиск с запоминанием запрещённых ходов для избегания циклов.
• Муравьиные алгоритмы (Ant Colony Optimization) — моделирование поведения муравьёв, оставляющих феромонные следы на удачных маршрутах.
• Роевой интеллект (Particle Swarm Optimization) — коллективный поиск на основе движения частиц в пространстве решений.

Гибридные методы

• Математические эвристики (Matheuristics) — комбинация точных методов (например, решение релаксации) с эвристиками для быстрого получения качественных решений.
• Локальный поиск с большими окрестностями (Large Neighborhood Search) — разрушение и восстановление части маршрутов с помощью точных или эвристических подзадач.

Применение

VRP имеет широкое практическое применение в различных отраслях:

• Логистика и доставка — оптимизация маршрутов курьерских служб (например, «Почта России», «СДЭК», «Яндекс.Доставка»), доставка продуктов и товаров из интернет-магазинов.
• Транспортные компании — планирование маршрутов грузовых автомобилей, автобусов, такси (например, сервисы «Яндекс.Такси», «Uber» — организация Uber признана нежелательной в РФ; «Ситимобил»).
• Службы экстренной помощи — маршрутизация машин скорой помощи, пожарных расчётов, полиции для минимизации времени прибытия.
• Управление отходами — оптимизация маршрутов мусоровозов с учётом объёмов контейнеров и временных окон.
• Сельское хозяйство — планирование маршрутов комбайнов, тракторов, опрыскивателей для минимизации холостых пробегов.
• Военное дело — логистика снабжения войск, маршрутизация конвоев.
• Городское планирование — оптимизация маршрутов общественного транспорта, школьных автобусов.

Примеры

Пример 1: Доставка пиццы. Пусть имеется 10 заказов от клиентов, разбросанных по городу, и один курьер на мотоцикле. VRP без ограничения по грузоподъёмности (все заказы помещаются) сводится к задаче коммивояжёра — требуется найти кратчайший маршрут, посещающий всех клиентов и возвращающийся в пиццерию. Решение может быть найдено алгоритмом Кларка-Райта или метаэвристикой.

Пример 2: Развоз товаров по магазинам. У оптового склада имеется 5 грузовиков вместимостью 10 тонн каждый. 30 магазинов заказали товары общим весом 40 тонн. CVRP решает, какие магазины обслуживать каждым грузовиком, чтобы суммарный пробег был минимальным, а каждый грузовик не превышал 10 тонн. Решение может быть найдено генетическим алгоритмом или поиском с запретами.

Интересные факты

• VRP является одной из наиболее изученных задач в области операционных исследований: по состоянию на 2024 год опубликовано более 10 000 научных статей, посвящённых её различным аспектам.
• В 2019 году команда исследователей из Массачусетского технологического института (MIT) с помощью нейросетевого подхода (рекуррентные нейронные сети) решила VRP с 100 клиентами за 1 миллисекунду с точностью, сопоставимой с лучшими эвристиками.
• Крупнейшие логистические компании (Amazon, DHL, FedEx) используют специализированные программные пакеты (например, OR-Tools от Google, CPLEX от IBM, Gurobi) для ежедневной оптимизации маршрутов миллионов заказов.
• В России VRP активно применяется в сервисах доставки «Яндекс.Еда», «Купер» (ранее «СберМаркет»), «Магнит Доставка» для планирования маршрутов курьеров и водителей.

Источники

• Данциг Дж., Рэмсер Дж. «The Truck Dispatching Problem» (1959)
• Кларк Г., Райт Дж. «Scheduling of Vehicles from a Central Depot to a Number of Delivery Points» (1964)
• Ленстра Дж., Ринной Кан А. «Complexity of Vehicle Routing and Scheduling Problems» (1981)
• Таутенхайн Т. «Metaheuristics for the Vehicle Routing Problem» (2014)
• Лапорт Ж. «The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms» (1992)
• OR-Tools Google — документация по решению VRP (2024)
• Gurobi Optimization — руководство пользователя (2024)