három fő különböző megközelítés létezik a VRP

1. Járműáramlási formulációk modellezésére—ez az egyes ívekhez társított egész változókat használja, amelyek megszámolják, hogy hányszor halad át az él egy jármű által. Általában az alapvető VRP-khez használják. Ez jó azokban az esetekben, amikor a megoldás költsége az ívekkel kapcsolatos költségek összegeként fejezhető ki. Azonban nem használható számos gyakorlati alkalmazás kezelésére.
2. Áruáramlási formulációk—további Egész változók társulnak az ívekhez vagy élekhez, amelyek az áruk áramlását képviselik a járművek által megtett utak mentén. Ezt csak a közelmúltban használták a pontos megoldás megtalálásához.
3. Set particionálási probléma-ezek exponenciális számú bináris változóval rendelkeznek, amelyek mindegyike más megvalósítható áramkörhöz kapcsolódik. A VRP – t ezután egy meghatározott particionálási problémaként fogalmazzák meg, amely megkérdezi, hogy mi a minimális költségű áramkörök gyűjteménye, amelyek kielégítik a VRP korlátait. Ez nagyon általános útköltségeket tesz lehetővé.

Jármű flow formulationsEdit

A megfogalmazása a TK által Dantzig, Fulkerson Johnson meghosszabbították, hogy hozzon létre a két index jármű flow készítmények a VRP

min ∑ én ∈ V ∑ j ∈ V c i j x j {\displaystyle {\text{min}}\összeg _{i\V}\összeg _{j\V}c_{ij}x_{ij}}

a témát, hogy

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

a megoldás részét képezi, és 0 {\displaystyle 0}

egyébként, k {\displaystyle k}

a rendelkezésre álló járművek száma és R ( K ) {\displaystyle R(S)}

megfelel az S sorozat kiszolgálásához szükséges járművek minimális számának {\displaystyle s}

. Azt is feltételezzük, hogy 0 {\displaystyle 0}

a depó csomópont.

az 1.és a 2. megszorítás kimondja, hogy pontosan egy ív lép be, és pontosan egy elhagyja az ügyfélhez társított csúcsokat. A 3.és 4. megszorítás szerint a raktárból kilépő járművek száma megegyezik a belépő számmal. Az 5. megszorítások a kapacitáscsökkentési korlátozások, amelyek előírják, hogy az útvonalakat össze kell kapcsolni, és hogy az egyes útvonalakon a kereslet nem haladhatja meg a jármű kapacitását. Végül a 6. megszorítások az integralitás korlátai.

a 2 | V | {\displaystyle 2|v|}

megszorítások közül egy tetszőleges korlátot a fennmaradó 2 | V | − 1 {\displaystyle 2|V|-1}

így eltávolítható. Az S {\displaystyle s}

ügyfélcsoport által meghatározott vágásokat nem kisebb ívek keresztezik, mint r ( s ) {\displaystyle r(s)}

(a kiszolgáláshoz szükséges járművek minimális száma) Set s {\displaystyle s}

).

alternatív formulációként a kapacitáscsökkentési megszorítások generalizált subtour eliminációs megszorításokká (gsecs) történő átalakításával lehet előállítani.

{\displaystyle \sum _{I\in s}\sum _{j\in s}x_{ij}\leq | S | − r ( s)}

amely előírja, hogy legalább r(s) {\displaystyle R ( S)}

ívek hagyják el az S {\displaystyle s}

ügyfélkészletet .

a Gcec-k és a CCC-k exponenciális számú korlátozással rendelkeznek, így gyakorlatilag lehetetlen megoldani a lineáris relaxációt. A megoldás egyik lehetséges módja, ha figyelembe vesszük ezeknek a korlátozásoknak egy korlátozott részhalmazát, és szükség esetén hozzáadjuk a többit.

egy másik módszer ismét az, hogy egy család megszorítások, amelyek egy polinom kardinalitása, amelyek az úgynevezett MTZ megszorítások, ezeket először javasolta a TSP, majd kiterjesztette Christofides, Mingozzi és Toth. u j − u i ≥ d j − C ( 1 − x j), ∀ i , j ∈ V ∖ { 0 } , i ≠ j s.t. d + d j ≤ C {\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})~~~~~~\mindazt, i,j\a V\backslash \{0\},én\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

0 ≤ u i ≤ C − d i ∀ én ∈ V ∖ { 0 } {\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\mindazt, én\a V\backslash \{0\}}

ahol u , én ∈ V ∖ { 0 } {\displaystyle u_{i},~i\a V\backslash \{0\}}

további folyamatos változó, amely a terhelés maradt a jármű után látogató, vásárló i {\displaystyle úgy}

, majd a d i {\displaystyle d_{i}}

az ügyfél igénye i {\displaystyle i}

. Ezek mind a csatlakozási, mind a kapacitási követelményeket előírják. Amikor x i j = 0 {\displaystyle x_{IJ}=0}

megszorítás, akkor i {\displaystyle i}

nem kötelező’ mivel u i\c\displaystyle u_ {I}\leq C}

és u j d j {\displaystyle u_ {J}\GEQ D_{J}}

míg X I J = 1 {\displaystyle x_ {IJ}=1}

azt írják elő, hogy u j o i + d j {\displaystyle u_ {J} \GEQ u_{i}+D_{j}}

.

ezeket széles körben használták a basic VRP (CVRP) és a VRPB modellezésére. Hatalmuk azonban ezekre az egyszerű problémákra korlátozódik. Csak akkor használhatók, ha a megoldás költsége az ívköltségek költségeinek összegeként fejezhető ki. Azt sem tudjuk, hogy melyik jármű halad át az egyes íveken. Ezért nem használhatjuk ezt bonyolultabb modelleknél, ahol a költség vagy a megvalósíthatóság az ügyfelek megrendelésétől vagy a használt járművektől függ.

kézi versus automatikus optimális útvonalszerkesztés

számos módszer létezik a jármű útvonalválasztási problémáinak kézi megoldására. Például az optimális útválasztás nagy hatékonysági kérdés a nagy raktárakban lévő targoncák számára. Néhány kézi módszer a leghatékonyabb útvonal eldöntésére: legnagyobb rés, S-alak, folyosóról folyosóra, kombinált és kombinált +. Míg a kombinált + módszer a legösszetettebb, így a legnehezebb a targonca-üzemeltetők számára, ez a leghatékonyabb útválasztási módszer. A kézi optimális útvonal és a valódi optimális útvonal közötti százalékos különbség átlagosan 13% volt.