Es gibt drei verschiedene Ansätze zur Modellierung der VRP

1. Fahrzeugflussformulierungen — dies verwendet ganzzahlige Variablen, die jedem Bogen zugeordnet sind, die zählen, wie oft die Kante von einem Fahrzeug durchquert wird. Es wird im Allgemeinen für grundlegende VRPs verwendet. Dies ist gut für Fälle, in denen die Lösungskosten als Summe aller mit den Bögen verbundenen Kosten ausgedrückt werden können. Es kann jedoch nicht für viele praktische Anwendungen verwendet werden.
2. Warenflussformulierungen — Den Bögen oder Kanten sind zusätzliche ganzzahlige Variablen zugeordnet, die den Warenfluss entlang der von den Fahrzeugen zurückgelegten Wege darstellen. Dies wurde erst kürzlich verwendet, um eine genaue Lösung zu finden.
3. Set-Partitionierungsproblem – Diese haben eine exponentielle Anzahl von binären Variablen, die jeweils einer anderen möglichen Schaltung zugeordnet sind. Das VRP wird dann stattdessen als ein Satzpartitionierungsproblem formuliert, das fragt, was die Sammlung von Schaltungen mit minimalen Kosten ist, die die VRP-Einschränkungen erfüllen. Dies ermöglicht sehr allgemeine Routenkosten.

Fahrzeug-flow formulationsEdit

Die Formulierung des TSP, die von Dantzig, Fulkerson und Johnson wurde erweitert, um das erstellen der beiden index-Fahrzeug-flow-Formulierungen für die VRP

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

unter den

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

In this formulation c i j {\displaystyle c_{ij}}

represents the cost of going from node i {\displaystyle i}

to node j {\displaystyle j}

, x i j {\displaystyle x_{ij}}

is a binary variable that has value 1 {\displaystyle 1}

if the arc going from i {\displaystyle i}

bis j {\displaystyle j}

wird als Teil der Lösung betrachtet und 0 {\displaystyle 0}

andernfalls wird K {\displaystyle K}

K

ist die Anzahl der verfügbaren Fahrzeuge und r ( S ) {\displaystyle r(S)}

entspricht der minimalen Anzahl von Fahrzeugen, die benötigt werden, um die Menge S {\displaystyle S}

zu bedienen . Wir nehmen auch an, dass 0 {\displaystyle 0}

der Depotknoten ist.

Die Einschränkungen 1 und 2 geben an, dass genau ein Bogen in jeden Scheitelpunkt eintritt und genau einer jeden Scheitelpunkt verlässt, der einem Kunden zugeordnet ist. Einschränkungen 3 und 4 besagen, dass die Anzahl der Fahrzeuge, die das Depot verlassen, mit der Anzahl der eintretenden Fahrzeuge übereinstimmt. Einschränkungen 5 sind die Kapazitätsreduzierungsbeschränkungen, die vorschreiben, dass die Routen verbunden sein müssen und dass die Nachfrage auf jeder Route die Fahrzeugkapazität nicht überschreiten darf. Schließlich sind die Einschränkungen 6 die Integritätsbeschränkungen.

Eine beliebige Einschränkung unter den 2 | V | {\displaystyle 2|V|}

Einschränkungen wird tatsächlich durch die verbleibenden impliziert 2 | V | − 1 {\displaystyle 2|V|-1}

Einsen, damit es entfernt werden kann. Jeder Schnitt, der von einem Kundensatz S {\displaystyle S}

definiert wird, wird von einer Anzahl von Bögen gekreuzt, die nicht kleiner als r ( s ) {\displaystyle r(s)}

