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