Járműútvonal-tervezési probléma

Egy illusztráció a jármű útvonaltervezési problémáról

A járműútvonal-tervezési probléma vagy jármű-útválasztási probléma (az angol szakirodalomban Vehicle Routing problem, VRP) egy kombinatorikai optimalizálási és egészértékű programozási probléma, amelynek központi kérdése: „Melyik az az optimális útvonalhalmaz egy járműflotta járművei számára, hogy azok a vevőkör minden rendelését teljesítsék?” Gyakran előfordul, hogy egy központi raktárban található árukat kell kiszállítani a kuncsaftoknak, és a VRP célja a teljes útvonalköltség minimalizálása. Az úgynevezett utazóügynök-probléma általánosítása.

A VRP legelőször George Dantzig és John Ramser 1959-es cikkében jelent meg, amely tárgyalta az első algoritmikus megközelítést, amelyet üzemanyag-szállításokra alkalmaztak. 1964-ben Clarke és Wright továbbfejlesztette Dantzig és Ramser megközelítését egy hatékony mohó algoritmus, az úgynevezett megtakarítási algoritmus (savings algorithm) segítségével.

Az optimális megoldás meghatározása NP-nehézségű feladat, így a matematikai programozással vagy kombinatorikus optimalizálással megoldható problémák mérete korlátozott lehet. Ezért a kereskedelmi algoritmusok általában heurisztikákat alkalmaznak a gyakorlatban előforduló esetekhez.

A VRP-nek számos alkalmazása létezik az iparban. Az útvonaltervező eszközök fejlesztői szerint az algoritmus 5%-30%-os költségmegtakarítást kínál.

Utasszállításhoz kapcsolódó problématípusok szempontrendszere

Az utasszállításhoz kapcsolódó problématípusoknál az optimalizációs feladat megközelítése során az alábbi szempontok figyelembevétele ajánlott:

• Igény kezelés:
  • Az igények egyidejűleg több igényfeladótól (pl. gyárakból) is származhatnak.
  • Az igényadatok összegyűjtésére többféle megoldás használatos lehet, néhány lehetőség a teljesség igénye nélkül:
    • ERP rendszerekből - interfészen keresztül - érkező igények alapján,
    • Műszakrendektől függő igények esetén a műszakrendekből történő generálással,
    • Manuálisan felrögzített igények alapján.
  • A munkába szállítási és a hazaszállítási probléma együtt kezelésével gazdaságosabb eredmény érhető el, mintha külön optimalizálnánk azokat.
  • Az igények összegyűjtése során korlátozott lehet azok jármű és állomásonkénti kombinálása, amelyet optimalizáció során figyelembe kell venni.
• Flotta kezelés:
  • A biztosított flotta járművei egyidejűleg több tulajdonostól is származhatnak.
  • Az egyes járműtípusok eltérők lehetnek, amely kihat az optimalizációra az alábbi ismérvek szerint:
    • Jármű kapacitás,
    • Jármű telephely,
    • Jármű futásidő limit – az optimalizációs feladat teljesítése során rendelkezésre álló időkeret,
    • Jármű időjárás faktor – időjárási viszonyoktól függő sebességkorlátozás,
    • Jármű priorizálási lehetőségek (pl. tulajdonos és jármű típus szerint),
    • Fix költségek (sofőr bére és annak járulékai, amortizáció, műszaki vizsga, szerviz, autópálya használat),
    • Változó költségek (üzemanyag költség).
  • Gyűjtőpontos szállítás esetén az egyes járműtípusok ugyancsak eltérők lehetnek:
    • Gyűjtőpontra szállító jármű,
    • Gyűjtőpontról szállító jármű,
    • Gyűjtőponttól független jármű,
  • Mivel a járművek telephelyei általában különbözőek, ez jelentősen kihat az optimalizáció eredményére, így számolni kell a flotta ideális elhelyezésével.
  • Számolni kell azzal, hogy a felvételi / leadási ponton egy adott jármű használata tiltott lehet. Naptártól és műszakrendtől függően változhatnak az említett kizárási szabályok.
  • Az úton lévő járműveket zárolni kell a következő optimalizációs feladat elől.
  • A járművek GPS követési adatait célszerű felhasználni az optimalizáció során.
