Požadavky dle Poissonova rozdělení

Problém směrování kapacitního okruhu se stochastickou poptávkou (CARPSD) řeší otázku, jak efektivně naplánovat trasy vozidel tak, aby doručily zboží zákazníkům, jejichž poptávka není předem přesně známa. Místo pevně daných množství zboží se pracuje s pravděpodobnostním modelem poptávky, což znamená, že se může lišit od očekávání.

Hlavním cílem je minimalizovat celkové náklady spojené s dopravou, jako jsou palivo, mzdové náklady nebo čas strávený na cestách, a zároveň zajistit, že poptávka zákazníků bude uspokojena co nejefektivněji. Tento problém se od klasických VRP liší tím, že musí zohlednit nejistotu a případné překročení kapacity vozidel.

V tomto případě se předpokládá, že požadavky na hrany mají Poissonovo rozdělení pravděpodobnosti.
To znamená, že pokud je hrana rozdělena do několika segmentů, poptávka po každém segmentu bude mít také Poissonovo rozdělení. Problém byl studován v příspěvku autorů Christiansen a kolektiv (2009).

V některých případech je poptávka na jednotlivých trasách (hranách grafu) modelována pomocí Poissonova rozdělení. Toto rozdělení se často používá pro modelování náhodných událostí, které nastávají s určitou průměrnou četností za určité období.

• Predikce frekvence požadavků: Poissonovo rozdělení umožňuje odhadnout pravděpodobnost, že na dané trase bude vyžadován určitý počet doručení.
• Optimalizace kapacity: Poissonův model pomáhá optimalizovat využití vozidel tak, aby bylo minimalizováno riziko přeplnění nebo zbytečných jízd naprázdno.
• Dynamické přizpůsobení tras: Díky tomuto přístupu lze flexibilně reagovat na změny v poptávce a přizpůsobit trasu podle aktuální situace.

Zajímavost

• Náhodnost požadavků: Poissonovo rozdělení často odpovídá situacím, kde je počet objednávek v daném období nepředvídatelný, například při rozvozu jídel.
• Použití ve veřejné dopravě: Tento model je využíván také při optimalizaci veřejné dopravy, například při predikci počtu cestujících na různých trasách.
• Efektivní plánování: Díky znalosti průměrné intenzity poptávky lze plánovat efektivnější využití vozidel.

Praktické využití

• Rozvoz jídel a zásilek: Modeluje frekvenci objednávek a umožňuje efektivní plánování tras.
• Přeprava cestujících: Ve veřejné dopravě pomáhá předvídat zatížení jednotlivých linek.
• Svoz odpadu: Pomáhá optimalizovat trasy svozových vozidel na základě pravděpodobnosti naplnění kontejnerů.

CARPSD s Poissonovým rozdělením je užitečným přístupem v případech, kdy požadavky na přepravu vznikají náhodně, ale s předvídatelnou průměrnou četností. Tento model umožňuje plánovat dopravu efektivněji a flexibilně reagovat na změny v poptávce. Oproti normálnímu rozdělení se Poissonovo rozdělení hodí pro situace, kde jsou požadavky vzácné, ale mohou se hromadit v určitých obdobích, například při doručování balíků nebo optimalizaci svozu odpadu.

Zdroj:
[1] 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).
[2] 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).
[3] 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).