Проблема маршрутизации транспортных средств

Проблема оптимизации

Рисунок, иллюстрирующий проблему маршрутизации транспортных средств

Задача маршрутизации транспортных средств ( VRP ) — это задача комбинаторной оптимизации и целочисленного программирования , которая спрашивает: «Каков оптимальный набор маршрутов для парка транспортных средств, которые необходимо пройти, чтобы доставить грузы заданному набору клиентов?» Она обобщает задачу коммивояжера (TSP). Впервые она появилась в статье Джорджа Данцига и Джона Рамсера в 1959 году ^[1] , в которой был описан первый алгоритмический подход, примененный к доставке бензина. Часто контекстом является доставка товаров, находящихся на центральном складе, клиентам, которые разместили заказы на такие товары. Целью VRP является минимизация общей стоимости маршрута. В 1964 году Кларк и Райт улучшили подход Данцига и Рамсера, используя эффективный жадный алгоритм, называемый алгоритмом сбережений.

Определение оптимального решения VRP является NP-трудным [ ^2], поэтому размер задач, которые можно оптимально решить с помощью математического программирования или комбинаторной оптимизации, может быть ограничен. Поэтому коммерческие решатели, как правило, используют эвристики из-за размера и частоты реальных VRP, которые им необходимо решить.

VRP имеет множество прямых приложений в промышленности. Поставщики инструментов маршрутизации VRP часто заявляют, что они могут предложить экономию затрат в размере 5%–30%. ^[3]

Постановка проблемы

VRP касается услуг компании по доставке. Как вещи доставляются из одного или нескольких депо , которые имеют заданный набор домашних транспортных средств и управляются набором водителей , которые могут перемещаться по заданной дорожной сети к набору клиентов . Он требует определения набора маршрутов , S , (один маршрут для каждого транспортного средства, которое должно начинаться и заканчиваться на своем собственном депо) таким образом, чтобы все требования клиентов и эксплуатационные ограничения были удовлетворены, а глобальные транспортные расходы были минимизированы. Эти расходы могут быть денежными, дальними или иными. ^[2]

Дорожную сеть можно описать с помощью графа , где дуги — это дороги, а вершины — перекрестки между ними. Дуги могут быть направленными или ненаправленными из-за возможного наличия улиц с односторонним движением или различных затрат в каждом направлении. Каждая дуга имеет связанную с ней стоимость, которая обычно равна ее длине или времени в пути, которое может зависеть от типа транспортного средства. ^[2]

Чтобы узнать глобальную стоимость каждого маршрута, необходимо знать стоимость поездки и время в пути между каждым клиентом и депо. Для этого наш исходный граф преобразуется в граф, вершинами которого являются клиенты и депо, а дуги — дороги между ними. Стоимость каждой дуги — это наименьшая стоимость между двумя точками исходной дорожной сети. Это легко сделать, поскольку задачи поиска кратчайшего пути относительно легко решаются. Это преобразует разреженный исходный граф в полный граф . Для каждой пары вершин i и j существует дуга (i,j) полного графа, стоимость которой записывается как и определяется как стоимость кратчайшего пути от i до j . Время в пути — это сумма времен перемещения дуг по кратчайшему пути от i до j на исходном дорожном графе. ${\displaystyle C_{ij}}$ ${\displaystyle t_{ij}}$

Иногда невозможно удовлетворить все требования клиентов, и в таких случаях решатели могут снизить требования некоторых клиентов или оставить некоторых клиентов необслуженными. Для решения этих ситуаций может быть введена приоритетная переменная для каждого клиента или соответствующие штрафы за частичное или необслуживание каждого клиента ^[2]

Целевая функция VRP может сильно различаться в зависимости от конкретного применения результата, но вот несколько наиболее распространенных целей: ^[2]

• Минимизировать глобальные транспортные расходы на основе пройденного расстояния, а также фиксированных расходов, связанных с подержанными транспортными средствами и водителями.
• Минимизировать количество транспортных средств, необходимых для обслуживания всех клиентов.
• Наименьшие колебания времени в пути и загрузки транспортного средства
• Минимизировать штрафы за некачественное обслуживание
• Увеличьте полученную прибыль/баллы.

