Manage and streamline operations across multiple locations, sales channels, and employees to has improve efficiency and your bottom line.

VRP s pevnými časovými okny a stochastickými servisními časy

Varianta, která propojuje pevná časová okna s nejistotou v servisních časech – a zároveň umožňuje přeskočení zákazníků za penalizaci, což dělá tento model flexibilní, ale nákladově velmi citlivý., označovaného jako VRPTW-ST.

VRP s pevnými časovými okny a 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ů.

Tento problém kombinuje:

  • Pevná časová okna – zákazník musí být obsloužen ve stanoveném čase, jinak je vynechán,
  • Stochastické servisní časy – doba obsluhy zákazníka je náhodná, což komplikuje dodržení harmonogramu,
  • Možnost přeskočit zákazníka za penalizaci, pokud by jeho obsluha ohrozila další dodávky,
  • Rekurzivní náklady – kromě běžných cestovních nákladů zahrnují také odchylky a rizika spojená s nejistotou.

Zajímavosti

  • Kombinace nejistoty a tvrdých časových omezení = výzva
    Pevná časová okna znamenají, že zákazník musí být obsloužen ve stanoveném čase. Stochastické servisní časy ale znamenají, že není jisté, jak dlouho předchozí obsluha potrvá. Tento rozpor vytváří velmi napjatý plánovací prostor.
  • Odmítnutí zákazníka jako součást strategie
    Zajímavé je, že v některých modelech (např. Errico et al., 2016) je přeskočení zákazníka povoleno – a penalizováno. To umožňuje rizikově adaptivní plánování: místo snahy „všechno stihnout“ se některé trasy záměrně zkrátí, aby snížily riziko rozsáhlého zpoždění.
  • Rekurzivní náklady a jejich výpočet
    Náklady v tomto problému nejsou jen „cestovní“. Zahrnují i pravděpodobnostní náklady na zpoždění, přeskočení zákazníků, a dopady na další zákazníky. Tato rekurzivní povaha nákladů dělá tento problém výpočetně velmi zajímavý.
  • Aplikace v reálném světě – doručovací služby, údržba, zdravotní péče
    V praxi se VRPTW-ST používá třeba:
    • ve zdravotnictví (např. návštěvy pacientů v domácím prostředí),
    • u expresních kurýrních služeb (kde má zákazník přísně dané doručovací okno),
    • nebo v technické údržbě (s pevnými okny a proměnnou délkou zásahu).
  • Silná role simulačních přístupů a scénářového testování
    Tradiční deterministické algoritmy mají potíže tento problém zvládnout. Často se proto používají simulace průběhu tras v různých scénářích, nebo se vytvářejí pravděpodobnostní modely rizika překročení časového okna.
  • Předběžná robustnost vs. dynamická reaktivita
    Výzkumně zajímavý je i rozpor:

Praktické využití

  • Služby s pevně danými návštěvními okny (např. zdravotnická péče v domácnostech, technická údržba),
  • Expresní doručovací služby, kde některé zásilky mohou být výhodněji přeskočeny (např. prémiová vs. standardní),
  • Logistika s omezenou možností zpoždění a s potřebou plánovat alternativy předem.

Metody řešení

Tato varianta výborně ilustruje konflikt mezi přísnými časovými požadavky a náhodností služby – a přitom poskytuje možnost ekonomicky racionálního řešení v případě problémů. Vhodná i pro scénářové nebo rekurzivní modely.

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