Stochastická poptávka s Poissonovo rozdělením

Pokud přítomnost zákazníků sleduje Poissonovo rozdělení, znamená to, že zákazníci se vyskytují v nepravidelných intervalech s určitou průměrnou četností. Tento model je vhodný pro případy, kdy požadavky na obsluhu jsou vzácné, ale mohou se nahromadit v určitých obdobích (Christiansen a kol., 2009).

Směrování kapacitního okruhu se stochastickou poptávkou, označené jako CARPSD-P (Capacitated Arc Routing Problem with Stochastic Demand on Poisson Distribution), je specifická varianta klasického problému směrování vozidel (VRP), která se zaměřuje na optimalizaci tras pro vozidla, jež musí navštívit specifické hrany v síti, přičemž poptávka je náhodná a podléhá Poissonovu rozdělení. Tento problém se vyskytuje v situacích, kde je potřeba distribuovat zboží nebo služby na určité infrastruktury (například energetické sítě, čištění komunikací, distribuce poštovních zásilek apod.), přičemž poptávka na těchto hranách je variabilní a musí být modelována pomocí stochastických procesů.

Tato varianta se hodí více než normální rozdělení v případech, kdy pracujeme s celými čísly a velmi malou nebo nulovou pravděpodobností velkých hodnot.

Zajímavost

• Stochastická poptávka: Poissonovo rozdělení je ideální pro modelování náhodných událostí, jako jsou poruchy nebo neplánované požadavky v reálném světě. Tento přístup pomáhá lépe odhadnout a připravit plánování tras pro případ nečekaných změn poptávky.
• Komplexita problému: CARPSD-P je náročný nejen kvůli stochastické povaze poptávky, ale i z hlediska potřeby zahrnout kapacitní omezení vozidel a specifika vztahující se k síťovým okruhům. Kombinace těchto faktorů činí tento problém velmi obtížným pro tradiční metody optimalizace.
• Praktické aplikace: Tento typ problému se používá v rozmanitých odvětvích, jako je údržba infrastruktury (např. pravidelná údržba elektrických vedení, úklid komunikací nebo rozvoz paliv), kde poptávka není zcela předvídatelná.

Praktické využití

Typicky se Poissonovo rozdělení hodí pro:

• svoz odpadu, který vzniká v malých množstvích, ale náhodně,
• naložení nákladu v průmyslových areálech,
• události typu: počet zásilek, počet zásahů, požadavků za období atd.

Například v distribuci poštovních zásilek by mohl tento model pomoci optimalizovat trasy, kde je poptávka na určitém místě (požadavky na doručení) náhodná a podle Poissonova rozdělení, přičemž je potřeba respektovat kapacity vozidel, které nemohou překročit určitou nosnost.

Metody řešení

• Simulace Monte Carlo (pro Poissonova data)
• Heuristiky využívající Poissonovský model – Clarke-Wrightova metoda, Sweep algorithm, Insertion heuristics
• Dynamické programování (upravené pro stochastické vstupy) (pro přesnější řízení v malých případech)
• Lokální heuristiky (2-opt, or-opt)

Směrování kapacitního okruhu se stochastickou poptávkou (CARPSD-P) je komplexní logistický problém, který kombinuje náhodné požadavky (modelované Poissonovým rozdělením) s kapacitními omezeními vozidel a potřebou optimalizovat trasy. Tento problém se běžně vyskytuje v různých průmyslových sektorech, kde poptávka není konstantní a je nutné zohlednit kapacity při plánování tras. Praktické aplikace tohoto modelu zahrnují údržbu a distribuci zboží na složitých sítích, jako jsou energetické nebo poštovní systémy, a poskytují nástroje pro efektivní rozdělení zdrojů v reálném čase.

Zdroj:
[1] Gendreau, M., Laporte, G., Séguin, R. (1996) Stochastic vehicle routing. European Journal of Operation Research, 88(1).
[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] 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).