Варианты ВРП

Карта, показывающая взаимосвязь между общими подзадачами VRP.

Существует несколько разновидностей и специализаций задачи маршрутизации транспортных средств:

• Задача маршрутизации транспортных средств с прибылью (VRPP): задача максимизации, в которой не обязательно посещать всех клиентов. Цель состоит в том, чтобы посетить клиентов один раз, максимизируя сумму собранной прибыли, соблюдая при этом ограничение по времени для транспортного средства. Транспортные средства должны начинать и заканчивать свой путь на складе. Среди наиболее известных и изученных VRPP мы приводим:
  • Задача командного ориентирования (TOP), которая является наиболее изученным вариантом VRPP, ^{[4] [5] [6]}
  • Задача ориентирования команды с достаточными возможностями (CTOP),
  • TOP с временными окнами (TOPTW).
• Проблема маршрутизации транспортных средств с получением и доставкой (VRPPD): необходимо переместить ряд товаров из определенных мест получения в другие места доставки. Цель состоит в том, чтобы найти оптимальные маршруты для парка транспортных средств, чтобы посетить места получения и высадки.
• Проблема маршрутизации транспортных средств с LIFO : Аналогично VRPPD, за исключением того, что на загрузку транспортных средств накладывается дополнительное ограничение: в любом месте доставки доставляемый товар должен быть последним забранным товаром. Эта схема сокращает время погрузки и разгрузки в местах доставки, поскольку нет необходимости временно выгружать товары, кроме тех, которые должны быть доставлены.
• Проблема маршрутизации транспортных средств с временными окнами (VRPTW): Места доставки имеют временные окна, в течение которых должны быть осуществлены доставки (или визиты).
• Проблема маршрутизации транспортных средств с ограниченной емкостью: CVRP или CVRPTW. Транспортные средства имеют ограниченную грузоподъемность для грузов, которые необходимо доставить.
• Проблема маршрутизации транспортных средств с несколькими поездками (VRPMT): транспортные средства могут следовать более чем по одному маршруту.
• Открытая проблема маршрутизации транспортных средств (OVRP): транспортным средствам не требуется возвращаться на склад.
• Проблема маршрутизации запасов (IRP): транспортные средства отвечают за удовлетворение спроса в каждой точке доставки ^[7]
• Проблема маршрутизации транспортных средств с несколькими депо (MDVRP): существует несколько депо, из которых транспортные средства могут отправляться и прибывать. ^[8]
• Проблема маршрутизации транспортных средств с пересадками (VRPWT): грузы могут передаваться между транспортными средствами в специально отведенных пересадочных узлах.
• Задача маршрутизации электромобилей (EVRP): это специальные задачи VRP, которые в качестве дополнительного ограничения учитывают емкость аккумулятора электромобилей.

Несколько поставщиков программного обеспечения создали программные продукты для решения различных проблем VRP. Для получения более подробной информации об их исследованиях и результатах доступны многочисленные статьи.

Хотя VRP связана с задачей планирования работ в цехе , эти две проблемы обычно решаются с использованием разных методов. ^[9]

Точные методы решения

Существует три основных подхода к моделированию VRP:

1. Формулировки потока транспортных средств — здесь используются целочисленные переменные, связанные с каждой дугой, которые подсчитывают количество раз, которое ребро пересекается транспортным средством. Обычно это используется для базовых VRP. Это хорошо для случаев, когда стоимость решения может быть выражена как сумма любых затрат, связанных с дугами. Однако это не может использоваться для обработки многих практических приложений. ^[2]
2. Формулировки товарного потока — дополнительные целочисленные переменные связаны с дугами или ребрами, которые представляют поток товаров вдоль путей, пройденных транспортными средствами. Это только недавно было использовано для нахождения точного решения. ^[2]
3. Задача разбиения множества — они имеют экспоненциальное число двоичных переменных , каждая из которых связана с отдельной допустимой схемой. Тогда VRP вместо этого формулируется как задача разбиения множества, которая спрашивает, каков набор схем с минимальной стоимостью, удовлетворяющих ограничениям VRP. Это допускает очень общие затраты маршрута. ^[2]

