← All articles

Algoritmi VRP: kako delujejo in kdaj jih uporabiti

Algoritmi VRP: kako delujejo in kdaj jih uporabiti

Načrtovalka pregleduje poti dostavnih vozil

Algoritmi VRP (Vehicle Routing Problem, problem usmerjanja vozil) iz seznama naročil, lokacij strank in razpoložljivih vozil izračunajo, katero vozilo obišče katere stranke in v kakšnem vrstnem redu, da so skupni stroški poti čim nižji. Pri tem upoštevajo omejitve, ki jih planer drugače drži v glavi: nosilnost vozil, časovna okna dostave, delovni čas voznikov. V praksi se uporabljajo tri družine metod: eksaktne metode za manjše primere, hevristike za hitre rešitve in metahevristike za velike, realne flote. V nadaljevanju razložimo, kako delujejo, kaj prinese kapacitetni VRP (CVRP) in kdaj se uvedba v slovenskem proizvodnem ali distribucijskem podjetju splača.

Novacore-groupOptimizirajte logistične proceseNovaCore Group avtomatizira delovne procese z umetno inteligenco ter pomaga podjetjem optimizirati upravljanje dokumentov, proizvodnjo in načrtovanje.Raziščite rešitve NovaCore

Na kratko

  • VRP išče najcenejši nabor dostavnih poti za več vozil iz enega ali več skladišč, ob upoštevanju operativnih omejitev.
  • Kapacitetni VRP (CVRP) doda pravilo, da tovor na posamezni poti ne sme preseči nosilnosti vozila. To je osnova skoraj vsakega realnega načrtovanja dostav.
  • Eksaktne metode najdejo dokazano optimalno rešitev, a le pri manjših primerih; hevristike in metahevristike v kratkem času najdejo zelo dobre rešitve za stotine strank.
  • Kakovost rezultata je odvisna predvsem od podatkov: točne razdalje, časi, količine in časovna okna iz ERP.
  • Učinek merite s skupnimi kilometri, številom vozil, izkoriščenostjo tovornega prostora in deležem dostav v dogovorjenem oknu.

Kazalo

Kaj je problem usmerjanja vozil

VRP je klasičen problem logistike in operacijskih raziskav. Laporte, Toth in Vigo ga v preglednem članku o zgodovini usmerjanja vozil opišejo kot načrtovanje najcenejših dostavnih poti skozi geografsko razpršene stranke ob stranskih omejitvah. Avtorji poudarjajo, da je njegova vrednost prav v povezavi dveh svetov: gospodarskega pomena distribucije in zahtevnega matematičnega izziva kombinatorične optimizacije.

Zakaj je problem tako težak? Že pri eni sami poti z 20 strankami obstaja astronomsko število možnih vrstnih redov. Ko dodamo več vozil, različne nosilnosti in časovna okna, število kombinacij eksplodira. Zato VRP spada med NP-težke probleme, za katere ni znanega postopka, ki bi pri velikih primerih v razumnem času zagotovo našel optimum.

Za podjetje to pomeni nekaj zelo konkretnega: ročno planiranje, tudi izkušenega dispečerja, skoraj vedno pusti kilometre in vozila na mizi. Pregled literature iz leta 2020 v reviji Operational Research ugotavlja, da razporejanje dostav in usmerjanje vozil pomembno določata distribucijske stroške in zadovoljstvo strank, zato so algoritmi VRP vgrajeni v informacijske sisteme za realne distribucijske primere. Avtorji so pregledali 334 člankov, od tega jih je 263 obravnavalo tovorni promet.

Kaj je problem usmerjanja vozil

Kapacitetni VRP in druge različice

Osnovni VRP je izhodišče, realni primeri pa skoraj vedno zahtevajo dodatne omejitve. Najpogostejša je kapaciteta.

Kapacitetni VRP (CVRP)

Pri CVRP povpraševanje na posamezni poti ne sme preseči kapacitete vozila. Spletna zbirka VRP Web Univerze v Málagi opredeli klasični CVRP kot problem z enotno floto vozil enake kapacitete, enim blagom, znanimi zahtevami strank in skupnim skladiščem, cilj pa je minimizacija stroškov prevoza.

Primer iz prehrambne distribucije: tovornjak nosi 18 palet, dnevno pa imate 60 trgovin z različnimi naročili. Algoritem mora stranke razdeliti v skupine, katerih vsota ne preseže 18 palet, in hkrati znotraj vsake skupine najti najkrajši vrstni red obiskov. Obe odločitvi sta povezani, zato ju dober algoritem rešuje skupaj.

Kapacitetni VRP (CVRP)