sind (Mindestanzahl von Fahrzeugen, die benötigt werden, um den Satz S {\displaystyleS ). Eine alternative Formulierung kann erhalten werden, indem die Kapazitätskürzungs-Beschränkungen in generalisierte Subtour Elimination Constraints (GSECs) umgewandelt werden. ∑ i ∈ S ∑ j ∈ S x i j ≤ | S | − r ( s ) {\displaystyle \Summe _{i\in S}\Summe _{j\in S}x_{ij}\leq |S|-r(s)}

was bedeutet, dass mindestens r (s ) {\displaystyle r(s)}

Bögen jeden Kundensatz verlassen S {\displaystyle S}

.

GCECs und CCCs haben eine exponentielle Anzahl von Einschränkungen, so dass es praktisch unmöglich ist, die lineare Relaxation zu lösen. Eine Möglichkeit, dies zu lösen, besteht darin, eine begrenzte Teilmenge dieser Einschränkungen zu berücksichtigen und den Rest bei Bedarf hinzuzufügen.Eine andere Methode besteht wiederum darin, eine Familie von Einschränkungen zu verwenden, die eine polynomiale Kardinalität aufweisen, die als MTZ-Einschränkungen bekannt sind. Sie wurden zuerst für die TSP vorgeschlagen und anschließend von Christofides, Mingozzi und Toth erweitert.

u j – u i ≥ d j – C ( 1 − x i j ) ∀ i , j ∈ V ∖ { 0 } , i ≠ j s.t. d i + d j ≤ C {\displaystyle u_{j}-u_{i}\geq d_{j}-C(1- x_{ij})~~~~~~\füralles i,j\in V\backslash \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

0 ≤ u i ≤ C − d i ∀ i ∈ V ∖ { 0 } {\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\füralles i\in V\backslash \{0\}}

wobei u i , i ∈ V ∖ { 0 } {\displaystyle u_{i},~i\in V\backslash \{0\}}

ist eine zusätzliche stetige Variable, die die Last darstellt, die nach dem Besuch des Kunden im Fahrzeug verbleibt i {\displaystyle i}

und d i {\displaystyle d_{i}}

ist die Nachfrage des Kunden i {\displaystyle i}

. Diese stellen sowohl die Konnektivitäts- als auch die Kapazitätsanforderungen. Wenn x i j = 0 {\displaystyle x_{ij}=0}

Einschränkung dann i {\displaystyle i}

ist nicht bindend‘ da u i ≤ C {\displaystyle u_{i}\leq C}

und u j ≥ d j {\displaystyle u_{j}\geq d_{j}}

wobei x i j = 1 {\displaystyle x_{ij}=1}

sie legen fest, dass u j ≥ u i + d j {\displaystyle u_{j}\geq u_{i}+d_{j}}

.

Diese wurden ausgiebig verwendet, um das grundlegende VRP (CVRP) und das VRPB zu modellieren. Ihre Macht beschränkt sich jedoch auf diese einfachen Probleme. Sie können nur verwendet werden, wenn die Kosten der Lösung als Summe der Kosten der Lichtbogenkosten ausgedrückt werden können. Wir können auch nicht wissen, welches Fahrzeug jeden Bogen durchquert. Daher können wir dies nicht für komplexere Modelle verwenden, bei denen die Kosten und / oder die Machbarkeit von der Bestellung der Kunden oder den verwendeten Fahrzeugen abhängen.

Manuelle versus automatische Fahrzeugroutingedit

Es gibt viele Methoden, wie Fahrzeugrouting-Probleme manuell gelöst werden können. Zum Beispiel ist optimales Routing ein großes Effizienzproblem für Gabelstapler in großen Lagern. Einige der manuellen Methoden, um die effizienteste Route zu bestimmen, sind: Größte Lücke, S-Form, Gang für Gang, Kombiniert und Kombiniert +. Während die kombinierte Routing-Methode am komplexesten ist und daher am schwierigsten von Gabelstaplern verwendet werden kann, ist sie die effizienteste Routing-Methode. Dennoch betrug der prozentuale Unterschied zwischen der manuellen optimalen Routingmethode und der realen optimalen Route im Durchschnitt 13%.