Náhodné servisní časy

V tomto problému jsou servisní časy náhodné – tedy není předem známo, jak dlouho bude každá zastávka trvat. Společně s náhodnými časy dopravy vzniká komplexní situace, kdy celý harmonogram nese riziko akumulace zpoždění.

Zajímavost

• Může jít o pacienty s různou potřebností péče, zákazníky s odlišnou rychlostí převzetí zboží, nebo servisní techniky, jejichž zásah trvá nepředvídatelně.
• Významná je závislost mezi body – dlouhá zastávka může způsobit zpoždění i u všech následujících zákazníků.
• Lze využít simulaci, stochastické modelování, nebo metody jako Monte Carlo.

Praktické využití

• Domácí zdravotní péče: pacienti vyžadují různý čas, který nelze vždy předem přesně určit.
• Technická podpora (např. opravy): doba zásahu závisí na složitosti závady.
• Montáž nebo kontrola zařízení: různě dlouhá pracovní zastavení.

Metody řešení

• Stochastické programování se simulací
• Programování s pravděpodobnostními omezeními
• ALNS
• Simulace s horizontem plánování
• Fuzzy heuristiky (pro měkká okna)

Tato varianta přináší větší realismus, protože zahrnuje náhodnost v interakcích se zákazníky. Zvyšuje ale složitost optimalizace, protože nelze snadno předpovídat, kdy bude trasa dokončena. Vyžaduje robustní nebo adaptivní přístup k plánování tras.

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).