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

редактировать

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

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

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

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

Содержание

1 Постановка проблемы
2 варианта VRP
3 Точные методы решения
- 3.1 Формулировка потока транспортного средства
- 3.2 Ручная и автоматическая оптимальная маршрутизация
4 Метаэвристика
5 См. Также
6 Ссылки
7 Дополнительная литература

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

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

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

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

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

Целевая функция VRP может сильно отличаться в зависимости от конкретного применения Результатом являются лишь некоторые из наиболее распространенных целей:

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

Варианты VRP

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

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

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

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

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

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

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

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

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

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

min ∑ i ∈ V ∑ j ∈ V cijxij {\ displaystyle {\ text {min}} \ sum _ {i \ in V} \ sum _ {j \ in V} c_ {ij} x_ {ij}}

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

при условии

∑ я ∈ В xij знак равно 1 ∀ j ∈ В ∖ {0} {\ displaystyle \ sum _ {i \ in V} x_ {ij} = 1 \ quad \ forall j \ in V \ backslash \ left \ {0 \ right \}}

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

(1)

∑ j ∈ V xij = 1 ∀ i ∈ V ∖ {0} {\ displaystyle \ sum _ {j \ in V} x_ {ij} = 1 \ quad \ для всех я \ in V \ обратная косая черта \ влево \ {0 \ right \}}

{\ displaystyle \ sum _ {j \ in V} x_ {ij} = 1 \ quad \ forall i \ in V \ обратная косая черта \ left \ {0 \ right \}}

(2)

∑ я ∈ V xi 0 = K {\ displaystyle \ sum _ {i \ in V} x_ {i0} = К}

{\ displaystyle \ сумма _ {я \ in V} x_ {i0} = K}

(3)

∑ j ∈ В Икс 0 j = К {\ Displaystyle \ sum _ {j \ in V} x_ {0j} = K}

{\ displaystyle \ sum _ {j \ in V} x_ {0j} = K}

(4)

∑ я ∉ S ∑ J ∈ S xij ≥ р (S), ∀ S ⊆ V ∖ {0}, S ≠ ∅ {\ displaystyle \ sum _ {i \ notin S} \ sum _ {j \ in S} x_ {ij } \ geq r (S), ~~ \ forall S \ substeq V \ setminus \ {0 \}, S \ neq \ emptyset}

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

(5)

xij ∈ {0, 1} ∀ i, j ∈ В {\ Displaystyle х_ {ij} \ в \ {0,1 \ } \ quad \ forall i, j \ in V}

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

(6)

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

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

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

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

∑ i ∈ S ∑ j ∈ S xij ≤ | S | - r (s) {\ displaystyle \ sum _ {i \ in S} \ sum _ {j \ in S} x_ {ij} \ leq | S | -r (s)}

\ sum_ {i \ in S} \ sum_ {j \ in S} x_ {ij} \ leq | S | -r ( s)

, что предполагает, что по крайней мере $r (s) {\ displaystyle r (s)}$ ${\ displaystyle r ( s)}$ дуг покидает каждый пользовательский набор $S {\ displaystyle S}$ $S$ .

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

Снова другой метод заключается в использовании семейства ограничений, имеющих полиномиальную мощность, которые известны как ограничения MTZ. nts, они были впервые предложены для TSP, а затем расширены Кристофидесом, Мингоцци и Тотом.

u j - u i ≥ d j - C (1 - x i j) ∀ i, j ∈ V ∖ {0}, i ≠ j s.t. ди + dj ≤ C {\ displaystyle u_ {j} -u_ {i} \ geq d_ {j} -C (1-x_ {ij}) ~~~~~~ \ forall i, j \ in V \ обратная косая черта \ {0 \}, я \ neq j ~~~~ {\ text {st }} d_ {i} + d_ {j} \ leq C}

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

0 ≤ ui ≤ C - di ∀ i ∈ V ∖ {0} {\ displaystyle 0 \ leq u_ {i} \ leq C-d_ {i } ~~~~~~ \ forall i \ in V \ backslash \ {0 \}}

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

где $ui, i ∈ V ∖ {0} {\ displaystyle u_ {i}, ~ i \ in V \ backslash \ {0 \}}$ $u_i, ~ i \ in V \ backslash \ {0 \}$ - дополнительная непрерывная переменная, которая представляет нагрузку, оставшуюся в транспортном средстве после посещения клиента $i {\ displaystyle i}$ $i$ и $di {\ displaystyle d_ {i}}$ $d_ {i}$ - это спрос клиента $i {\ displaystyle i}$ $i$ . Это накладывает требования как к возможности подключения, так и к емкости. Когда $xij = 0 {\ displaystyle x_ {ij} = 0}$ $x _ {{ij}} = 0$ ограничение, тогда $i {\ displaystyle i}$ $i$ не является обязательным, поскольку $ui ≤ C {\ displaystyle u_ {i} \ leq C}$ $u_i \ leq C$ и $uj ≥ dj {\ displaystyle u_ {j} \ geq d_ {j}}$ $u_j \ geq d_j$ тогда как $xij = 1 {\ displaystyle x_ {ij} = 1}$ $x_ {ij} = 1$ они предполагают, что $uj ≥ ui + dj {\ displaystyle u_ {j} \ geq u_ {i} + d_ {j}}$ $u_j \ geq u_i + d_j$ .

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

Ручной или автоматический оптимальный маршрут

Есть много методов, как решать проблемы с маршрутизацией транспортных средств вручную. Например, оптимальная маршрутизация является большой проблемой для вилочных погрузчиков на больших складах. Некоторые из ручных методов выбора наиболее эффективного маршрута: наибольший зазор, S-образная форма, от прохода к проходу, комбинированный и комбинированный +. Хотя комбинированный + метод является наиболее сложным и, следовательно, трудным для использования операторами автопогрузчиков, он является наиболее эффективным методом маршрутизации. Тем не менее, процентная разница между ручным методом оптимальной маршрутизации и реальным оптимальным маршрутом составила в среднем 13%.

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

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

См. Также

Ссылки

Дополнительная литература

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