• Gráf kezelés:
  • Az úthálózat kezelést célszerű valamelyik online térképkezelő rendszerrel integrálni, az induló gráf felépítése és az esetleges változások automatizált követése érdekében.
  • Az útszakaszok gyakorlati használhatósága eltérő lehet az online térképi adatbázisban használtaktól, ezért a gráf manuális korrekciójával, korlátozásaival számolni kell.
  • Az útszakaszok maximálisan járható sebessége változó, mellyel az optimalizáció során számolni kell.
  • Az útszakaszok átjárhatósága korlátozott lehet a jármű áthaladási irányától függően. Naptártól és műszakrendtől függően változhatnak az említett kizárási szabályok.

Utasszállításhoz kapcsolódó problématípusok megoldási heurisztikái

Az egészértékű programozási feladatokkal (MILP) leírt, utasszállításhoz kapcsolódó problématípusok optimalizálása a következő heurisztikák segítségével jelentősen egyszerűsíthető és gyorsítható:

• Probléma részekre bontása:
  • Küllőkre bontás – amennyiben a bejárandó gráf a természeti vagy közlekedési adottságok alapján részekre bontható, úgy az optimalizálandó problémát is célszerű az egyes részgráfokra bontva futtatni.
  • Irányokra bontás – az optimalizálandó feladat általában egyidőben tartalmaz beszállási és hazaszállítási igényeket is, amelyeket egyesített feladatként kiértékelve gazdaságosabb, azonban számításigényesebb megoldás kapunk. Külön-külön futtatva a bemenő és hazatérő igényeket, majd a kapott eredményeket egy heurisztika segítségével egyesítve, közel optimális eredményt, azonban többszörös teljesítménynövekedést érhetünk el.
• Probléma egyszerűsítése:
  • Bázis buszok számának limitálásával – a megoldandó feladat a terminál buszokon kívül központi (bázis) buszokat is tartalmazhat, azonban csak azokat a bázis buszokat érdemes bevonni a probléma kiszámításába, amelyek a megoldás tekintetében jobb eredményt hozhatnak. A bázis buszok számának korlátozása megfelelő heurisztika alkalmazásával többszörös teljesítménynövekedéshez vezethet.
  • Gráf tömörítés – alapértelmezett esetben az alkalmazott gráf egy élre eső felvevő vagy leadópontjain bárhol megfordulhatnak a buszok. Amennyiben viszont feltördeljük a gráf ezen élét egy előre definiált élhosszúsággal és a buszok fordulását az említett él mentén csak a törési pontokon engedélyezzük, közel optimális eredményt, azonban többszörös teljesítménynövekedést érhetünk el.
  • Feszítőfa képzés – egy adott probléma esetén ha járművenként a valóban felmerült felvevő vagy leadópontokat, illetve a jármű állomását a legrövidebb utakon összekötve megkapjuk a probléma által érintett útszakaszok variációinak összességét. Az ezen útszakaszokon kívül eső élek tehát biztosan nem lesznek érintve, így ezeket a probléma megoldásában felesleges figyelembe venni. Ez a heurisztika probléma típustól függően változó, adott esetben akár tízszeres gyorsulást hozhat.
  • Zónázás
    • Negatív zónázás - a járművek utasfelvétele tapasztalati értékek alapján korlátozható: nem halad távolabb a jármű a járművet az ipari parkkal összekötő legrövidebb úttól egy tapasztalati X távolságnál. Ezen elv mentén minden járműre kizárhatók bizonyos nem gyakorlatias távolságban lévő igényfelvételi vagy leadási pontok.
    • Pozitív zónázás – azon igényfelvételi vagy igényleadási pontok, amelyek a negatív zónázás következtében jármű nélkül maradnának, a feladatot megoldhatatlanná tennék. Ennek elkerülésére a hozzájuk legközelebb eső N db járműre fel kell oldani a negatív kizárás eredményét – annak pozitív korrekciójaként.