Формулы расхода транспортного средства

Формулировка TSP Данцига, Фулкерсона и Джонсона была расширена для создания двух индексных формул потока транспортных средств для VRP.

${\displaystyle {\text{min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}}$

при условии

В этой формулировке представляет собой стоимость перехода от узла к узлу , является двоичной переменной, которая имеет значение , если дуга, идущая от к , рассматривается как часть решения, и в противном случае является количеством доступных транспортных средств и соответствует минимальному количеству транспортных средств, необходимых для обслуживания множества . Мы также предполагаем, что является узлом депо. ${\displaystyle c_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle x_{ij}}$ ${\displaystyle 1}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle 0}$ ${\displaystyle K}$ ${\displaystyle r(S)}$ ${\displaystyle S}$ ${\displaystyle 0}$

Ограничения 1 и 2 устанавливают, что ровно одна дуга входит и ровно одна выходит из каждой вершины, связанной с клиентом, соответственно. Ограничения 3 и 4 устанавливают, что количество транспортных средств, покидающих депо, равно количеству входящих. Ограничения 5 являются ограничениями сокращения пропускной способности, которые устанавливают, что маршруты должны быть соединены и что спрос на каждом маршруте не должен превышать пропускную способность транспортного средства. Наконец, ограничения 6 являются ограничениями целостности. ^[2]

Одно произвольное ограничение среди ограничений фактически подразумевается оставшимися, поэтому его можно удалить. Каждый разрез, определенный набором клиентов, пересекается числом дуг, не меньшим, чем ⁠ ⁠ (минимальное количество транспортных средств, необходимых для обслуживания набора ). ^[2] ${\displaystyle 2|V|}$ ${\displaystyle 2|V|-1}$ ${\displaystyle S}$ ${\displaystyle r(S)}$ ${\displaystyle S}$

Альтернативную формулировку можно получить путем преобразования ограничений по сокращению пропускной способности в обобщенные ограничения по исключению подтуров (GSEC).

${\displaystyle \sum _{i\in S}\sum _{j\in S}x_{ij}\leq |S|-r(S)}$

что требует, чтобы по крайней мере ⁠ ⁠ ${\displaystyle r(S)}$ дуги покидали каждый набор клиентов . ^[2] ${\displaystyle S}$

GCEC и CCC имеют экспоненциальное число ограничений, поэтому практически невозможно решить линейную релаксацию. Возможный способ решения этой проблемы — рассмотреть ограниченное подмножество этих ограничений и добавить остальные при необходимости. Определение необходимых ограничений выполняется с помощью процедуры разделения. Разработаны эффективные точные методы разделения для таких ограничений (основанные на смешанном целочисленном программировании). ^[10]

Другой метод заключается в использовании семейства ограничений, имеющих полиномиальную мощность, которые известны как ограничения MTZ. Они были впервые предложены для TSP ^[11] и впоследствии расширены Кристофидесом, Мингоцци и Тотом ^{[12] .}

${\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})~~~~~~\forall i,j\in V\backslash \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}$

${\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\forall i\in V\backslash \{0\}}$

где - дополнительная непрерывная переменная, которая представляет собой груз, оставленный в транспортном средстве после посещения клиента , и является спросом клиента . Они налагают как требования к подключению, так и к вместимости. Когда ограничение, то не является обязательным, поскольку и в то время как они налагают, что . ${\displaystyle u_{i},~i\in V\backslash \{0\}}$ ${\displaystyle i}$ ${\displaystyle d_{i}}$ ${\displaystyle i}$ ${\displaystyle x_{ij}=0}$ ${\displaystyle i}$ ${\displaystyle u_{i}\leq C}$ ${\displaystyle u_{j}\geq d_{j}}$ ${\displaystyle x_{ij}=1}$ ${\displaystyle u_{j}\geq u_{i}+d_{j}}$

