Rozhodování za nejistoty

Problém stochastického směrování vozidel s měkkými časovými okny za nejistoty přepravy a servisní doby (Adulyasak & Jaillet, 2016) nabízí minimalizovat součet fixních nákladů na brzké příjezdy, nákladů na pozdní příjezdy a náklady na nadměrnou dobu trasy. Nejvyšší prioritu má minimalizace počtu vozidel s minimální pravděpodobností včasného příjezdu. Každý zákazník může mít jiné omezení úrovně zákaznických služeb.

Kombinace stochastických cestovních/servisních časů, měkkých časových oken a rozhodování za nejistoty (decision-making under uncertainty) představuje komplexní variantu dopravního problému, kde plánovač musí navrhnout trasy s ohledem na náhodné průběhy a přitom rozhodovat tak, aby minimalizoval očekávané náklady nebo rizika.

V tomto typu problému neznáme přesně vstupní parametry v době rozhodování (např. přesné časy nebo dopravní situaci), ale můžeme s nimi počítat jako s náhodnými veličinami. Výsledkem je rozhodnutí, které je robustní nebo adaptivní, podle toho, zda se mění podle realizace nejistot.

Zajímavost

• Scénářové plánování: Běžná technika je práce se souborem scénářů – každý scénář představuje jednu možnou realizaci náhodných veličin.
• Dvoufázové rozhodování: Nejprve vytvoříme první fázi – rozhodnutí před realizací nejistot (např. předběžné trasy). Po zjištění skutečných hodnot pak přichází druhá fáze – reakce systému (např. změna trasy, penalizace).
• Stochastické programování vs. robustní optimalizace:
  • Stochastické programování pracuje s pravděpodobností – minimalizujeme např. očekávané náklady.
  • Robustní optimalizace vytváří řešení, která jsou „nejméně špatná“ i v nejhorším případě.
• Šancová omezení (chance constraints): Říkají např. „obsluž zákazníka ve stanoveném časovém okně s pravděpodobností alespoň 90 %“.

Praktické využití

• Expresní doručování (např. kurýři, jídlo, léky): Rozhodnutí musí brát v úvahu jak měnící se podmínky (např. dopravní kolaps), tak důsledky zpoždění (sankce, ztráta zákazníka).
• Mobilní zdravotní služby: Plánování tras se dělá ráno, ale podmínky (délky návštěv, provoz) jsou náhodné – adaptivní strategie zohlední možnost přeplánování nebo penalizace.
• Zásobování supermarketů: Měkká časová okna umožní pružnější přístup, ale rozhodnutí o pořadí dodávek musí být činěna ještě předtím, než známe skutečné podmínky.

Metody řešení

• ALNS
• Fuzzy heuristiky
• Simulace Monte Carlo
• Fuzzy simulace
• Programování s pravděpodobnostními omezeními
• NSGA-II (při vícekriteriálním hodnocení nejistoty a kvality obsluhy)

Problém stochastických cestovních/servisních časů s měkkými časovými okny a rozhodováním za nejistoty kombinuje realističnost (stochastika), pružnost (měkká časová okna) a optimalizační složitost (rozhodování s neznámými). Tento model zachycuje nejistotu v průběhu dne, umožňuje penalizaci zpoždění a podporuje strategie, které minimalizují očekávané náklady nebo snižují riziko porušení časových omezení. Hodí se pro situace, kde se musí učinit rozhodnutí dopředu, ale s vědomím, že budoucí podmínky nejsou zcela známy. Využití najde zejména v logistice s vysokými nároky na spolehlivost, ale s omezenou kontrolou nad vnějšími faktory.

Tento problém nabízí tři různé modifikace:

Přidáním rozhodování za nejistoty do problému se stochastickými cestovními/servisními časy a měkkými časovými okny se dostáváme na pokročilejší úroveň rozhodovacích modelů, kde nestačí jen naplánovat trasu, ale zároveň volíme nejlepší strategii s ohledem na možný budoucí vývoj situace.

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] Adulyasak, Y., & Jaillet, P. (2016). Models and algorithms for stochastic and robust vehicle routing with deadlines. Transportation Science, 50(2).