on olemassa kolme pääasiallista erilaista lähestymistapaa VRP: n mallintamiseen

1. Ajoneuvovirtausformulaatiot—tässä käytetään kuhunkin kaareen liittyviä kokonaislukumuuttujia, jotka laskevat, kuinka monta kertaa ajoneuvo ylittää reunan. Sitä käytetään yleensä perus VRPs. Tämä on hyvä tapauksissa, joissa ratkaisukustannukset voidaan ilmaista mahdollisten kaariin liittyvien kustannusten summana. Sitä ei kuitenkaan voi käyttää moniin käytännön sovelluksiin.
2. Tavaravirtaformulaatiot—ylimääräisiä kokonaislukumuuttujia liittyy kaariin tai reunoihin, jotka kuvaavat tavaravirtaa kulkuneuvojen kulkemia reittejä pitkin. Tällä on vasta viime aikoina pyritty löytämään tarkka ratkaisu.
3. Aseta osiointiongelma—näillä on eksponentiaalinen määrä binäärimuuttujia, jotka kukin liittyvät eri toteutuskelpoiseen piiriin. VRP on sitten sen sijaan muotoiltu joukko osiointi ongelma, joka kysyy, Mikä on kokoelma piirejä pienin kustannuksin, jotka täyttävät VRP rajoitteet. Tämä mahdollistaa hyvin yleiset reittikustannukset.

Ajoneuvon virtaus formulationsEdit

muotoilu TL by Dantzig, Biddix ja Johnson oli laajennettu luoda kaksi-indeksi ajoneuvon virtaus muotoiluja VRP

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

sovelletaan

∑ 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}

to j {\displaystyle j}

katsotaan osaksi ratkaisua ja 0 {\displaystyle 0}

muutoin k {\displaystyle k}

on käytettävissä olevien ajoneuvojen lukumäärä ja R ( S ) {\displaystyle r(s)}

vastaa joukkojen s {\displaystyle S}

. Oletamme myös, että 0 {\displaystyle 0}

on varikon solmu.

rajoitteet 1 ja 2 toteavat, että tasan yksi kaari tulee ja tasan yksi lähtee jokaisesta asiakkaaseen liittyvästä huippupisteestä. Rajoitukset 3 ja 4 kertovat, että varikolta lähtevien ajoneuvojen määrä on sama kuin sisään tulevien määrä. Rajoitteet 5 ovat kapasiteetin vähennysrajoituksia, joiden mukaan reitit on yhdistettävä ja kunkin reitin kysyntä ei saa ylittää ajoneuvokapasiteettia. Lopuksi rajoitteet 6 ovat integraalisuuden rajoitteita.

yksi mielivaltainen rajoite 2 | V | {\displaystyle 2|V|}

rajoitteet ovat itse asiassa implisiittisiä jäljelle jäävien 2 | V | − 1 {\displaystyle 2|V|-1}

ykköset, jotta se voidaan poistaa. Jokaisen asiakasjoukon s {\displaystyle S}

ylittämä kaarien lukumäärä on vähintään r ( s ) {\displaystyle r(s)}

(palvelemiseen tarvittavien ajoneuvojen vähimmäismäärä set s {\displaystyle S}

).

vaihtoehtoinen formulaatio voidaan saada muuntamalla kapasiteetin leikkausrajoitukset yleisiksi subtour elimination-rajoituksiksi (gsecs).

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

, jonka mukaan ainakin r ( s ) {\displaystyle r(s)}

kaaret jättävät jokaisen asiakasjoukon s {\displaystyle S}

.

Gceceillä ja CCC: llä on eksponentiaalinen määrä rajoitteita, joten lineaarisen relaksaation ratkaiseminen on käytännössä mahdotonta. Mahdollinen tapa ratkaista tämä on harkita rajallinen osajoukko näistä rajoitteista ja lisätä loput tarvittaessa.

toisenlainen menetelmä on jälleen käyttää rajoitteiden perhettä, jonka POLYNOMIKARDINAALISUUS tunnetaan MTZ: n rajoitteina, niitä ehdotettiin ensin TSP: lle ja myöhemmin jatkoivat Christofides, Mingozzi ja 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 ≤ u i ≤ c − d i ∀ i ∈ V ∖ { 0 } {\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~\forall i\in v\backslash \{0\}}

where u i , i ∈ v ∖ { 0 } {\displaystyle u_{i},~i\in v\backslash \{0\}}

on jatkuva lisämuuttuja, joka kuvaa kuormaa, joka jää ajoneuvoon asiakkaan i {\displaystyle i}

ja D I {\displaystyle d_{i}}

on asiakkaan I {\displaystyle i}

. Nämä asettavat sekä liitettävyys-että kapasiteettivaatimukset. Kun x i j = 0 {\displaystyle x_{ij}=0}

rajoitus silloin I {\displaystyle i}

ei ole sitova”koska u i ≤ c {\displaystyle u_{I}\leq C}

ja u j ≥ d j {\displaystyle u_{j}\geq D_{j}}

taas X i j = 1 {\displaystyle x_{IJ}=1}

ne määräävät, että u j ≥ u i + d j {\displaystyle u_{J}\geq u_{i}+D_{j}}

.

näitä on käytetty laajasti perus-VRP: n (CVRP) ja VRPB: n mallintamiseen. Niiden voima rajoittuu kuitenkin näihin yksinkertaisiin ongelmiin. Niitä voidaan käyttää vain silloin, kun ratkaisun kustannukset voidaan ilmaista valokaarikustannusten summana. Emme voi myöskään tietää, mikä ajoneuvo kulkee kunkin kaaren halki. Näin ollen emme voi käyttää tätä monimutkaisemmissa malleissa, joissa kustannukset ja toteutettavuus riippuvat asiakkaiden tai käytettyjen ajoneuvojen tilauksesta.

Manual versus automatic optimal routingEdit

on olemassa monia menetelmiä, joilla ajoneuvon reititysongelmat voidaan ratkaista manuaalisesti. Esimerkiksi optimaalinen reititys on suuri tehokkuuskysymys trukeille suurissa varastoissa. Joitakin manuaalisia menetelmiä, joilla päätetään tehokkaimmasta reitistä, ovat: suurin aukko, S-muoto, Käytäväkohtainen, yhdistetty ja yhdistetty +. Vaikka yhdistetty + – menetelmä on monimutkaisin ja siten vaikein käyttää nostoautoilijoiden, se on tehokkain reititysmenetelmä. Silti prosentuaalinen ero manuaalisen optimireititysmenetelmän ja todellisen optimireitityksen välillä oli keskimäärin 13%.