Они широко использовались для моделирования базового VRP (CVRP) и VRPB. Однако их возможности ограничены этими простыми задачами. Их можно использовать только тогда, когда стоимость решения может быть выражена как сумма стоимости стоимости дуг. Мы также не можем знать, какое транспортное средство пересекает каждую дугу. Следовательно, мы не можем использовать это для более сложных моделей, где стоимость и/или осуществимость зависят от порядка клиентов или используемых транспортных средств. ^[2]

Оптимальная маршрутизация вручную или автоматически

Существует множество методов ручного решения проблем маршрутизации транспортных средств. Например, оптимальный маршрут — это большая проблема эффективности для погрузчиков на больших складах. Некоторые ручные методы выбора наиболее эффективного маршрута: Наибольший зазор, S-образная форма, проход за проходом, комбинированный и комбинированный + Хотя комбинированный + метод является самым сложным, поэтому его труднее всего использовать операторам погрузчиков, это самый эффективный метод маршрутизации. Тем не менее, процентная разница между ручным методом оптимального маршрута и реальным оптимальным маршрутом в среднем составила 13%. ^{[13] [14]}

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

Из-за сложности решения оптимальности крупномасштабных примеров задач маршрутизации транспортных средств значительные исследовательские усилия были посвящены метаэвристикам, таким как генетические алгоритмы , поиск с запретами , имитация отжига и адаптивный поиск в больших окрестностях (ALNS). Некоторые из самых последних и эффективных метаэвристик для задач маршрутизации транспортных средств достигают решений в пределах 0,5% или 1% от оптимума для примеров задач, насчитывающих сотни или тысячи точек доставки. ^[15] Эти методы также более надежны в том смысле, что их можно легче адаптировать для работы с различными побочными ограничениями. Таким образом, применение метаэвристических методов часто является предпочтительным для крупномасштабных приложений со сложными ограничениями и наборами решений.

Смотрите также

• Проблема китайского почтальона
• Проблема перепланировки транспортного средства
• Дуговая маршрутизация
• Список тем по теории графов

Ссылки

