det er tre hoved ulike tilnærminger til modellering VRP

1. Kjøretøy flyt formuleringer—dette bruker heltall variabler knyttet til hver bue som teller antall ganger at kanten er krysset av et kjøretøy. Den brukes vanligvis til grunnleggende VRPs. Dette er bra for tilfeller der løsningskostnaden kan uttrykkes som summen av eventuelle kostnader forbundet med buene. Men det kan ikke brukes til å håndtere mange praktiske applikasjoner.
2. Commodity flow formuleringer-flere heltall variabler er knyttet til buer eller kanter som representerer flyten av varer langs stier reist av kjøretøyene. Dette har bare nylig blitt brukt til å finne en eksakt løsning.
3. Set partisjonering problem-Disse har et eksponentielt antall binære variabler som hver er forbundet med en annen mulig krets. VRP er da i stedet formulert som et sett partisjoneringsproblem som spør hva er samlingen av kretser med minimumskostnad som tilfredsstiller VRP-begrensningene. Dette gir svært generelle rutekostnader.

Kjøretøy flow formulationsEdit

formuleringen av TSP av Dantzig, Fulkerson og Johnson ble utvidet til å opprette to indeks kjøretøy flow formuleringer for VRP

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

er underlagt

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

til j {\displaystyle j}

betraktes som en del av løsningen og 0 {\displaystyle 0}

ellers, k {\displaystyle k}

er antall tilgjengelige kjøretøy og r ( s ) {\displaystyle r(s)}

tilsvarer det minste antall kjøretøy som trengs for å betjene sett s {\displaystyle s}

. Vi antar også at 0 {\displaystyle 0}

er depotnoden.

Begrensninger 1 og 2 angir at nøyaktig en bue går inn og nøyaktig en forlater hvert toppunkt knyttet til en kunde, henholdsvis. Begrensninger 3 og 4 sier at antall kjøretøy som forlater depotet er det samme som nummeret som kommer inn. Begrensninger 5 er kapasitetskuttbegrensningene, som pålegger at rutene må kobles sammen og at etterspørselen på hver rute ikke må overstige kjøretøyets kapasitet. Endelig er begrensninger 6 integritetsbegrensningene.

en vilkårlig begrensning blant 2 | V | {\displaystyle 2|V|}

begrensninger er faktisk implisitt av de resterende 2 | V | − 1 {\displaystyle 2|V|-1}

de slik at den kan fjernes. Hvert kutt definert av et kundesett s {\displaystyle s}

krysses av et antall buer som ikke er mindre enn r ( s ) {\displaystyle r(s)}

(minimum antall kjøretøy som trengs for å betjene sett s {\displaystyle displaystyle s}

).

en alternativ formulering kan oppnås ved å transformere kapasitetskuttbegrensningene til generaliserte subtur eliminasjonsbegrensninger (GSECs).

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

Som pålegger at minst r(s) {\displaystyle r(s)}

buer forlater hvert kundesett s {\displaystyle s}

. GCECs og Ccc har et eksponentielt antall begrensninger, så det er praktisk talt umulig å løse lineær avslapping. En mulig måte å løse dette på er å vurdere en begrenset delmengde av disse begrensningene og legge til resten om nødvendig.en annen metode igjen er å bruke en familie av begrensninger som har et polynom kardinalitet som er kjent som MTZ begrensninger, de ble først foreslått FOR TSP og deretter utvidet Av Christofides, Mingozzi Og Toth. u j − u-jeg ≥ d j − C ( 1 − x i j ) ∀ i , j ∈ V ∖ { 0 } , jeg ≠ j s.t. d i + d j ≤ C {\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})~~~~~~\forall i,j\i V\omvendt skråstrek \{0\},jeg\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

0 ≤ u i ≤ C − d jeg ∀ jeg ∈ V ∖ { 0 } {\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\forall jeg\i V\omvendt skråstrek \{0\}}

hvor u-jeg , jeg ∈ V ∖ { 0 } {\displaystyle u_{i},~i\i V\omvendt skråstrek \{0\}}

er en ekstra kontinuerlig variabel som representerer legg inn igjen i bilen etter å ha besøkt kunde jeg {\displaystyle jeg}

og d i {\displaystyle d_{i}}

er etterspørselen til kunden i {\displaystyle i}

. Disse pålegger både tilkoblings-og kapasitetskravene. Når x i j = 0 {\displaystyle x_{ij}=0}

begrensning da {\displaystyle i}

er ikke bindende’ siden u i ≤ c {\displaystyle u_{i}\leq c}

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

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

de pålegger den u j ≥ u i + d j {\displaystyle u_{j}\geq u_{i}+d_{j}}

. disse har blitt brukt mye til å modellere grunnleggende VRP (CVRP) og VRPB. Men deres makt er begrenset til disse enkle problemene. De kan bare brukes når kostnaden for løsningen kan uttrykkes som summen av kostnadene for arc-kostnadene. Vi kan heller ikke vite hvilket kjøretøy som går gjennom hver bue. Derfor kan vi ikke bruke dette til mer komplekse modeller der kostnadene og gjennomførbarheten er avhengig av rekkefølgen til kundene eller kjøretøyene som brukes.

Manuell versus automatisk optimal routingEdit

det er mange metoder for å løse kjøretøy ruting problemer manuelt. For eksempel er optimal ruting et stort effektivitetsproblem for gaffeltrucker i store varehus. Noen av de manuelle metodene for å bestemme den mest effektive ruten er: Største gap, S-form, Gang-for-gang, Kombinert og Kombinert +. Mens Kombinert + metoden er den mest komplekse, og dermed den vanskeligste å bli brukt av løft lastebil operatører, er det den mest effektive rutemetode. Likevel var prosentforskjellen mellom den manuelle optimale rutingsmetoden og den virkelige optimale ruten i gjennomsnitt 13%.