Stochastický problém
Taxonomické označení: SVRP
V případě tohoto VRP jsou některá klíčová data náhodná.
Stochasticita může být začleněna do problému prostřednictvím různých aspektů. Typicky se jeden nebo dva prvky považují za stochastické.
Problémy stochastického směrování vozidel jsou obvykle řešeny ve dvoufázovém procesu. První fáze zahrnuje výpočet řešení za použití náhodných proměnných. Na základě výsledků s náhodnými veličinami se ve druhé fázi provádějí zpřesňující výpočty. Druhá fáze zahrnuje definici tzv. rekurzivní funkce, která určuje další postup při plánování okružního problému.
Jedná se například o:
- dobu na trase k zákazníkovi nebo čas obsluhy zákazníka, které jsou náhodnými proměnnými,
- přítomnost či nepřítomnost zákazníka v úloze je určena jistou mírou pravděpodobnosti
- poptávku jednotlivého zákazníka, která má náhodnou velikost
Zajímavosti
Na rozdíl od klasického VRP, kde jsou všechny informace známé předem, ve stochastickém modelu se některé parametry (např. poptávka zákazníků, časy doručení, dostupnost vozidel) mění náhodně. Firmy proto používají pravděpodobnostní modely a simulace, aby mohly lépe předvídat nejistoty v reálném provozu.
- Dvouetapové rozhodování (here‐and‐now vs. recourse)
- Modelování nejistoty pomocí scénářů
- Sample Average Approximation (SAA) a heuristiky. Přímé řešení stochastických modelů bývá výpočetně náročné. SAA přístupy náhodně generují vzorky scénářů a optimalizují průměrné náklady napříč těmito vzorky.
- Kompromis mezi očekávanými náklady a rizikem
Praktické využití
- Rozvoz potravin a léků, kde poptávka kolísá a je třeba předvídat potřeby zákazníků.
- Zásobování čerpacích stanic palivem, kde poptávka závisí na aktuálním provozu.
- Logistika e-shopů, kde se objednávky generují průběžně během dne.
Metody řešení
Shrnutí
Stochastický VRP pomáhá optimalizovat trasy v situacích, kdy nejsou všechny údaje známy předem. Tento model je zásadní pro pružné a efektivní plánování v prostředí s nejistotou. SVRP přidává do klasického VRP prvek nejistoty – například nevíme dopředu, kolik objednávek skutečně přijde, jak dlouho bude každá dodávka trvat, nebo zda budou všechna vozidla k dispozici. Nejprve v tzv. „here-and-now“ fázi vytvoříme základní plán tras na základě odhadů a pravděpodobnostních scénářů. Když se ukáže, jaká varianta skutečně nastala, v „recourse“ fázi trasu upravíme tak, aby byly co nejmenší sankce za zpoždění nebo přeplnění vozidel. Při modelování nejistoty často používáme sadu možných scénářů s příslušnými pravděpodobnostmi a optimalizujeme průměrné náklady nebo některou míru rizika (například CVaR).
Zdroj:
[1] Yang, W.-H., Mathur, K., Ballou, R. H. (2000). Stochastic vehicle routing problem with restocking. Transportation Science, 34(1).
[2] Cordeau, J.-F., Laporte, G., Savelsbergh, M. W., Vigo, D. (2007). Vehicle routing, chapter 6. In: Barnhart C, Laporte G (eds) Transportation, vol 14. Elsevier, Amsterdam
[3] Tan, K., Cheong, C., Goh, C. (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. European Journal of Operation Research.
[4] Oyola, J., Arntzen, H., & Woodruff, D. L. (2017). The stochastic vehicle routing problem, a literature review, part II: solution methods. EURO Journal on Transportation and Logistics, 6(4).
[5] Oyola, J., Arntzen, H., & Woodruff, D. L. (2018). The stochastic vehicle routing problem, a literature review, part I: models. EURO Journal on Transportation and Logistics, 7(3).
[6] Bertsimas, D. J. (1992). A vehicle routing problem with stochastic demand. Operations Research, 40(3).
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň