Задача маршрутизации транспорта

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

История

Ранние предпосылки

Первые математические постановки задач, связанных с маршрутизацией, появились в середине XX века. В 1959 году американские математики Джордж Данциг и Джон Рамсер впервые сформулировали задачу маршрутизации транспорта (VRP) в контексте доставки бензина на автозаправочные станции. Они предложили метод решения на основе линейного программирования и целочисленного программирования.

Развитие в 1960–1980-е годы

В 1964 году Гарри Кларк и Дж. У. Райт разработали эвристический алгоритм «экономии» (Clarke-Wright savings algorithm), ставший одним из первых практически применимых методов для VRP. В 1970-е годы появились точные методы решения (метод ветвей и границ, динамическое программирование), однако из-за NP-трудности задачи они были применимы только для малых размерностей (до 50–100 точек). В 1980-е годы началось активное развитие метаэвристик: имитации отжига, генетических алгоритмов, поиска с запретами.

Современный этап

С 1990-х годов VRP стала одной из центральных задач в логистике и транспортном планировании. Развитие вычислительной техники и алгоритмов (муравьиные алгоритмы, алгоритмы роя частиц, нейросетевые подходы) позволило решать задачи с тысячами точек. В XXI веке активно внедряются системы реального времени, учитывающие пробки, погоду, окна доставки и динамически изменяющийся спрос. В России задача маршрутизации транспорта применяется в логистических компаниях («Почта России», «СберЛогистика», «Деловые Линии»), а также в сфере городского пассажирского транспорта.

Классификация и разновидности

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

Основные типы VRP

• CVRP (Capacitated VRP) — базовая версия с ограничением грузоподъёмности каждого транспортного средства.
• VRPTW (VRP with Time Windows) — каждый клиент должен быть обслужен в заданный временной интервал (окно).
• VRPPD (VRP with Pickup and Delivery) — транспортное средство может как забирать, так и доставлять грузы, причём доставка должна предшествовать забору.
• MDVRP (Multi-Depot VRP) — транспортные средства базируются на нескольких складах (депо).
• SDVRP (Split Delivery VRP) — допускается разделение заказа одного клиента между несколькими транспортными средствами.
• VRP with Backhauls — клиенты делятся на две группы: доставка (linehaul) и сбор (backhaul), причём сбор выполняется после завершения доставок.
• Dynamic VRP — заказы поступают в реальном времени, маршруты пересчитываются динамически.
• Green VRP — оптимизация с учётом экологических критериев (выбросы CO₂, расход топлива).

По типу транспортных средств

• Однородный парк — все транспортные средства имеют одинаковые характеристики (грузоподъёмность, скорость, стоимость).
• Неоднородный парк — транспортные средства различаются по параметрам (например, грузовики разной вместимости, электромобили и дизельные автомобили).

По критерию оптимизации

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

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

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

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

Математически задача сводится к минимизации целевой функции: \[ \min \sum_{k=1}^{K} \sum_{(i,j) \in E} c_{ij} x_{ij}^k \] при ограничениях, обеспечивающих целостность маршрутов и вместимость.

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

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

• Метод ветвей и границ — перебор с отсечением неперспективных вариантов. Применим для задач до 50–100 клиентов.
• Целочисленное линейное программирование — использование симплекс-метода и отсечений (Гомори, ветвей и отсечений).
• Динамическое программирование — для малых размерностей (до 20–30 точек).

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

• Алгоритм Кларка-Райта — построение маршрутов путём объединения пар клиентов с максимальной «экономией» (снижением затрат).
• Метод ближайшего соседа — последовательное добавление ближайшего необслуженного клиента.
• Метод вставки — построение маршрута путём вставки новых точек в существующий маршрут с минимальным увеличением стоимости.

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

• Генетические алгоритмы — эволюционный поиск с операциями скрещивания и мутации.
• Поиск с запретами — локальный поиск с запоминанием запрещённых решений для избегания циклов.
• Имитация отжига — вероятностный метод, позволяющий выходить из локальных оптимумов.
• Муравьиные алгоритмы — имитация поведения колонии муравьёв при поиске кратчайших путей.
• Алгоритмы роя частиц — коллективный поиск на основе движения частиц в пространстве решений.