V praksi flota redko ni enotna. Dokumentacija odprtokodne knjižnice VRPy pri heterogeni floti navaja, da se vozila razlikujejo po kapaciteti in stroških, algoritem pa izbere kombinacijo vozil, ki pokrije povpraševanje ob najnižjih skupnih stroških. Ista dokumentacija opozori na pogost zaplet: če skupno povpraševanje preseže skupno kapaciteto flote, je problem neizvedljiv. Model lahko zato dopusti izpuščene obiske s kazenskim stroškom, kar planerju jasno pokaže, kaj danes ne gre na pot.

Pregled najpogostejših različic

Različica Kaj doda Tipična raba
CVRP Omejitev nosilnosti vozila Distribucija palet, zabojev, rinfuze
VRP s časovnimi okni (VRPTW) Dostava v dogovorjenem intervalu Trgovine, gostinstvo, prevzemne točke
VRP s prevzemi in dostavami Prevzem mora biti pred dostavo istega tovora Povratna embalaža, kurirske storitve
Heterogena flota Vozila z različno kapaciteto in stroškom Mešane flote kombijev in tovornjakov
VRP z omejitvijo razdalje ali časa Najdaljša dovoljena dolžina poti Delovni čas voznikov, hladna veriga
Več skladišč Vozila začnejo v različnih bazah Regionalni distribucijski centri

Katere podatke potrebuje algoritem

Algoritem je toliko dober, kolikor so dobri njegovi podatki. Google OR-Tools za osnovni primer navaja tri vhodne podatke: matriko razdalj, število vozil in lokacijo skladišča. Za CVRP se dodata povpraševanje vsake lokacije in kapaciteta vsakega vozila, s pravilom, da tovor na vozilu nikoli ne preseže njegove največje nosilnosti.

Uporabniški priročnik OR-Tools med pogostimi omejitvami našteva še največje število obiskov na pot, največji čas ali razdaljo poti, časovna okna in vrstni red pri prevzemu in dostavi.

V realnem podjetju to pomeni naslednje podatke:

  1. Lokacije in naslovi strank z geokodiranimi koordinatami, ne le s poštno številko.
  2. Matrika razdalj in časov vožnje po dejanskem cestnem omrežju, po možnosti ločeno za jutranjo konico in preostanek dneva.
  3. Naročila s količino v enoti, ki omejuje vozilo: palete, kilogrami, litri ali prostornina.
  4. Flota: število vozil, nosilnost, posebnosti (hladilnik, dvižna ploščad), strošek na kilometer in na uro.
  5. Časovna okna strank in čas raztovarjanja na lokaciji.
  6. Pravila voznikov: začetek izmene, odmori, najdaljši delovni čas.

Strošek na kilometer se pri električnih dostavnih vozilih računa drugače kot pri dizelskih, saj vključuje tudi polnjenje. Če prehajate na električno floto, je smiselno najprej urediti obračun stroškov polnjenja službenih vozil, da algoritem dobi realno ceno kilometra.

Pregled logistične literature iz leta 2020 poudarja, da morajo biti algoritmi VRP prilagojeni konkretnim zahtevam prevoznikov, strank in okolja, saj te zahteve v modelu nastopijo kot spremenljivke ali omejitve. Večina teh podatkov že obstaja v vašem ERP, zato je povezava z njim prvi tehnični korak. Kako se tega lotiti, razlagamo v vodniku integracija AI z ERP.

Vrste algoritmov VRP

Metode za reševanje VRP delimo v tri družine. Razlikujejo se po kakovosti rešitve in času, ki ga potrebujejo.

Družina Primeri Kakovost rešitve Čas izračuna Kdaj jo izbrati
Eksaktne metode Branch-and-bound, branch-and-price, dinamično programiranje Dokazano optimalna Hitro narašča z velikostjo Manjši primeri, preverjanje drugih metod
Konstrukcijske hevristike Clarke-Wright (savings), metoda najbližjega soseda, metoda pometanja Dobra začetna rešitev Sekunde Hiter prvi plan, izhodišče za izboljšave
Izboljševalne hevristike 2-opt, zamenjave in premiki strank med potmi Lokalno izboljšana Sekunde do minute Dodelava obstoječega plana
Metahevristike Tabu iskanje, simulirano ohlajanje, genetski algoritmi, ALNS Blizu optimuma Minute Realne flote s stotinami strank

Eksaktne metode

Tan in Yeh v pregledu stanja raziskav VRP (obdobje 2019 do 2021) razlagata, da eksaktne metode, kot so branch-and-X in dinamično programiranje, lahko najdejo optimalno rešitev, vendar so primerne predvsem za manjše probleme. Laporte, Toth in Vigo dodajajo, da je že CVRP s samimi kapacitetnimi omejitvami težko eksaktno rešiti pri približno 100 do 200 strankah. Prav to je spodbudilo razvoj zmogljivih metahevristik.

Hevristike: Clarke-Wright in sorodne metode

