det finns tre huvudsakliga olika metoder för att modellera VRP

1. Vehicle flow formuleringar—detta använder heltal variabler associerade med varje båge som räknar antalet gånger som kanten korsas av ett fordon. Det används vanligtvis för grundläggande VRP. Detta är bra för fall där lösningskostnaden kan uttryckas som summan av eventuella kostnader i samband med bågarna. Men det kan inte användas för att hantera många praktiska tillämpningar.
2. Råvaruflödesformuleringar-ytterligare heltalsvariabler är associerade med bågarna eller kanterna som representerar flödet av varor längs de vägar som fordonen färdas. Detta har bara nyligen använts för att hitta en exakt lösning.
3. ange partitioneringsproblem – dessa har ett exponentiellt antal binära variabler som var och en är associerade med en annan genomförbar krets. VRP formuleras istället som ett setpartitioneringsproblem som frågar vad som är samlingen av kretsar med minimikostnad som uppfyller VRP-begränsningarna. Detta möjliggör mycket allmänna ruttkostnader.

Fordon flöde formulationsEdit

Den formulering av TSP från Danzig, Fulkerson och Johnson var utvidgas till att skapa de två index fordon flöde formuleringar för VRP

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

motiv till

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

till j {\displaystyle j}

betraktas som en del av lösningen och 0 {\displaystyle 0}

annars, k {\displaystyle K}

är antalet tillgängliga fordon och r ( s ) {\displaystyle r(s)}

motsvarar det minsta antalet fordon som behövs för att betjäna set s {\displaystyle s}

. Vi antar också att 0 {\displaystyle 0}

är depotnoden.

Begränsningar 1 och 2 anger att exakt en båge kommer in och exakt en lämnar varje toppunkt som är associerad med en kund. Begränsningar 3 och 4 säger att antalet fordon som lämnar depån är detsamma som numret som kommer in. Begränsningar 5 är kapacitetsbegränsningarna, som innebär att rutterna måste anslutas och att efterfrågan på varje rutt inte får överstiga fordonskapaciteten. Slutligen är begränsningar 6 integralitetsbegränsningarna.

en godtycklig begränsning bland 2 | V | {\displaystyle 2|V|}

begränsningar är faktiskt underförstått av de återstående 2 | V | − 1 {\displaystyle 2|V|-1}

sådana så att den kan tas bort. Varje snitt som definieras av en kunduppsättning s {\displaystyle s}

korsas av ett antal bågar som inte är mindre än r ( s ) {\displaystyle r(s)}

(minsta antal fordon som behövs för att betjäna set s {\displaystyle s}

).

en Alternativ formulering kan erhållas genom att omvandla kapacitetsbegränsningarna till generella subtour elimination constraints (gsecs). jag är en av de mest kända och mest kända av dessa är:

som innebär att minst r(s) {\displaystyle r ( s)}

bågar lämnar varje kunduppsättning s{\displaystyle s}

.

GCECs och CCC har ett exponentiellt antal begränsningar så det är praktiskt taget omöjligt att lösa den linjära avkopplingen. Ett möjligt sätt att lösa detta är att överväga en begränsad delmängd av dessa begränsningar och lägga till resten om det behövs.

en annan metod är igen att använda en familj av begränsningar som har en polynom kardinalitet som kallas MTZ-begränsningarna, de föreslogs först för TSP och utvidgades därefter av Christofides, Mingozzi och Toth.

u j − u jag ≥ d-j − K ( 1 − x i j ) ∀ i , j ∈ V ∖ { 0 } , jag ≠ j s.t. d jag + d j ≤ K {\displaystyle u_{j}-u_{jag}\geq d_{j}-C(1-x_{ij})~~~~~~\forall jag,j\i V\bakstreck \{0\},jag\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

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

där u jag , jag ∈ V ∖ { 0 } {\displaystyle u_{i},~i\V\bakstreck \{0\}}

är en extra kontinuerlig variabel som representerar lasten kvar i bilen efter att ha besökt en kund i {\displaystyle jag}

och d jag {\displaystyle d_{i}}

är kundens efterfrågan i {\displaystyle i}

. Dessa ställer både anslutnings-och kapacitetskraven. När x i j = 0 {\displaystyle x_{ij}=0}

begränsning då jag {\displaystyle i}

är inte bindande’ eftersom u i i} \leq C}

och u J. C. J {\displaystyle u_{J} \GEQ d_ {j}}

medan X I J = 1 {\displaystyle x_{IJ}=1}

de ålägger att u J. I. O. I + D. J {\displaystyle u_{J} \geq u_ {i}+d_{j}}

.

dessa har använts i stor utsträckning för att modellera den grundläggande VRP (CVRP) och VRPB. Men deras makt är begränsad till dessa enkla problem. De kan endast användas när kostnaden för lösningen kan uttryckas som summan av kostnaderna för arc-kostnaderna. Vi kan inte heller veta vilket fordon som passerar varje båge. Därför kan vi inte använda detta för mer komplexa modeller där kostnaden och eller genomförbarheten är beroende av kundens order eller de fordon som används.

Manuell kontra automatisk optimal routingEdit

det finns många metoder för att lösa fordonsdirigeringsproblem manuellt. Till exempel är optimal routing en stor effektivitetsfråga för gaffeltruckar i stora lager. Några av de manuella metoderna för att bestämma den mest effektiva rutten är: största gap, S-form, gång-för-gång, kombinerad och kombinerad +. Medan Combined + – metoden är den mest komplexa och därmed den svåraste att använda av truckoperatörer, är den den mest effektiva dirigeringsmetoden. Ändå var den procentuella skillnaden mellan den manuella optimum routing-metoden och den verkliga optimum-rutten i genomsnitt 13%.