Задача маршрутизации транспорта. ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ
Задачи маршрутизации транспорта (Vehicle Routing Problems, VRP) — задачи комбинаторной оптимизации, в которых для парка транспортных средств, расположенных в одном или нескольких депо, должен быть определен набор маршрутов до нескольких отдаленных точек-потребителей.
Интерес к VRP вызван ее практической значимостью при значительной сложности.
VRP — хорошо известная задача целочисленного программирования, относящаяся к классу NP-трудных задач, что означает, что вычислительная сложность задачи зависит от размера входных данных экспоненциально.
Для таких задач обычно достаточно искать приближенные решения, которые находятся достаточно быстро и достаточно точны для требуемых целей. Обычно это достигается разными эвристическими методами.
Задачи VRP лежат на пересечении двух хорошо изученных задач.
Задача коммивояжера (Traveling Salesman Problem, TSP): если грузоподъемность С каждого транспортного средства принимается бесконечной (точнее, достаточной), то задача VRP сводится к множественной задаче коммивояжера (Multiple Traveling Salesman Problem, MTSP) путем добавления к исходному графу k-1 (где k — количество маршрутов) копий нулевой вершины и ее ребер (между этими копиями ребра отсутствуют).
Задача об упаковке рюкзака (Bin Packing Problem, BPP): решение данной задачи, по сути, эквивалентно решению задачи VRP при условии, что все расстояния принимаются равными нулю (таким образом, эффективность всех подходящих решений будет одинакова).
Задачи маршрутизации являются ключевыми в областях транспортных перевозок, перемещения и логистики. Во многих областях рынка доставка товара добавляет к его стоимости сумму, сравнимую со стоимостью самого товара. Тем не менее, использование компьютерных методов оптимизации доставки товара часто выражается в экономии порядка 5-20% от общей его стоимости.
Классический вариант задачи маршрутизации
Маршрутизация транспорта относится к комбинаторным задачам, которые можно представить в виде графа G(V, E):
V = {v0, v1, ..., vn} — множество вершин (v0 — депо, v1..n — потребители)
E — множество ребер {(vi, vj) | i ≠ j}
C — матрица неотрицательных расстояний (стоимости пути) cij между потребителями
m — количество машин
Ri — маршрут i-й машины (i=1..m)
C(Ri) — стоимость маршрута Ri
qi - объем груза, поставляемый i-му потребителю
С каждой вершиной Vi ассоциировано некоторое количество товаров, которые должны быть доставлены соответствующему потребителю. Задача маршрутизации состоит в определении такого множества маршрутов m с минимальной общей стоимостью, чтобы каждая вершина множества V была посещена только одним автомобилем только один раз. Кроме того, все маршруты должны начинаться и заканчиваться в депо (v0).
Решением задачи является:
разбиение множества V на подмножества (маршруты);
задание порядка обхода на каждом подмножестве (перестановка вершин маршрута).
Решение является приемлемым (feasible), если все маршруты удовлетворяют дополнительным ограничениям задачи.
Целевой функцией является стоимость решения задачи:
FVRP = ∑C(Ri), i = 1..m
где C(Ri) — сумма длин ребер маршрута Ri.
В классическом варианте требуется найти приемлемое решение с минимальной стоимостью.
Разновидности VRP
Обычно, в реальных задачах оптимизации возникает множество дополнительных ограничений и вариаций, наиболее важные из которых перечислены ниже.
Capacitated VRP (CVRP): каждое транспортное средство имеет ограниченную и грузоподъемность.
VRP with Time Windows (VRPTW): каждый заказчик должен быть обслужен в определенное «временное окно».
Multiple Depot VRP (MDVRP): используются несколько депо для обслуживания клиентов.
VRP with Pick-Ups and Delivering (VRPPD): клиенты могут возвращать некоторые товары в депо.
VRP with Backhauls (VRPB): аналогично предыдущей, но возврат начинается только после доставки всех товаров из депо.
Split Delivery VRP (SDVRP): каждый клиент может обслуживаться одновременно несколькими машинами.
Periodic VRP (PVRP): доставка может осуществляться в течение нескольких дней.
Stochastic VRP (SVRP): некоторые компоненты задачи (количество и запросы клиентов, длина пути) могут иметь случайное поведение.
VRP with Satellite Facilities (VRPSF): существует возможность дозагрузки автомобиля на маршруте.
1. Маршрутизация с ограничением по грузоподъемности (Capacitated VRP, CVRP)
В задачах этого типа вводится дополнительное ограничение: объем грузов на каждом маршруте Ri не должен превышать заданной величины Q (одинаковый для всех машин).
Цель: Минимизировать парк машин, необходимых для выполнения задания, а также общее время выполнения задачи.
2. Маршрутизация с ограничением по времени (VRP with Time Windows, VRPTW)
Данная задача подобна VRP с основным дополнительным условием: для выполнения запроса каждого клиента vi существует известный промежуток времени, определенный как интервал [ei,li] — намеченный горизонт (scheduling horizon).
На рисунке представлен типичный вариант решения задачи с ограничением по времени. Для выполнения заказа каждого клиента существует допустимый интервал времени (показан белым цветом), реальный момент выполнения заказа в соответствии с полученным решением отмечен чертой.
Цель: минимизировать количество машин, общие времена пути и ожидания, необходимые для обработки запросов клиентов в назначенные интервалы времени.
Ограничения: по сравнению с VRP, в задачах данного типа добавляются следующие условия:
решение неприемлемо, если клиент обслуживается после верхней временной границы;
машина, прибывшая ранее нижней временной границы, ожидает ее наступления;
как вариант, опоздание не влияет на пригодность решения, но добавляет некоторое штрафное значение к целевой функции.
Получив решение VRPTW, кроме всего остального, имеется возможность точнее подобрать время выезда транспорта из депо и тем самым избежать бесполезных простоев.
3. Маршрутизация с несколькими депо (Multiple Depot VRP, MDVRP)
В наличии может быть несколько депо, которыми обслуживаются потребители. В случае, если потребители сгруппированы вокруг каждого депо, задача может быть разбита на несколько независимых. Однако, если потребители и депо расположены в беспорядке, нужно искать решение для задачи маршрутизации с множественным депо (MDVRP).
Данная задача требует распределения потребителей по разным депо. В каждом депо располагается парк транспорта. Каждая машина выезжает из своего депо, обслуживает потребителей, прикрепленных к данному депо, и затем возвращается обратно.
Цель: минимизировать парк транспорта и общее время пути.
Ограничения: Каждый маршрут должен удовлетворять стандартным ограничениям VRP, а также начинаться и заканчиваться в одном и том же депо.
Стоимость пути рассчитывается, как и в случае стандартной VRP.
4. Маршрутизация с возвратом товаров (VRP with Pick-Ups and Deliveries, VRPPD)
Задача маршрутизации с возможностью возврата и доставки товаров расширяет стандартную VRP тем, что требуется доставка некоторого количества товаров назад от потребителей в депо. Таким образом, нужно быть уверенным в том, что товары, которые вернет потребитель, не превысят вместимость машины. Это ограничение делает планирование задачи более сложным и может привести к непроизводительному использованию вместимости транспорта, увеличению общего пути и количества единиц транспорта в депо.
Для простоты обычно рассматриваются задачи с дополнительными ограничениями, например, когда все запросы на доставку товаров начинаются в депо и все запросы на возврат товаров оканчиваются в депо, то есть, не происходит обмен товарами между потребителями. Другой способ состоит в отмене ограничения, что все клиенты должны посещаться только один раз. Существует еще одно обычное упрощение — принять, что каждый автомобиль сначала развозит все товары, прежде чем начать принимать товар от клиентов (VRP with Backhauls, VRPB).
Цель: минимизировать парк транспорта и общее время движения.
Ограничения: количество товара, который нужно доставить потребителей и товара, которые нужно забрать от потребителей в депо, не должно превышать вместимость машины ни в одной точке маршрута.
5. Маршрутизация с возвратом товаров (VRP with Backhauls, VRPB)
Задачи маршрутизации с возвратом товаров (VRPB) являются расширением VRP, в котором потребители могут как запросить, так и вернуть некоторые товары. В задаче с доставкой и возвратом (VRPPD) необходимо принять во внимание, что товары, которые вернут потребители, должны уместиться в машине. Отличие от VRPPD состоит в том, что все товары должны быть доставлены, прежде чем произойдет любой возврат. Это требование происходит из того факта, что все машины загружаются сзади и перестановка грузов не является экономически выгодной и приемлемой. Количество товара, который необходимо доставить и принять, фиксировано и известно заранее.
Цель: найти такой набор маршрутов, чтобы минимизировать общее пройденное расстояние.
Ограничения: возврат товаров происходит только после того, как завершена доставка. Объем товаров при доставке и при возврате не должен превышать грузоподъемности.
Постановка задачи: Задача формулируется аналогично задаче с доставкой и возвратом товаров (VRPPD).
6. Маршрутизация с различным транспортом (Split Delivery VRP, SDVRP)
Данная задача расширяет VRP, позволяя обслуживать одного клиента различными видами транспорта, если это уменьшает общую стоимость задачи. Этот случай типичен для ситуации, когда объем заказа сравним по величине с вместимостью машины. Как правило, для задачи маршрутизации с различными видами транспорта получить оптимальное решение сложнее, чем для классической задачи VRP.
Цель: минимизировать парк транспорта и общее время обслуживания всех клиентов.
Ограничения: в отличие от классической VRP, в задачах SDVRP снимается ограничение на то, что клиент должен быть обслужен только одной машиной. Кроме того, парк транспорта включает машины различной вместимости.
Задача SDVRP сводится к VRP разбиением каждого заказа на несколько неделимых заказов.
7. Периодическая маршрутизация (Periodic VRP, PVRP)
В классической задаче VRP обычный период планирования — один день. В задачах с периодической маршрутизацией VRP обобщается расширением периода планирования до нескольких дней.
Цель: минимизировать парк транспорта и общее время обслуживания всех клиентов.
Ограничения: те же, как и в классической VRP. Кроме того, машина может вернуться в депо не в тот же день. По истечении M-дневного периода каждый клиент должен быть посещен как минимум один раз.
Постановка задачи: запросы каждого клиента должны быть выполнены за один визит одним автомобилем. Если период планирования M=1, задача сводится к классической VRP. Каждый клиент в задаче с периодической маршрутизацией должен быть посещен k раз, причем 1 ≤ k ≤ M. В классическом варианте PVRP, ежедневный заказ клиента всегда фиксированный. PVRP можно рассматривать, как задачу компоновки группы маршрутов на каждый день, причем, маршруты должны удовлетворять наложенным ограничениям и общая стоимость задачи должна быть минимальна.
8. Маршрутизация со случайными данными (Stochastic VRP, SVRP)
В данном варианте VRP один или несколько компонентов задачи могут иметь случайное поведение.
Случайные клиенты: каждый клиент существует с вероятностью p и отсутствует с вероятностью p-1.
Случайные запросы: запрос каждого клиента — случайная величина.
Случайные времена: времена поездок (расстояния между потребителями) — случайные величины.
Решение SVRP происходит в два подхода. Первый этап дает решение без учета случайных переменных. На втором этапе, когда становятся известными случайные значения, происходит коррекция ранее полученного решения.
Цель: минимизировать парк транспорта и общее время обслуживания всех клиентов.
Ограничения: когда некоторые данные неизвестны, становится невозможным выполнение всех ограничений для всех случайных переменных. Таким образом, может требоваться выполнение некоторых условий с заданной вероятностью, либо построение корректирующей модели, выполняющейся при нарушении каких-либо ограничений.
Например, в задаче SVRP с возвратом товаров и ограничением по вместимости, возможными способами коррекции будут следующие:
вернуться в депо, когда машина заполнится, с целью разгрузиться, затем продолжить путь по маршруту;
вернуться в депо, когда машина заполнится, и заново оптимизировать оставшуюся часть пути;
запланировать досрочный возврат в депо, даже если машина заполнена не до конца. В данном случае, решение может зависеть от количества собранного груза, и расстояния до депо. Машина может вернуться в депо, если известно, что груз следующего потребителя превысит вместимость автомобиля.
9. Маршрутизация с возможностью дозагрузки (VRP with Satellite Facilities, VRPSF)
Классическая задача VRP предполагает, что каждый маршрут начинается и заканчивается в депо. Одной из причин возврата в депо является ограниченная грузоподъемность. Когда машина развозит все товары, она должна вернуться в депо за новой порцией товаров. Однако, в некоторых случаях выгоднее произвести дозагрузку на маршруте, без возврата в депо, при помощи дополнительных транспортных средств. Типичным является случай, когда множество потребителей ожидают регулярных поставок от одного центрального поставщика.
Цель: минимизировать расходы на доставку товаров за определенный срок (возможно, что, учитывая расходы на вспомогательные машины, общая стоимость решения задачи в краткосрочной перспективе будет выше, чем, например, при решении классической задачи VRP).
Ограничения: товар на складе клиента не должен заканчиваться.
Постановка задачи: задача маршрутизации с возможностью дозагрузки является составной частью задачи распределения товара (IRP, Inventory Routing Problem), в связи с чем полное описание задачи выходит за рамки данной статьи.
Способы решения задач маршрутизации
Ниже приведен список наиболее часто используемых способов решения задачи. Почти все из них — эвристические и мета-эвристические методы, так как точные алгоритмы не всегда дают решение за приемлемое время при большом размере задачи.
Предлагается следующая классификация методов решения.
Точные подходы
Как следует из названия, такой подход перебирает все возможные решения, пока не будет найдено оптимальное.
Метод ветвей и границ (Branch and bound, Fisher, 1994)
Метод ветвей с отсечением (Branch and cut)
Эвристические методы
Производится относительно ограниченный поиск по пространству решений, и обычно находятся хорошие решения за приемлемое время.
Конструктивные методы
Постепенно строят подходящее решение, принимая во внимание получающуюся общую стоимость.
Механизм сбережений (Savings, Clark and Wright, 1964)
Метод, основанный на совпадениях (Matching Based)
Эвристики улучшения многих маршрутов (Multi-route Improvement Heuristics)
Двухфазный алгоритм
Задача разделяется на две части: организация вершин в группы, и построение маршрута по каждой группе.
Fisher and Jaikumar (1981)
The Petal Algorithm
The Sweep Algorithm
Taillard (1993)
Мета-эвристики
В мета-эвристических методах упор делается на тщательном изучении наиболее перспективных частей пространства решений. Качество получаемых решений получается выше, чем у полученных классическими эвристиками.
Ant Algorithms
Constraint Programming
Deterministic Annealing
Genetic Algorithms
Simulated Annealing
Tabu Search
Granular Tabu
The adaptative memory procedure
Kelly and Xu (1999)
Источники
The VRP Web
Vehicle Routing Problems
Vehicle Routing Tutor
Vehicle Routing and Travelling Salesperson Problems
Дмитрий Трофимов, Анатолий Федуков
https://www.lobanov-logist.ru/library/all_articles/55059/