VRP se stochastickými servisními časy
Servisní časy/doby se vyznačují menší variabilitou než doba jízdy. Stochasticita je tedy součástí doby poskytování služby (Lei a kol., 2012). Opět platí, pokud je překročena doba jízdy, dojde k navýšení cestovních nákladů o poplatek. Součet cestovních nákladů, očekávaných služeb a nákladů z prodlení je minimalizován. V této variantě je doba obsluhy zákazníka náhodná veličina. To ovlivňuje délku trasy a riziko zpoždění v celé síti.
VRP s pevnými časovými okny a stochastickými servisními časy, označován jako VRPTW-ST, je problém minimalizace celkových očekávaných nákladů – cestovních nákladů včetně rekurzivních opatření (Errico a kol., 2016; 2018). Zákazníci, kteří nemohou být obslouženi ve svém časovém okně, jsou přeskočeni za poplatek. Rekurzivní náklady jsou kombinací poplatků a odchylek cestovních nákladů.
Zajímavost
- Typické pro služby, kde čas obsluhy závisí na chování zákazníka (např. délka konzultace, čas vykládky).
- Vyžaduje modelování časových rezerv nebo adaptivních strategií.
- Možná integrace penalizací za překročení kapacitních nebo časových limitů.
Praktické využití
- Terénní technici s různě náročnými zásahy.
- Rozvoz zásilek vyžadujících podpis, asistenci, apod.
- Servisní nebo údržbové služby s neodhadnutelnou délkou práce.
Metody řešení
VRP se stochastickými servisními časy přináší větší realističnost při plánování tras tam, kde není znám přesný čas obsluhy.
Vyžaduje flexibilní a robustní strategie.
Zdroj:
[1] Bertsimas, D. J., & Van Ryzin, G. (1991). A stochastic and dynamic vehicle routing problem in the Euclidean plane. Operations Research, 39(4).
[2] 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).
[3] 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).
[4] Lei, H., Laporte, G., & Guo, B. (2012). A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times. Top, 20(1).
[5] Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & Rousseau, L. M. (2016). A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. European Journal of Operational Research, 249(1).
[6] Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & Rousseau, L. M. (2018). The vehicle routing problem with hard time windows and stochastic service times. EURO Journal on Transportation and Logistics, 7(3).