Problema rutării vehiculelor

Problema rutării vehiculelor (abr. en. VRP) este o problemă de optimizare combinatorică și programare în numere întregi care răspunde la întrebarea „Care este mulțimea optimă de rute pe care o flotă de vehicule să o traverseze pentru a efectua livrări către o mulțime dată de clienți?”. Aceasta generalizează binecunoscuta problemă a comis-voiajorului (abr. en. TSP). A apărut pentru prima dată într-un articol de George Dantzig și John Ramser din anul 1959,^[1] în care prima abordare algoritmică a fost publicată și aplicată livrărilor de benzină. Adesea, contextul este cel de livrare de bunuri aflate într-un depozit central către clienți care transmit comenzi pentru astfel de bunuri. Obiectivul VRP este minimizarea costului total al rutei. În anul 1964, Clarke și Wright au îmbunătățit abordarea lui Dantzig și Ramser folosind o abordare lacomă eficace denumită algoritmul economisirilor.

Determinarea soluției optime a VRP este NP-hard,^[2] astfel că mărimea problemelor care pot fi rezolvate, optim, folosind optimizarea sau optimizarea combinatorială poate fi limitată. Din această cauză, programele comerciale de soluționare tind să utilizeze euristica datorită mărimii și frecvenței VRP-urilor reale pe care trebuie să le rezolve. (Pentru explicația netehnică a dificultății VRP vedeți secțiunea Legături externe de mai jos.)

VRP are numeroase aplicații evidente în industrie. De fapt, folosirea programelor computerizate de optimizare poate conduce la economii de 5% pentru o firmă^[3] deoarece transportul este de obicei o componentă semnificativă în costul unui produs (10%)^[4] - într-adevăr, sectorul transporturilor reprezintă 10% din PIB-ul UE. Prin urmare, economiile produse de VRP, deși sub 5%, sunt semnificative.^[3]

Definirea problemei

VRP privește serviciile unei firme de livrări. Cum sunt livrate lucruri de la unul sau mai multe depozite care au un număr dat de vehicule în bază, operate de un număr de șoferi care se pot deplasa pe o rețea de drumuri dată, către un număr clienți. Se solicită determinarea unui număr de rute, S, (o rută pentru fiecare vehicul care trebuie să pornească din și sa încheie la depozitul propriu) astfel încât toate cerințele clientului și constrângerile operaționale să fie satisfăcute iar costul global al transportării să fie minimizat. Acest cost poate fi monetar, în distanță sau de altă natură.^[2]

Rețeaua de drumuri poate fi descrisă folosind un graf în care arcele sunt drumurile iar punctele sunt intersecțiile dintre acestea. Arcele pot fi orientate sau neorientate datorită prezenței posibile a străzilor cu sens unic sau a costurilor diferite pentru fiecare direcție. Fiecare arc are un cost asociat care este în general lungimea sa sau durata de mers, care poate depinde de tipul de vehicul.^[2]

Pentru a cunoaște costul global al fiecărei rute, costul și durata deplasării între fiecare client și depozit trebuie să fie cunoscute. Pentru asta graful inițial este transformat într-unul în care punctele sunt clienții și depozitul, iar arcele sunt drumurile dintre acestea. Costul pe fiecare arc este cel mai redus cost dintre cele două puncte din rețeaua de drumuri inițială. Acest lucru este ușor deoarece problemele celui mai scurt drum sunt relativ ușor de rezolvat. Aceasta transformă graful inițial rarefiat într-un graf complet. Pentru fiecare pereche de puncte i și j, există un arc (i,j) din graful complet al cărui cost este scris ca $C_{ij}$ și este definit ca fiind costul drumului minim de la i la j. Durata drumului $t_{ij}$ este suma duratelor drumurilor arcelor pe drumul minim de la i la j din graful inițial al drumurilor.

Câteodată nu este posibilă satisfacerea tuturor cerințelor clientului iar în asemenea cazuri rezolvarea poate conduce la reducerea cerințelor unor clienți sau la neservirea unor clienți. Pentru astfel de situații se poate introduce o variabilă de prioritate pentru fiecare client sau asocierea de penalități pentru serviciu parțial sau absent pentru fiecare client dat. ^[2]

Funcția obiectivă a unei VRP poate fi diferită în funcție de aplicația specifică a rezultatului dar câteva dintre obiectivele cel mai obișnuite sunt:^[2]

Minimizarea costului global de transport pe baza distanței globale parcurse precum și costurile fixe asociate vehiculelor și șoferilor folosiți
Minimizarea numărului de vehicule necesare pentru a servi toți clienții
Variație minimă a duratei de parcurs și încărcare de vehicul
Minimizarea penalităților pentru serviciu de calitate redusă

