Problemă de rutare a vehiculului
Problema de rutare a vehiculelor (VRP) este o clasă de probleme în domeniul cercetării operaționale . Aceste probleme tratează toate aspectele legate de gestionarea unei flote de vehicule în logistică .
Generalități ale VRP
VRP se ocupă în mod ideal de gestionarea vehiculelor din orice punct de vedere. Această clasă de probleme include o serie foarte variată: acest motiv înseamnă că astfel de probleme sunt greu de rezolvat în cel mai bun caz. Cel mai general caz implică planificarea traseului vehiculelor în prezența:
- livrări multiple
- mai multe vehicule.
Fiecare vehicul:
- poate avea mai mulți clienți.
- are capacitate de încărcare nelimitată
Fiecare client:
- are o cerere pentru un anumit produs.
Ţintă:
- minimizați costurile asociate călătoriei vehiculului (distanță, timp etc.)
- maximiza profitul.
Aceste metode trebuie:
- atribuiți un anumit set de clienți fiecărui vehicul.
- dezvoltă un traseu pentru fiecare vehicul.
Problema vânzătorului călător
Un caz particular al VRP este faimoasa problemă a vânzătorului ambulant . În acest caz, se presupune:
- un vehicul
- capacitate infinită a vehiculului
Este posibil:
- extindeți metodele soluției TSP la VRP
- descompuneți VRP în mai multe subprobleme TSP
Problema poate fi rezolvată în timpuri polinomiale numai pentru maximum două noduri, unul de plecare și unul de destinație.
Dacă solicitați computerului cea mai scurtă / mai ieftină rută pentru a conecta numeroase locații, soluția nu poate ajunge în timp uman, din cauza absenței unui algoritm care să rezolve în mod eficient problema.
Metode euristice pentru VRP
Marea complexitate a problemelor VRP face foarte dificilă, sau chiar imposibilă, calcularea soluției optime. Prin urmare, este obișnuit să procedăm prin euristică, la fel ca în cazul mai simplu al TSP. Puteți aplica la VRP:
- euristică constructivă : construiesc un set valid de soluții extinse la fiecare pas al algoritmului
- euristică iterativă : construiesc un set complet de soluții care este îmbunătățit iterativ la fiecare pas al algoritmului
Algoritmul Clarke & Wright
Este o metodă constructivă pentru soluția VRP de bază; se mai numește metoda de economisire , tocmai pentru că obiectivul este de a maximiza economiile de costuri obținute din prăbușirea mai multor căi.
Bibliografie
- Toth, P.; Vigo, D.; Problema de rutare a vehiculului. Monografii despre matematica discretă și aplicațiile sale, SIAM, (2002).
- Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2020). Un euristic hibrid adaptativ de căutare a cartierelor mari pentru problema de orientare a echipei . Calculatoare și cercetări operaționale ., 123.