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 stochastickou poptávkou

Cílem je najít řešení, u kterého jsou minimální odchylky v počtů výjezdů způsobené realizací náhodných událostí. Taxonomické označení: CARPSD.

Směrování kapacitního okruhu se stochastickou poptávkou

CARPSD (Capacitated Arc Routing Problem with Stochastic Demand) je varianta VRP, ve které:

  • požadavky se nacházejí na hranách (úsecích), nikoliv v uzlech jako u klasického VRP,
  • poptávka na těchto hranách je stochastická – známá až po začátku obsluhy.

Poprvé byl tento typ problému označen jako SCARP (Solutions for the Capacitated Arc Routing Problem) v pracích Fleury et al. (2002, 2004, 2005).
Poptávky na hranách sledují například zkrácené normální rozdělení a jsou kladné, ale nepřekračují kapacitu vozidla.

Model patří mezi tzv. stochastické problémy s rekurzí (SPR) – tzn. že při překročení kapacity musí být trasa přerušena a vozidlo se vrací do depa, což mění následné pořadí a strukturu služby.

Cílem je:

  • minimalizovat očekávané náklady na obsluhu hran,
  • minimalizovat počet výpadků a přerušení tras, které jsou způsobeny náhodnými výkyvy v poptávce.

Modelování se nejčastěji provádí generováním scénářů, na jejichž základě se hodnotí robustnost řešení.

Zajímavosti

  • Na rozdíl od klasického VRP, který pracuje se zákazníky v uzlech, CARPSD plánuje obsluhu přímo na úsecích (hranách). Tento typ modelu tak lépe simuluje reálné situace, kdy se vozidlo pohybuje podél cest a provádí službu na trase.
  • Jde o stochastický problém s rekurzí (SPR) – tedy s nutností návratu do depa v případě vyčerpání kapacity. Tím se zvyšuje realističnost modelu, ale i jeho výpočetní složitost.
  • Řešení CARPSD bývá hodnoceno na základě generovaných scénářů, což umožňuje pracovat s celým rozsahem nejistoty, ne jen s očekávanými hodnotami.
  • Problém může zahrnovat i zkrácená rozdělení poptávky, kdy je například známo, že poptávka nebude nikdy záporná ani vyšší než maximální nosnost vozidla.

Praktické využití

  • Sběr odpadu (komunálního, průmyslového i nebezpečného) – obsluhují se celé ulice, nikoli jednotlivé adresy. Poptávka (množství odpadu) je často neznámá, ale lze ji odhadnout.
  • Údržba komunikací – např. zimní údržba (posyp, pluhování), kde množství použitého materiálu závisí na aktuálních podmínkách.
  • Poštovní a kurýrní služby v příměstských oblastech – kde služba není vázána na přesný bod, ale na úsek.
  • Opravy a inspekce infrastruktury (kanály, veřejné osvětlení), kde se servis provádí podél trasy.

Jednotlivé varianty směrování kapacitního okruhu se stochastickou poptávkou můžeme najít zde:

Varianty CARPSD

Metody řešení

Problém CARPSD modeluje kapacitní směrování vozidel, které musí obsluhovat úseky (hrany) s nejistou poptávkou.
Hlavním cílem je minimalizovat očekávané náklady na trasování a přerušení obsluhy, které vznikají při překročení kapacity. Vozidla operují z jednoho depa a musí pokrýt všechny požadované úseky. Model se využívá především v distribučních službách prováděných přímo na cestách a počítá s návratem do depa při poruše trasy. Díky svému charakteru je CARPSD realistický a robustní nástroj pro městskou a technickou logistiku.

Zdroj:
[1] Fleury, G., Prins, C., Lacomme, P., & Chérif, W. R. (2002). Robustness evaluation of solutions for the capacitated arc routing problem.
[2] Fleury, G., Lacomme, P., & Prins, C. (2004). Evolutionary algorithms for stochastic arc routing problems. In Workshops on Applications of Evolutionary Computation (pp. 501-512). Springer, Berlin, Heidelberg.
[3] Fleury, G., Lacomme, P., Prins, C., & Ramdane-Chérif, W. (2005). Improving robustness of solutions to arc routing problems. Journal of the operational research society, 56(5).
[4] Laporte, G., Musmanno, R., & Vocaturo, F. (2010). An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands. Transportation Science, 44(1).
[5] Christiansen, C. H., Lysgaard, J., & Wøhlk, S. (2009). A branch-and-price algorithm for the capacitated arc routing problem with stochastic demands. Operations Research Letters, 37(6).
[5] Beraldi, P., Bruni, M. E., Laganà, D., & Musmanno, R. (2015). The mixed capacitated general routing problem under uncertainty. European Journal of Operational Research, 240(2), 382-392.
[6] Keenan, P., Panadero, J., Juan, A. A., Martí, R., & McGarraghy, S. (2021). A strategic oscillation simheuristic for the Time Capacitated Arc Routing Problem with stochastic demands. Computers & Operations Research, 133.