Er zijn drie belangrijke verschillende benaderingen voor het modelleren van de VRP

1. voertuigrouteformuleringen—dit maakt gebruik van integer variabelen geassocieerd met elke boog die het aantal keren telt dat de rand door een voertuig wordt doorkruist. Het wordt over het algemeen gebruikt voor basis VRP ‘ s. Dit is goed voor gevallen waarin de oplossingskosten kunnen worden uitgedrukt als de som van alle kosten in verband met de bogen. Het kan echter niet worden gebruikt om veel praktische toepassingen te verwerken.
2. productstroomformuleringen-aanvullende gehele variabelen worden geassocieerd met de bogen of randen die de goederenstroom langs de door de voertuigen afgelegde paden vertegenwoordigen. Dit is pas onlangs gebruikt om een exacte oplossing te vinden.
3. Set partitioneringsprobleem-deze hebben een exponentieel aantal binaire variabelen die elk geassocieerd zijn met een ander haalbaar circuit. De VRP wordt dan geformuleerd als een set partitionering probleem dat vraagt Wat is de verzameling van circuits met minimale kosten die voldoen aan de VRP beperkingen. Dit zorgt voor zeer algemene route kosten.

Voertuig flow formulationsEdit

De formulering van de TSP door Dantzig, Fulkerson en Johnson werd uitgebreid tot de twee-index voertuig flow formuleringen voor de VRP

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

onder

∑ i ∈ V x i j = 1 ∀ j ∈ V ∖ { 0 } {\displaystyle \som _{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}

j {\displaystyle j}

wordt beschouwd als deel van de oplossing en 0 {\displaystyle 0}

anders, K {\displaystyle K}

is het nummer van de beschikbare voertuigen en r ( S ) {\displaystyle r(S)}

komt overeen met het minimum aantal voertuigen dat nodig is om te dienen verzameling {\displaystyle S}

. We gaan er ook van uit dat 0 {\displaystyle 0}

de depotnode is.

restricties 1 en 2 geven aan dat er respectievelijk precies één boog binnenkomt en exact één boog verlaat elk vertex dat aan een klant is gekoppeld. Restricties 3 en 4 zeggen dat het aantal voertuigen dat het depot verlaat hetzelfde is als het aantal dat wordt ingevoerd. Beperkingen 5 zijn de capaciteitsverminderingsbeperkingen, die voorschrijven dat de routes moeten worden aangesloten en dat de vraag op elke route de voertuigcapaciteit niet mag overschrijden. Ten slotte zijn beperkingen 6 de integriteitsbeperkingen.

Eén willekeurige beperking onder de 2 | V | {\displaystyle 2|V|}

wordt in feite geïmpliceerd door de resterende 2 | V | − 1 {\displaystyle 2|V|-1}

zodat het kan worden verwijderd. Elke knip gedefinieerd door een klant verzameling {\displaystyle S}

wordt doorkruist door een aantal bogen die niet kleiner is dan r ( s ) {\displaystyle r(s)}

(minimum aantal voertuigen dat nodig is om te dienen verzameling {\displaystyle S}

).

een alternatieve formulering kan worden verkregen door de capaciteitsverminderingsbeperkingen om te zetten in algemene subtour eliminatiebeperkingen (gsecs).

∑ i ∈ S ∑ j ∈ S x i j ≤ | S | − r ( s ) {\displaystyle \som _{i\N}\som _{j\S}x_{ij}\leq |S|-r(s)}

die stelt dat ten minste r ( s ) {\displaystyle r(s)}

bogen laat elke klant verzameling {\displaystyle S}

.

GCECs en CCC ‘ s hebben een exponentieel aantal beperkingen, zodat het praktisch onmogelijk is om de lineaire ontspanning op te lossen. Een mogelijke manier om dit op te lossen is om een beperkte subset van deze beperkingen te overwegen en de rest toe te voegen indien nodig.

een andere methode is opnieuw het gebruik van een familie van beperkingen die een veelterm kardinaliteit hebben, die bekend staan als de MTZ-beperkingen.ze werden eerst voorgesteld voor de TSP en vervolgens uitgebreid door Christofides, Mingozzi en Toth.

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})~~~~~~\forall i,j\in v\backslash \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

0 ≤ i ≤ C − d i ∀ i ∈ V ∖ { 0 } {\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\forall i\V\backslash \{0\}}

waar de u i , i ∈ V ∖ { 0 } {\displaystyle u_{i}~i\V\backslash \{0\}}

is een meer continue variabele vertegenwoordigt de lading in het voertuig achtergebleven na een bezoek aan de klant i {\displaystyle i}

en d i {\displaystyle d_{i}}

is de vraag van klant i {\displaystyle i}

. Deze leggen zowel de connectiviteit als de capaciteitsvereisten op. Als x i j = 0 {\displaystyle x_{ij}=0}

beperking dan ik {\displaystyle i}

is niet bindend’ sinds u i ≤ C {\displaystyle u_{i}\leq C}

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

overwegende dat x i j = 1 {\displaystyle x_{ij}=1}

ze leggen die u j ≥ i + d j {\displaystyle u_{j}\geq u_{i}+d_{j}}

.

Deze zijn uitgebreid gebruikt om het basis VRP (CVRP) en het VRPB te modelleren. Hun macht is echter beperkt tot deze eenvoudige problemen. Zij kunnen alleen worden gebruikt wanneer de kosten van de oplossing kunnen worden uitgedrukt als de som van de kosten van de arc-kosten. We kunnen ook niet weten welk voertuig elke boog doorkruist. Daarom kunnen we dit niet gebruiken voor complexere modellen waarbij de kosten en of haalbaarheid afhankelijk is van de volgorde van de klanten of de gebruikte voertuigen.

Manual versus automatic optimum routingEdit

Er zijn vele methoden om problemen met het routeren van voertuigen handmatig op te lossen. Optimale routering is bijvoorbeeld een groot efficiëntieprobleem voor heftrucks in grote magazijnen. Enkele van de handmatige methoden om te beslissen over de meest efficiënte route zijn: grootste kloof, S-vorm, Aisle-by-aisle, gecombineerd en gecombineerd +. Terwijl de gecombineerde + – methode de meest complexe en dus de moeilijkste methode is voor heftruckoperators, is het de meest efficiënte routeringsmethode. Toch was het procentuele verschil tussen de manuele optimale routeringsmethode en de werkelijke optimale route gemiddeld 13%.