există trei abordări principale diferite pentru modelarea formulărilor de flux ale vehiculului VRP

1. —aceasta utilizează variabile întregi asociate fiecărui arc care numără de câte ori marginea este traversată de un vehicul. Este utilizat în general pentru VRP-uri de bază. Acest lucru este bun pentru cazurile în care costul soluției poate fi exprimat ca suma oricăror costuri asociate arcurilor. Cu toate acestea, nu poate fi folosit pentru a gestiona multe aplicații practice. formulările fluxului de mărfuri—variabile întregi suplimentare sunt asociate cu arcele sau marginile care reprezintă fluxul de mărfuri de-a lungul căilor parcurse de vehicule. Acest lucru a fost folosit doar recent pentru a găsi o soluție exactă.
2. setați problema de partiționare—acestea au un număr exponențial de variabile binare care sunt fiecare asociate cu un circuit fezabil diferit. VRP este apoi formulat ca o problemă de partiționare setată care întreabă Care este colecția de circuite cu costuri minime care satisfac constrângerile VRP. Acest lucru permite costuri de traseu foarte generale.

fluxul de Vehicul formulationsEdit

formularea de LINGURITA de Dantzig, Fulkerson și Johnson a fost extins pentru a crea două indicele vehicul fluxul de formulări pentru VRP

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

subiect

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

la j {\displaystyle j}

este considerat ca parte a soluției și 0 {\displaystyle 0}

altfel, k {\displaystyle k}

este numărul de vehicule disponibile și R ( S ) {\displaystyle r(s)}

corespunde numărului minim de vehicule necesare pentru a servi setul s {\displaystyle S}

. De asemenea, presupunem că 0 {\displaystyle 0}

este nodul de depozit.

constrângerile 1 și 2 afirmă că exact un arc intră și exact unul părăsește fiecare vârf asociat cu un client, respectiv. Constrângerile 3 și 4 spun că numărul de vehicule care părăsesc depozitul este același cu numărul care intră. Constrângerile 5 sunt constrângerile de reducere a capacității, care impun ca rutele să fie conectate și ca cererea pentru fiecare rută să nu depășească capacitatea vehiculului. În cele din urmă, constrângerile 6 sunt constrângerile de integralitate.

o constrângere arbitrară între cele 2 | V | {\displaystyle 2|v|}

constrângeri este de fapt implicată de restul de 2 | V | − 1 {\displaystyle 2|V|-1}

Cele astfel încât să poată fi eliminate. Fiecare tăiere definită de un set de clienți S {\displaystyle S}

este traversată de un număr de arce nu mai mici de r ( S ) {\displaystyle r(s)}

(numărul minim de vehicule necesare pentru a servi Set s {\displaystyle S}

).

o formulare alternativă poate fi obținută prin transformarea constrângerilor de reducere a capacității în constrângeri generalizate de eliminare a subturilor (Gsec).

care impune ca cel puțin r ( s ) {\displaystyle r(s)}

arcele să părăsească fiecare set de clienți s {\displaystyle S}

.

Gcec-urile și CCC-urile au un număr exponențial de constrângeri, astfel încât este practic imposibil să se rezolve relaxarea liniară. O modalitate posibilă de a rezolva acest lucru este să luați în considerare un subset limitat al acestor constrângeri și să adăugați restul, dacă este necesar.

o altă metodă este din nou de a folosi o familie de constrângeri care au o cardinalitate polinomială cunoscută sub numele de constrângeri MTZ, au fost propuse mai întâi pentru TSP și ulterior extinse de Christofides, Mingozzi și 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})~~~~~~\pentrutoate i,j\la V\backslash \{0\},m\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}~~~~~~\pentrutoate am\la V\backslash \{0\}}

în cazul în care u i , i ∈ V ∖ { 0 } {\displaystyle u_{i},~n\la V\backslash \{0\}}

este o altă variabilă continuă care reprezintă sarcina lăsat în autovehicul după ce a vizitat client {\displaystyle i}

și d i {\displaystyle d_{i}}

este cererea clientului i {\displaystyle i}

. Acestea impun atât cerințele de conectivitate, cât și cele de capacitate. Când X i j = 0 {\displaystyle x_{ij}=0}

constrângere atunci i {\displaystyle i}

nu este obligatoriu’ din moment ce u i i} \leq c}

și u j inkt d j {\displaystyle u_{J} \GEQ D_ {J}}

întrucât X i j = 1 {\displaystyle x_{IJ}=1}

ei impun ca u j u i + d j {\displaystyle u_{J} \GEQ u_ {i}+D_{J}}

.

acestea au fost utilizate pe scară largă pentru a modela VRP de bază (CVRP) și VRPB. Cu toate acestea, puterea lor este limitată la aceste probleme simple. Acestea pot fi utilizate numai atunci când costul soluției poate fi exprimat ca suma costurilor costurilor arc. De asemenea, nu putem ști ce vehicul traversează fiecare arc. Prin urmare, nu putem folosi acest lucru pentru modele mai complexe în care costul și fezabilitatea depind de comanda clienților sau a vehiculelor utilizate.

manual versus automat optim routingEdit

există multe metode de rezolvare manuală a problemelor de rutare a vehiculelor. De exemplu, rutarea optimă este o problemă mare de eficiență pentru stivuitoarele din depozitele mari. Unele dintre metodele manuale pentru a decide asupra celei mai eficiente rute sunt: cel mai mare decalaj, forma S, culoar cu culoar, combinat și combinat +. În timp ce metoda combinată + este cea mai complexă, deci cea mai greu de utilizat de către operatorii de camioane de ridicare, este cea mai eficientă metodă de rutare. Totuși, diferența procentuală dintre metoda de rutare optimă manuală și ruta optimă reală a fost în medie de 13%.