Existují tři hlavní odlišné přístupy k modelování VRP

1. Vozidlo tok formulací—používá celočíselné proměnné spojené s každou oblouk, který se počítat, kolikrát, že edge je projet vozidla. Obvykle se používá pro základní VRP. To je dobré pro případy, kdy lze náklady na řešení vyjádřit jako součet všech nákladů spojených s oblouky. Nicméně to nemůže být použit pro zpracování mnoha praktických aplikací.
2. formulace toku komodit—další celočíselné proměnné jsou spojeny s oblouky nebo hranami, které představují tok komodit podél cest, které projíždějí vozidly. To bylo teprve nedávno použito k nalezení přesného řešení.
3. Set partitioning problem—tyto mají exponenciální počet binárních proměnných, které jsou spojeny s jiným proveditelným obvodem. VRP je pak místo toho formulován jako problém s rozdělením sady, který se ptá, Jaký je sběr obvodů s minimálními náklady, které splňují omezení VRP. To umožňuje velmi obecné náklady na trasu.

Vozidlo tok formulationsEdit

složení TSP tím, Dantzig, Fulkerson a Johnson byl rozšířen vytvořit dvě index vozidlo tok přípravky pro VRP

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

téma

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

j {\displaystyle j}

je považován za součást řešení a 0 {\displaystyle 0}

jinak, K {\displaystyle K}

je počet dostupných vozidel a r ( S ) {\displaystyle r(Y)}

odpovídá minimálního počtu vozidel potřebných k sloužit set S {\displaystyle}

. Předpokládáme také, že 0 {\displaystyle 0}

je depotní uzel.

omezení 1 a 2 uvádějí, že přesně jeden oblouk vstoupí a přesně jeden opustí každý vrchol spojený se zákazníkem. Omezení 3 a 4 říkají, že počet vozidel opouštějících depo je stejný jako počet vstupujících. Omezení 5 jsou omezení snížení kapacity, která ukládají, že trasy musí být propojeny a že poptávka na každé trase nesmí překročit kapacitu vozidla. Konečně, omezení 6 jsou integrální omezení.

Jeden svévolné omezení mezi 2 | V | {\displaystyle 2|V|}

omezení je ve skutečnosti předpokládané zbývající 2 | V | − 1 {\displaystyle 2|V|-1}

takže to může být odstraněn. Každý řez definovanými zákazníkem set S {\displaystyle Y}

je protkána řadou oblouků nesmí být menší než r ( s ) {\displaystyle r(y)}

(minimálního počtu vozidel potřebných k sloužit set S {\displaystyle}

).

alternativní formulace může být získána transformací omezení snížení kapacity na generalizovaná omezení eliminace podtour (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(y)}

, které ukládá, že nejméně r ( s ) {\displaystyle r(y)}

oblouků nechat každý zákazník nastavit Y {\displaystyle}

.

Gcec a CCC mají exponenciální počet omezení, takže je prakticky nemožné vyřešit lineární relaxaci. Možným způsobem, jak to vyřešit, je zvážit omezenou podmnožinu těchto omezení a v případě potřeby přidat zbytek.

jiný způsob je opět použít rodinu omezení, které mají polynomiální mohutnost, které jsou známé jako MTZ omezení, byly poprvé navržena pro TSP a následně rozšířena o Christofides, Mingozzi a 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\zpětné lomítko \{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\zpětné lomítko \{0\}}

kde u i , i ∈ V ∖ { 0 } {\displaystyle u_{i},~i\v V\zpětné lomítko \{0\}}

je další kontinuální proměnné, která představuje zatížení nechal ve vozidle po návštěvě zákazníka jsem {\displaystyle i}

a d i {\displaystyle d_{i}}

je požadavek zákazníka jsem {\displaystyle i}

. Ty ukládají požadavky na konektivitu i kapacitu. Když x i j = 0 {\displaystyle x_{ij}=0}

omezení pak jsem {\displaystyle i}

není závazný, protože u i ≤ C {\displaystyle u_{i}\leq C}

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

vzhledem k tomu, že x i j = 1 {\displaystyle x_{ij}=1}

ukládají, že u j ≥ u i + d j {\displaystyle u_{j}\geq u_{i}+d_{j}}

.

tyto byly široce používány k modelování základního VRP (CVRP) a VRPB. Jejich síla je však omezena na tyto jednoduché problémy. Mohou být použity pouze tehdy, když náklady na řešení mohou být vyjádřeny jako součet nákladů na náklady na oblouk. Nemůžeme také vědět, které vozidlo prochází každým obloukem. Proto to nemůžeme použít pro složitější modely, kde cena a proveditelnost závisí na pořadí zákazníků nebo použitých vozidel.

manuální versus automatické optimální směrováníedit

existuje mnoho způsobů, jak vyřešit problémy s směrováním vozidel ručně. Například optimální směrování je velkým problémem pro vysokozdvižné vozíky ve velkých skladech. Některé z manuálních metod, jak rozhodnout o nejefektivnější trase, jsou: největší mezera, tvar S, ulička po uličce, kombinované a kombinované +. Zatímco kombinovaná metoda + je nejsložitější, a proto nejtěžší pro provozovatele výtahových vozidel, je to nejúčinnější metoda směrování. Přesto byl procentuální rozdíl mezi metodou manuálního optimálního směrování a skutečnou optimální trasou v průměru 13%.