Variante ale VRP

O diagramă care prezintă relația dintre subproblemele VRP obișnuite.

Există câteva variații și specializări ale problemei rutării vehiculelor:

Problema rutării vehiculelor cu încărcare și livrare (abr. en. VRPPD): Un număr de bunuri trebuie mutate din anumite locuri de încărcare către alte locuri de livrare. Scopul este găsirea rutelor optime pentru ca o flotă de vehicule să viziteze locurile de încărcare și livrare.
Problema rutării vehiculelor cu LIFO: Similar cu VRPPD, cu excepția unei restricții suplimentare la încărcarea vehiculelor: în orice loc de livrare, articolul livrat trebuie să fie articolul care a fost încărcat cel mai recent. Această schemă reduce duratele de încărcare și descărcare în locurile de livrare deoarece nu este nevoie de o descărcare temporară a articolelor care nu trebuie descărcate imediat.
Problema rutării vehiculelor cu ferestre temporale (abr. en. VRPTW): Locurile de livrare au ferestre de timp în care trebuie efectuate livrările (sau vizitele).
Problema rutării vehiculelor cu capacitate: abr. en. CVRP sau CVRPTW. Vehiculele au capacitate de transport limitată pentru bunurile care trebuie livrate.
Problema rutării vehiculelor cu drumuri dus-întors (abr. en. VRPMT): Vehiculul poate efectua mai mult de o rută.
Problema deschisă a rutării vehiculelor (abr. en. OVRP): Vehiculele nu trebuie să se întoarcă la depozit.

Vezi și

Problema comis-voiajorului

Referințe

^ Dantzig, George Bernard; Ramser, John Hubert (octombrie 1959). „Problema dispeceratului de camioane” (PDF). Management Science. 6 (1): 80–91. doi:10.1287/mnsc.6.1.80. (en.)
^ ^a ^b ^c ^d ^e Toth, P.; Vigo, D., ed. (2002). Problema rutării vehiculelor. Monographs on Discrete Mathematics and Applications. 9. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 0-89871-579-2. (en.)
^ ^a ^b Geir Hasle; Knut-Andreas Lie; Ewald Quak, ed. (2007). Modelare geometrică, simulare numerică și optimizare:: matematică aplicată la SINTEF. Berlin: Springer Verlag. ISBN 978-3-540-68783-2. (en.)
^ Comtois, Claude; Slack, Brian; Rodrigue, Jean-Paul (2013). Geografia sistemelor de transport (ed. 3rd). London: Routledge, Taylor & Francis Group. ISBN 978-0-415-82254-1. (en.)

Lectură suplimentară

Oliveira, H.C.B.de; Vasconcelos, G.C. (2008). „O metodă de căutare hibridă pentru problema rutării vehiculelor cu ferestre de timp”. Annals of Operations Research. 180: 125–144. doi:10.1007/s10479-008-0487-y.
Frazzoli, E.; Bullo, F. (2004). „Algoritmi descentralizați pentru rutarea vehiculelor într-un mediu stocastic cu timp variabil”. 2004 43rd IEEE Conference on Decision and Control (CDC). 43rd IEEE Conference on Decision and Control, 14-17 Dec. 2004, Nassau, Bahamas. Proceedings of the ... IEEE Conference on Decision & Control. 4. IEEE. doi:10.1109/CDC.2004.1429220. ISBN 0-7803-8682-5. ISSN 0191-2216.

[DantzigRamser1959-1] Dantzig, George Bernard; Ramser, John Hubert (octombrie 1959). „Problema dispeceratului de camioane” (PDF). Management Science. 6 (1): 80–91. doi:10.1287/mnsc.6.1.80. (en.)

[toth-2] Toth, P.; Vigo, D., ed. (2002). Problema rutării vehiculelor. Monographs on Discrete Mathematics and Applications. 9. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 0-89871-579-2. (en.)

[Springer_Verlag-3] Geir Hasle; Knut-Andreas Lie; Ewald Quak, ed. (2007). Modelare geometrică, simulare numerică și optimizare:: matematică aplicată la SINTEF. Berlin: Springer Verlag. ISBN 978-3-540-68783-2. (en.)

[4] Comtois, Claude; Slack, Brian; Rodrigue, Jean-Paul (2013). Geografia sistemelor de transport (ed. 3rd). London: Routledge, Taylor & Francis Group. ISBN 978-0-415-82254-1. (en.)

[1]

[2]

[3]

[4]