Najbolj znana konstrukcijska hevristika je algoritem prihrankov Clarka in Wrighta iz leta 1964. Laporte, Toth in Vigo jo opišejo kot metodo, ki je cenjena zaradi hitrosti, preprostosti in razmeroma dobre natančnosti.

Ideja je preprosta. Na začetku vsaka stranka dobi svojo pot: skladišče, stranka, skladišče. Nato algoritem za vsak par strank izračuna, koliko prihrani, če ju obiščete v isti vožnji, in poti združuje po vrsti od največjega prihranka navzdol, dokler to dopušča kapaciteta vozila.

Računski primer: skladišče je od stranke A oddaljeno 20 km, od stranke B 25 km, A in B pa sta med seboj oddaljeni 10 km.

  • Ločeni vožnji: 2 × 20 + 2 × 25 = 90 km.
  • Skupna vožnja skladišče, A, B, skladišče: 20 + 10 + 25 = 55 km.
  • Prihranek: 20 + 25 − 10 = 35 km.

Pri 60 strankah algoritem izračuna prihranke za vse pare in v delčku sekunde zgradi smiseln plan. Ta plan je dober začetek, ne pa končni odgovor.

Metahevristike

Pregled hevristik iz leta 2023 na arXivu loči tri ravni hevrističnih pristopov: konstrukcijske, ki hitro zgradijo začetno rešitev, izboljševalne, ki jo lokalno popravljajo, in metahevristike, ki z višjenivojskim iskanjem zmanjšujejo nevarnost, da se iskanje ustavi v lokalnem optimumu. Tabu iskanje si zapomni nedavne poteze in jih začasno prepove, simulirano ohlajanje občasno sprejme slabšo rešitev, da pobegne iz slepe ulice, genetski algoritmi pa križajo dobre rešitve med seboj. Te metode stojijo za večino sodobnih orodij za načrtovanje poti.

Strojno učenje in nevronske mreže

Raziskave preizkušajo tudi nevronske mreže, ki se učijo graditi poti. Ciglarič je v magistrskem delu na Univerzi v Ljubljani (2021) kapacitetni VRP obravnaval kot NP-poln kombinatorični problem. Mreža GRU z mehanizmom pozornosti je na majhnih grafih dosegla primerljivo dobre rezultate, na večjih pa je zaradi naraščajoče kompleksnosti zaostajala. Za produkcijsko planiranje danes zato najbolje deluje kombinacija: preverjene optimizacijske metode za izračun poti in AI za napovedovanje vhodnih podatkov, na primer povpraševanja ali časov vožnje.

Kdaj se algoritem VRP splača

Algoritem VRP ni rezerviran za velike prevoznike. Smiseln postane, ko velja vsaj nekaj od naslednjega:

  • dnevno načrtujete poti za tri ali več vozil in več deset dostav,
  • planiranje traja več kot uro na dan ali je odvisno od enega samega dispečerja,
  • stranke imajo časovna okna in zamude povzročajo reklamacije,
  • vozila pogosto odpeljejo napol prazna ali pa tovor ne gre v vozilo,
  • se naročila spreminjajo čez dan in je treba plan hitro preračunati.

Računska zmogljivost danes ni ovira. Erdoğan je že leta 2017 predstavil odprtokodni reševalnik v preglednici, ki je primere CVRP in VRP z omejitvijo razdalje z do 200 strankami reševal v eni uri procesorskega časa. Specializirani sistemi, povezani z ERP, gredo dlje: plan se osveži ob vsakem novem naročilu in gre neposredno v aplikacijo voznika.

Pri mestni dostavi pa sama optimizacija vrstnega reda ni dovolj. Raziskovalci Univerze v Mariboru so za mestno dostavo razvili model dodeljevanja nakladalnih mest z mehkim in trdim gručenjem. Mehko gručenje je pri večjem številu mest izboljšalo prilagodljivost, skrajšalo vozne razdalje in ohranilo kratke pešpoti. Sporočilo za slovenske distributerje v Ljubljani ali Mariboru: optimizirajte celoten sistem, vključno z mestom raztovarjanja in zadnjimi metri do stranke.

Kako izmeriti učinek optimizacije

Brez izhodiščne meritve ne boste vedeli, ali algoritem dela dobro. OR-Tools pojasnjuje, da je cilj lahko minimizacija skupne razdalje ali najdaljše posamezne poti, dodatne dimenzije pa spremljajo akumulirane količine, kot sta razdalja in čas. Iz tega izpeljite svoje kazalnike:

Kazalnik Kako ga izračunate Zakaj je pomemben
Skupni kilometri na dan Vsota vseh poti Gorivo, obraba, emisije
Število aktivnih vozil Vozila z vsaj eno potjo Največji fiksni strošek flote
Izkoriščenost kapacitete Naložene palete ÷ kapaciteta vozila Pokaže prazne vožnje
Delež dostav v oknu Pravočasne dostave ÷ vse dostave Zadovoljstvo strank
Najdaljša pot Najdaljši čas posamezne poti Nadure in delovni čas voznikov
Čas planiranja Ure dispečerja na dan Strošek in odvisnost od posameznika

