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

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkeszté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[szerkesztés]

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.) ^{[halott link]}
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.
(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.

Közlekedésportál • összefoglaló, színes tartalomajánló lap