• Kiértékelő tuningolása – a kereskedelemben kapható MILP kiértékelő komponensek teljesítménye problématípustól függően több tízszerese vagy több százszorosa is lehet az ingyenes eszközökének. Ezen felül a kereskedelmi eszközök olyan funkciókkal is rendelkeznek ami növeli használhatóságukat az utasszállításhoz kapcsolódó problématípusok esetén, ezek a következők:
  • Többszálú futtatás lehetősége
  • Automatikus paraméter tuningolás lehetősége
  • Lazy kényszerek alkalmazásának lementése
  • Kiértékelő kezdőértékek használatának lehetősége:
    • Előző számítás kezdőértékek – előfordul, hogy a probléma kiértékelés az előző azonos probléma kiértékelésének egy finomítása, bizonyos paraméterek (pl. járművek) megkötésével, ilyen esetben célszerű az előző számítás eredményéből fixált változókat indulóértékként vagy megkötésekként felhasználni.
    • Struktúramegoldás kezdőértékek – az optimalizálandó probléma általánosságban egy hálózatot reprezentáló gráfon fut, azonban a gráfot struktúrává alakítva és a kiértékelést ezen elvégezve az így kapott eredmények, mint induló eredmények jelentősen gyorsíthatják a valós, hálózat alapú probléma kiértékelését.
  • Az optimumkeresés korai megszakításának lehetősége:
    • Az optimumkeresés relatív érték szerinti megszakítása
    • Az optimumkeresés abszolút érték szerinti megszakítása
    • Az optimumkeresés időlimit szerinti megszakítása
    • Az optimumkeresés növekményalapú megszakítása (elért optimum és az optimalizálásra fordított idő hányasa)

Utasszállításhoz kapcsolódó problématípusok infrastrukturális elvárásai

Az utasszállításhoz kapcsolódó problématípusokat kiszolgáló rendszer tervezése esetén az alábbi infrastrukturális elvárások figyelembevétele ajánlott:

• MI alapú öntanuló keretrendszer:
  • Automatizált úthálózati-gráf építés
  • Automatikus jármű priorizálás
  • Jármű elhelyezés tanítás támogatása
  • Egyedi műszakdefiníciók kezelése
  • Automatizált HR-igény generálás
  • Időjárási és közlekedési viszonyok tanulása
  • K+F alapú algoritmusok a számítás során
  • K+F alapú számítási heurisztikák és kombinálásuk
  • Különböző kiértékelők alkalmazási lehetősége
  • Gráf-mintázatok felismerésén alapuló gyorsítótár
  • Munkába és haza utazás összevont optimalizálása
• A rendszer rugalmassága és skálázhatósága:
  • Tetszőleges számú gyár
  • Tetszőleges számú személyszállító cég
  • Változó körülményekhez való adaptív alkalmazkodás
  • Területi sajátosságok öntanuló felmérése
• Azonnali és teljes körű adatszolgáltatás:
  • Integrált információ szolgáltatási platformok:
    • GPS készülék és alkalmazás a buszokon
    • TV kijelző a gyárakban
    • Mobil applikáció
    • Mobil weboldal
    • Pdf menetrend
  • Valós idejű járműkövetés és információszolgáltatás
  • Dinamikus menetrend frissítés és késés értesítés
  • Összesített és részletes kimutatások
  • Szervezettség, részletes útiterv

Fordítás

• Ez a szócikk részben vagy egészben a Vehicle routing problem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Irodalom

• Oliveira, H.C.B.de (2008). „A hybrid search method for the vehicle routing problem with time windows”. Annals of Operations Research 180, 125–144. o. DOI:10.1007/s10479-008-0487-y. (Hozzáférés: 2009. január 29.) 
• Frazzoli, E. (2004). „Decentralized algorithms for vehicle routing in a stochastic time-varying environment”. 43rd IEEE Conference on Decision and Control, 14-17 Dec. 2004, Nassau, Bahamas 2004 43rd IEEE Conference on Decision and Control (CDC) 4, IEEE. doi:10.1109/CDC.2004.1429220. 
• Psaraftis, H.N. (1988). „Dynamic vehicle routing problems”. Vehicle Routing: Methods and Studies 16, 223–248. o. 
• Bertsimas, D.J. (1991). „A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane”. Operations Research 39 (4), 601–615. o. DOI:10.1287/opre.39.4.601. JSTOR 171167. 
• (2013) „Heuristics for multi-attribute vehicle routing problems: A survey and synthesis”. European Journal of Operational Research 231 (1), 1–21. o. DOI:10.1016/j.ejor.2013.02.053. 
• Arnold Horváth (2021). „Hercules Routes: Presentation of business requirements, business processes and statistics”, 43. o. DOI:10.5281/zenodo.5804606. 
• Arnold Horváth (2022). „Hercules Routes: Presentation of calculation algorithms, calculation heuristics and statistics for 2022”, 25. o. DOI:10.5281/zenodo.7490333.