Проблема с маршрутизацией автомобиля - Vehicle routing problem

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

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

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

VRP имеет множество непосредственных применений в промышленности. Фактически, использование программ компьютерной оптимизации может дать компании экономию до 5%.^[3] так как транспортировка обычно составляет значительную часть стоимости продукта (10%)^[4] - действительно, транспортный сектор составляет 10% от ЕС ВВП. Следовательно, любая экономия, созданная VRP, даже менее 5%, является значительной.^[3]

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

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

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

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

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

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

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

Варианты VRP

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

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

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

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

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

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

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

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

Составы потока транспортных средств

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

{displaystyle {ext {min}} sum _ {iin V} sum _ {jin V} c_ {ij} x_ {ij}}

при условии

{displaystyle sum _ {iin V} x_ {ij} = 1quad forall jin V ackslash left {0ight}}

(1)

{displaystyle sum _ {jin V} x_ {ij} = 1quad для всех iin V, косая черта слева {0ight}}

(2)

{displaystyle sum _ {iin V} x_ {i0} = K}

(3)

{displaystyle sum _ {jin V} x_ {0j} = K}

(4)

{displaystyle sum _ {iotin S} sum _ {jin S} x_ {ij} geq r (S), ~~ forall Ssubseteq Vsetminus {0}, Seq emptyset}

(5)

{displaystyle x_ {ij} в {0,1} квадроциклах для всех i, jin V}

(6)

В этой формулировке ${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]

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

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

{displaystyle sum _ {iin S} sum _ {jin S} x_ {ij} leq | S | -r (s)}

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

GCEC и CCC имеют экспоненциальное количество ограничений, поэтому решить линейную релаксацию практически невозможно. Возможный способ решить эту проблему - рассмотреть ограниченное подмножество этих ограничений и при необходимости добавить остальные.

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

{displaystyle u_ {j} -u_ {i} geq d_ {j} -C (1-x_ {ij}) ~~~~~~ forall i, jin V ackslash {0}, ieq j ~~~~ {ext {ул }} d_ {i} + d_ {j} leq C}

{displaystyle 0leq u_ {i} leq C-d_ {i} ~~~~~~ forall iin V ackslash {0}}

куда ${displaystyle u_ {i}, ~ iin V ackslash {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]Эти методы также более надежны в том смысле, что их легче адаптировать для работы с различными побочными ограничениями. Таким образом, применение метаэвристических методов часто предпочтительнее для крупномасштабных приложений со сложными ограничениями и наборами решений.

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

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

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

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

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

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

[4] Комтуа, Клод; Слэк, Брайан; Родриг, Жан-Поль (2013). География транспортных систем (3-е изд.). Лондон: Routledge, Taylor & Francis Group. ISBN 978-0-415-82254-1.

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

[6] Archetti, C .; Sperenza, G .; Виго, Д. (2014). «Проблемы маршрутизации транспортных средств с прибылью»: 273–297. Дои:10.1137 / 1.9781611973594.ch10. Цитировать журнал требует | журнал = (Помогите)

[7] Хаммами, Фарук; Рекик, Моня; Коэльо, Леандро К. (2020). «Гибридная адаптивная эвристика поиска больших окрестностей для задачи командного ориентирования». Компьютеры и исследования операций. 123: 105034. Дои:10.1016 / j.cor.2020.105034.

[8] Экичи, Али; Озенер, Окан Орсан; Куйзу, Гюлтекин (ноябрь 2015 г.). «Циклические графики доставки для задачи маршрутизации инвентаря». Транспортная наука. 49 (4): 817–829. Дои:10.1287 / trsc.2014.0538.

[9] Махмуд, Нафикс; Хак, штат Мэриленд, Мокаммель (февраль 2019 г.). Решение проблемы маршрутизации нескольких транспортных средств (MDVRP) с использованием генетического алгоритма. Международная конференция по электротехнике, вычислительной технике и коммуникационной технике 2019 г. (ECCE). Дои:10.1109 / ECACE.2019.8679429.

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

[mtz-11] Miller, C.E .; Tucker, E.W .; Землин, Р. А. (1960). "Целочисленные формулировки программирования и задачи коммивояжера". J. ACM. 7: 326–329. Дои:10.1145/321043.321046. S2CID 2984845.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]