Приближённые алгоритмы

• Алгоритм Фишера-Янга — гарантированная оценка качества решения (например, 2-приближение для некоторых вариантов VRP).
• LP-релаксация — решение задачи с ослабленными целочисленными ограничениями с последующим округлением.

Применение

Логистика и транспорт

• Планирование маршрутов доставки товаров (интернет-магазины, курьерские службы, сети розничной торговли).
• Оптимизация вывоза мусора и сбора вторсырья.
• Управление парком такси и каршеринга (в том числе динамическое распределение заказов).
• Маршрутизация школьных автобусов и служебного транспорта.

Городское планирование

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

Производство и складское хозяйство

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

Военное дело

• Планирование маршрутов снабжения войск и эвакуации.
• Маршрутизация беспилотных летательных аппаратов (БПЛА) для разведки или доставки грузов.

Программное обеспечение

Для решения задач маршрутизации транспорта разработано множество коммерческих и открытых программных продуктов:

• OR-Tools (Google) — библиотека с открытым исходным кодом, поддерживающая CVRP, VRPTW и другие модификации.
• LKH-3 — модификация алгоритма Лин-Кернигана для VRP.
• VROOM — открытое решение для реального времени.
• IBM ILOG CPLEX — коммерческий решатель для точных методов.
• Gurobi — коммерческий решатель с поддержкой целочисленного программирования.
• OptaPlanner (Red Hat) — платформа для планирования на Java.
• PTV Optima — коммерческий продукт для транспортного планирования.
• Logistics Vision — российская система для оптимизации маршрутов доставки.

В России также используются решения на базе 1С (например, «1С:Логистика:Управление перевозками») и специализированные модули от компаний «Яндекс.Такси» и «СберЛогистика».

Сложности и открытые проблемы

• NP-трудность — для больших размерностей (более 1000 клиентов) точные методы неприменимы, требуется разработка эффективных эвристик.
• Динамические условия — учёт пробок, погоды, отказов транспорта и изменений заказов в реальном времени.
• Многокритериальность — одновременная оптимизация нескольких противоречивых критериев (стоимость, время, экологичность).
• Стохастичность — неопределённость во времени в пути, спросе клиентов, доступности транспорта.
• Интеграция с другими системами — задача VRP часто решается совместно с управлением запасами (Inventory Routing Problem) или планированием производства (Production Routing Problem).

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

• Задача маршрутизации транспорта входит в список 10 самых важных задач оптимизации, сформулированных Международным обществом математического программирования.
• Первое практическое применение VRP в СССР было связано с оптимизацией маршрутов молоковозов в Московской области в 1970-х годах.
• Современные алгоритмы способны находить решения для 10 000 клиентов за несколько минут на обычном персональном компьютере.
• В 2020 году компания Amazon запатентовала метод маршрутизации с использованием дронов и наземных транспортных средств (гибридная доставка).

Источники

• Dantzig G. B., Ramser J. H. The Truck Dispatching Problem // Management Science. — 1959. — Vol. 6, № 1. — P. 80–91.
• Clarke G., Wright J. W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points // Operations Research. — 1964. — Vol. 12, № 4. — P. 568–581.
• Toth P., Vigo D. (eds.). The Vehicle Routing Problem. — SIAM, 2002. — 367 p.
• Laporte G. The Vehicle Routing Problem: An overview of exact and approximate algorithms // European Journal of Operational Research. — 1992. — Vol. 59, № 3. — P. 345–358.
• Vidal T., Crainic T. G., Gendreau M., Prins C. Heuristics for multi-attribute vehicle routing problems: A survey and synthesis // European Journal of Operational Research. — 2013. — Vol. 231, № 1. — P. 1–21.
• Материалы конференций «Логистика и управление цепями поставок» (Россия, 2010–2023).