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

Problém směrování kapacitního okruhu se stochastickými servisními časy

Označení: SCARP-SS

Problém směrování kapacitního okruhu se stochastickými servisními časy

Tato modifikace kombinuje omezenou kapacitu vozidel a stochastickou dobu obsluhy. Je nutné optimalizovat trasu i přidělení zákazníků tak, aby se předešlo překročení časových nebo kapacitních limitů.

Formulace problému význačného v oblasti každodenní údržby silnic. Jedná se o variantu směrování okruhu, kde je doba jízdy i servisu stochastickými veličinami (Chen a kol., 2014). Disponibilní vozový park je používán pro určité (monitorované) segmenty silniční sítě. Každý servis je spojen se stochastickou dobou jízdy a odhadovanou dobou služby. Minimalizace celkových nákladů se týká fixních nákladů na používání vozidel a celkových nákladů na provoz.

SCARP-SS (Stochastic Capacitated Arc Routing Problem with Stochastic Service Times) je rozšířením klasického kapacitního problému směrování na hranách (CARP) o stochastické prvky, konkrétně o nejistotu v délce servisního času.

Model je definován na orientovaném nebo neorientovaném grafu, kde určité hrany (úseky) vyžadují servis – například údržbu, sběr, čištění nebo kontrolu. Každý úsek má známou poptávku (např. množství odpadu nebo délku práce) a stochastickou dobu potřebnou k obsluze, jejíž rozdělení je známo nebo odhadnuto (např. normální, lognormální apod.).

Zajímavost

  • Dochází k interakci mezi časovým rozvrhem a kapacitní zátěží vozidla.
  • Řešení může zahrnovat dodatečné vozidlo nebo pojistné doby obsluhy.
  • Často se používají heuristiky s penalizací za překročení limitů.

Praktické využití

  • Zásobování maloobchodních provozoven (různá doba vykládky zboží).
  • Sběr odpadu, kde se čas obsluhy odvíjí od množství odpadu.
  • Distribuce lahvovaného plynu nebo vody.

Metody řešení

SCARP-SS řeší trasování v podmínkách neurčité obsluhy a omezené kapacity. Zaměřuje se na zajištění proveditelných a efektivních plánů přepravy.
Z důvodu nejistoty v čase servisní obsluhy je nutné plánovat s rezervami nebo využívat robustní scénářové přístupy, případně simulačně-optimalizační metody, které dokážou odhadnout výkonnost navržených tras pod různými podmínkami.

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] Chen, Q., Li, K., & Liu, Z. (2014). Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads. Transportation Research Part E: Logistics and Transportation Review, 69.