Priporočamo, da algoritem najprej teče vzporedno z ročnim planom dva do štiri tedne in primerjate oba na istih naročilih. Tako dobite pošteno primerjavo, preden spremenite delo voznikov. Načrt takega preizkusa opisujemo v članku AI pilotni projekt v podjetju.

Uvedba v podjetju korak za korakom

  1. Opredelite cilj. Manj kilometrov, manj vozil ali več pravočasnih dostav: vsak cilj vodi do nekoliko drugačnega modela.
  2. Popišite omejitve. Skupaj z dispečerji zapišite vsa nenapisana pravila, od dostavnih ramp do strank, ki sprejmejo le manjše vozilo.
  3. Uredite podatke. Preverite naslove, količine in časovna okna v ERP. Če podatki še niso urejeni, vam pomaga ocena zrelosti za umetno inteligenco.
  4. Izberite pristop. Hevristika za hiter začetni plan, metahevristika za izboljšavo; pri zapletenih omejitvah je to podobno kot planiranje z omejitvami v proizvodnji.
  5. Povežite sisteme. Plan naj gre samodejno iz ERP v aplikacijo voznika in nazaj kot potrditev dostave.
  6. Merite in prilagajajte. Kazalnike spremljajte tedensko in model dopolnite, ko se pojavijo nova pravila.

Naš pogled

Pri NovaCore Group vidimo, da se projekti optimizacije poti redko zataknejo pri samem algoritmu. Zataknejo se pri podatkih, pri povezavi z ERP in pri pravilih, ki jih pozna le izkušen dispečer.

Zato rešitve gradimo okoli procesa naročnika, ne okoli orodja. V projekte vključujemo ekipe, ki poznajo panogo, od proizvodnje in distribucije do prehrambne industrije, in rešitev prilagodimo vašim omejitvam, namesto da bi vi prilagajali delo programu.

Usmerjanje vozil je pri nas del širše slike: upravljanje naročil in transporta, aplikacije za voznike, sledenje dostavam in povezava z ERP. Ko se ti deli pogovarjajo med seboj, postane plan poti izvedljiv že ob prvem izračunu.

Po uvedbi ostanemo ob vas. Omejitve se spreminjajo, nove stranke prinesejo nova pravila, in stalna podpora zmanjšuje tveganje, da bi se sistem čez leto dni oddaljil od realnosti.

Martin

Optimizacija logistike z NovaCore Group

Naša rešitev za upravljanje proizvodnje vključuje nadzor logistike, upravljanje naročil in transporta, aplikacije za voznike, sledenje dostavam in povezavo z ERP. Za planiranje dodajamo prediktivno planiranje z napovedovanjem povpraševanja, da algoritem poti računa s številkami, ki bodo res prišle.

Novacore-group

Pri eni od naših implementacij se je čas obdelave naročil skrajšal za 68 %, naložba pa se je povrnila v 8 do 10 mesecih. Povejte nam, kako danes planirate dostave, in skupaj ocenimo, kje je največ prihranka.

→ Oglejte si naše rešitve

Pogosta vprašanja

Kakšna je razlika med VRP in problemom trgovskega potnika?

Problem trgovskega potnika (TSP) išče najkrajšo pot za eno samo vozilo skozi vse točke. VRP doda več vozil in omejitve, kot so kapaciteta in časovna okna. TSP je tako poseben primer VRP z enim vozilom brez omejitev.

Ali algoritem VRP vedno najde optimalno rešitev?

Ne vedno. Eksaktne metode optimum zagotovijo, a so praktične predvsem pri manjših primerih. Pri realnih flotah s stotinami strank metahevristike v nekaj minutah najdejo rešitve, ki so zelo blizu optimuma, in to je za vsakodnevno planiranje povsem dovolj.

Kaj storiti, če naročila presežejo kapaciteto flote?

Model lahko dopusti izpuščene obiske s kazenskim stroškom. Algoritem tako pokaže, katere dostave so najmanj ugodne za danes, planer pa se odloči, ali jih prestavi, doda vozilo ali najame zunanjega prevoznika.

Kako hitro je mogoče preračunati plan, ko pride novo naročilo?

Konstrukcijske hevristike nov plan zgradijo v sekundah, metahevristike ga izboljšajo v nekaj minutah. Zato je dnevno ali celo sprotno preračunavanje izvedljivo, če so podatki v ERP sproti posodobljeni.

Viri

Priporočeno

Algoritmi VRP: kako delujejo in kdaj jih uporabiti | NovaCore Group