1. Данциг, Джордж Бернард; Рамсер, Джон Хьюберт (октябрь 1959 г.). «Проблема диспетчеризации грузовиков» (PDF) . Наука управления . 6 (1): 80–91. doi :10.1287/mnsc.6.1.80.
2. Toth, P.; Vigo, D., ред. (2002). Проблема маршрутизации транспортных средств . Монографии по дискретной математике и ее приложениям. Том 9. Филадельфия: Общество промышленной и прикладной математики. ISBN 0-89871-579-2.
3. Гейр Хасле; Кнут-Андреас Ли; Эвальд Куак, ред. (2007). Геометрическое моделирование, численное моделирование и оптимизация:: прикладная математика в SINTEF. Берлин: Springer Verlag. стр. 397–398. ISBN 978-3-540-68783-2.
4. Чао, И-Мин; Голден, Брюс Л.; Васил, Эдвард А. (1996). «Проблема командного ориентирования». Европейский журнал операционных исследований . 88 (3): 464–474. doi :10.1016/0377-2217(94)00289-4.
5. Archetti, C.; Sperenza, G.; Vigo, D. (2014). «Проблемы маршрутизации транспортных средств с прибылью». В Toth, P.; Vigo, D. (ред.). Маршрутизация транспортных средств: проблемы, методы и приложения (второе изд.). стр. 273–297. doi :10.1137/1.9781611973594.ch10.
6. Хаммами, Фарук; Рекик, Мония; Коэльо, Леандро К. (2020). «Гибридная адаптивная эвристика поиска в большом соседстве для задачи командного ориентирования». Компьютеры и исследования операций . 123 : 105034. doi : 10.1016/j.cor.2020.105034. S2CID  221134904.
7. Экичи, Али; Озенер, Окан Орсан; Куйзу, Гюльтекин (ноябрь 2015 г.). «Циклические графики доставки для задачи маршрутизации запасов». Транспортная наука . 49 (4): 817–829. дои : 10.1287/trsc.2014.0538.
8. Махмуд, Нафикс; Хак, Мд. Мокаммель (февраль 2019 г.). Решение задачи маршрутизации транспортных средств с несколькими депо (MDVRP) с использованием генетического алгоритма . Международная конференция по электротехнике, вычислительной технике и коммуникационной технике (ECCE) 2019 г. doi : 10.1109/ECACE.2019.8679429.
9. Бек, Дж. К.; Проссер, П.; Селенски, Э. (2003). «Маршрутизация транспортных средств и планирование работы цеха: в чем разница?» (PDF) . Труды 13-й Международной конференции по планированию и составлению расписаний с использованием искусственного интеллекта .
10. Павликов, К.; Петерсен, NC; Сёренсен, JL (2023). «Точное разделение округленных неравенств пропускной способности для задачи маршрутизации транспортных средств с пропускной способностью». Сети . 83. Сети: 197–209. doi : 10.1002/net.22183 . S2CID  263321558.
11. Миллер, CE; Такер, EW; Землин, RA (1960). «Формулировки целочисленного программирования и задачи коммивояжера». J. ACM . 7 : 326–329. doi : 10.1145/321043.321046 . S2CID  2984845.
12. Кристофидес, Н.; Мингоцци, А.; Тот, П. (1979). Проблема маршрутизации транспортных средств . Чичестер, Великобритания: Wiley. С. 315–338.
13. «Почему ручная оптимальная маршрутизация на складе так неэффективна?». Locatible.com . 2016-09-26 . Получено 2016-09-26 .
14. Рудберген, Кис Ян (2001). «Методы маршрутизации для складов с несколькими поперечными проходами» (PDF) . roodbergen.com . Получено 26.09.2016 .
15. Видал Т., Крейник Т.Г., Джендро М., Принс К. (2014). «Унифицированная структура решения для многоатрибутивных задач маршрутизации транспортных средств» (PDF) . Европейский журнал операционных исследований . 234 (3): 658–673. doi :10.1016/j.ejor.2013.09.045. S2CID  21037953.

Дальнейшее чтение

• Оливейра, HCBde; Васконселос, GC (2008). «Гибридный метод поиска для задачи маршрутизации транспортных средств с временными окнами». Annals of Operations Research . 180 : 125–144. doi :10.1007/s10479-008-0487-y. S2CID  32406011.
• Frazzoli, E.; Bullo, F. (2004). "Децентрализованные алгоритмы маршрутизации транспортных средств в стохастической изменяющейся во времени среде". 2004 43-я конференция IEEE по принятию решений и управлению (CDC) (IEEE Cat. No.04CH37601) . Том 4. IEEE. стр. 3357–3363. doi :10.1109/CDC.2004.1429220. ISBN 0-7803-8682-5. ISSN  0191-2216.
• Psaraftis, HN (1988). "Проблемы динамической маршрутизации транспортных средств" (PDF) . Маршрутизация транспортных средств: методы и исследования . 16 : 223–248.
• Бертсимас, DJ; Ван Райзин, G. (1991). «Стохастическая и динамическая задача маршрутизации транспортных средств в евклидовой плоскости». Исследование операций . 39 (4): 601–615. doi :10.1287/opre.39.4.601. hdl : 1721.1/2353 . JSTOR  171167.
• Видал Т., Крейник Т.Г., Джендро М., Принс К. (2013). «Эвристика для многоатрибутивных задач маршрутизации транспортных средств: обзор и синтез» (PDF) . Европейский журнал операционных исследований . 231 (1): 1–21. doi :10.1016/j.ejor.2013.02.053. S2CID  15983279.
• Хиротака, Ирие; Вонгпаисарнсин, Гораго; Тэрабе, Масаёши; Мики, Акира; Тагучи, Шиничиро (2019). «Квантовый отжиг задачи маршрутизации транспортных средств с учетом времени, состояния и пропускной способности». arXiv : 1903.06322 [quant-ph].