Проблема с маршрутом автомобиля

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

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

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

Настройка проблемы

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

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

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

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

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

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

VRP variants

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

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

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

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

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

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

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

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

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

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

при условии

\sum _{i\in V}x_{ij}=1\quad \forall j\in V\backslash \left\{0\right\}

( 1 )

\sum _{j\in V}x_{ij}=1\quad \forall i\in V\backslash \left\{0\right\}

( 2 )

\sum _{i\in {V\backslash \left\{0\right\}}}x_{i0}=K

( 3 )

\sum _{j\in {V\backslash \left\{0\right\}}}x_{0j}=K

( 4 )

\sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S),~~\forall S\subseteq V\setminus \{0\},S\neq \emptyset

( 5 )

x_{ij}\in \{0,1\}\quad \forall i,j\in V

( 6 )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

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

[DantzigRamser1959-1] Данциг, Джордж Бернард; Рамсер, Джон Хьюберт (октябрь 1959 г.). «Проблема диспетчеризации грузовиков» (PDF) . Наука управления . 6 (1): 80–91. дои : 10.1287/mnsc.6.1.80 .

[toth-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Тот, П.; Виго, Д., ред. (2002). Проблема выбора маршрута транспортного средства . Монографии по дискретной математике и ее приложениям. Том. 9. Филадельфия: Общество промышленной и прикладной математики. ISBN 0-89871-579-2 .

[Springer_Verlag-3] Гейр Хасле; Кнут-Андреас Ли; Эвальд Квак, ред. (2007). Геометрическое моделирование, численное моделирование и оптимизация:: Прикладная математика в SINTEF . Берлин: Springer Verlag. стр. 397–398. ISBN 978-3-540-68783-2 .

[4] Чао, И-Мин; Голден, Брюс Л.; Васил, Эдвард А. (1996). «Задача командного ориентирования». Европейский журнал операционных исследований . 88 (3): 464–474. дои : 10.1016/0377-2217(94)00289-4 .

[5] Арчетти, К.; Сперенца, Г.; Виго, Д. (2014). «Проблемы маршрутизации транспортных средств с прибылью». Ин Тот, П.; Виго, Д. (ред.). Маршрут движения транспортных средств: проблемы, методы и приложения (второе изд.). стр. 273–297. дои : 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. дои : 10.1109/ECACE.2019.8679429 .

[Beck2003-9] Бек, Джей Си; Проссер, П.; Селенский, Э. (2003). «Маршрутизация транспортных средств и планирование работы цеха: в чем разница?» (PDF) . Материалы 13-й Международной конференции по планированию и планированию искусственного интеллекта .

[10] Павликов, К.; Петерсен, Северная Каролина; Соренсен, Дж.Л. (2023). «Точное разделение округленных неравенств пропускной способности для задачи выбора маршрута вместительного транспортного средства» . Сети . 83 . Сети: 197–209. дои : 10.1002/net.22183 . S2CID 263321558 .

[mtz-11] Миллер, CE; Такер, EW; Землян, Р.А. (1960). «Формулы целочисленного программирования и задачи коммивояжера» . Дж. АКМ . 7 : 326–329. дои : 10.1145/321043.321046 . S2CID 2984845 .

[christof-12] Кристофидес, Н.; Мингоцци, А.; Тот, П. (1979). Проблема выбора маршрута транспортного средства . Чичестер, Великобритания: Wiley. стр. 315–338.

[13] «Почему оптимальная маршрутизация склада вручную настолько неэффективна?» . Местоположение.com . 26 сентября 2016 г. Проверено 26 сентября 2016 г.

[14] Рудберген, Кес Ян (2001). «Методы маршрутизации для складов с несколькими поперечными проходами» (PDF) . www.rodbergen.com . Проверено 26 сентября 2016 г.

[15] Видал Т., Крайник Т.Г., Жандро М., Принс С. (2014). «Единая структура решения многоатрибутных задач маршрутизации транспортных средств» (PDF) . Европейский журнал операционных исследований . 234 (3): 658–673. дои : 10.1016/j.ejor.2013.09.045 . S2CID 21037953 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]