Problémy se stochastickou přítomností zákazníků
Problémy se stochastickou přítomností zákazníků, označované jako CVRPSCD (Capacitated Vehicle Routing Problem with Stochastic Customer Demand), jsou variantou klasického problému směrování vozidel (VRP), kde není pouze náhodná poptávka po produktech nebo službách, ale také náhodná přítomnost zákazníků. Tento problém se vyskytuje v situacích, kdy zákazníci mohou být přítomní nebo nepřítomní na základě stochastických faktorů, což činí plánování tras pro vozidla složitější. Kromě toho musí být zohledněny kapacitní omezení vozidel, které mají za úkol pokrýt poptávku ve stanoveném čase.
Zajímavosti
- Stochastická přítomnost zákazníků: Na rozdíl od tradičních problémů VRP, kde je vždy předem známo, že zákazníci budou k dispozici, v tomto případě zákazníci nemusí být přítomní vždy. Může se jednat o náhodný proces, kde zákazník buď nebude k dispozici (například nebude doma nebo není možné s ním v daném čase komunikovat), nebo se jeho požadavky na službu nebo doručení změní v reálném čase.
- Flexibilita ve strategii trasování: Tento typ problému přináší výzvu v plánování, protože trasování vozidel musí být dynamické a schopné reagovat na změny ve dostupnosti zákazníků. Místo předem naplánovaného rozvozu zboží na pevně stanovené trasy je nutné trasování přizpůsobit aktuálnímu stavu přítomnosti zákazníků.
- Komplexnost stochastických faktorů: Tento problém je komplexní kvůli kombinaci několika stochastických faktorů: jak přítomnost zákazníků, tak i poptávka mohou být náhodné. V některých případech je poptávka zákazníků modelována jako stochastická veličina (např. normálním nebo Poissonovým rozdělením), což dále zvyšuje složitost.
Praktické využití
Problémy CVRPSCD se používají v různých oblastech, kde je potřeba zohlednit náhodnou dostupnost zákazníků a poptávku, například:
- Doručování zboží: V případě doručování balíků nebo potravin, kde někteří zákazníci mohou být nepřítomní nebo nebudou schopni přijmout zásilku v určený čas, je tento problém velmi relevantní. Například v rozvozu potravin na objednávku se může stát, že zákazník nebude doma v určený čas nebo změní svou objednávku, což znamená, že trasování vozidel musí být flexibilní.
- Servisní služby: Pro údržbu nebo opravy zařízení u zákazníků je tento problém důležitý, když se očekává, že zákazník nebude vždy přítomen, nebo že dojde k náhodným změnám v poptávce. Příkladem může být pravidelná údržba ve zdravotnických zařízeních, kde je třeba plánovat návštěvy na základě přítomnosti pacientů a jejich aktuálních potřeb.
- Pohotovostní služby: V oblasti pohotovostních služeb, jako je záchranná služba nebo opravy v krizových situacích, musí vozidla reagovat na náhodnou přítomnost „zákazníků“ (např. poruchy, které je nutné opravit), což přináší výzvu v optimalizaci tras a kapacit vozidel.
Jednotlivé varianty směrování kapacitního okruhu se stochastickou poptávkou můžeme najít zde:
Metody řešení
- ALNS
- Simulace s horizontem plánování
- Simulace Monte Carlo
- Simulace a přeplánování v reálném čase
- Multi-agentní heuristiky
Problémy se stochastickou přítomností zákazníků (CVRPSCD) představují výzvu v oblasti optimalizace tras vozidel, kdy není předem jisté, zda budou zákazníci k dispozici pro poskytování služeb nebo doručení produktů. Tento problém je obzvláště relevantní v sektorech jako je rozvoz zboží, servisní služby nebo pohotovostní služby, kde je nutné reagovat na dynamické a náhodné faktory, jako jsou přítomnost zákazníků a jejich poptávka. K řešení tohoto problému se využívají sofistikované metody pro dynamické trasování a optimalizaci kapacit vozidel, aby byly minimalizovány náklady a zajistil se efektivní servis i v podmínkách nejistoty.
Zdroj:
[1] Gendreau, M., Laporte, G., Séguin, R. (1996) Stochastic vehicle routing. European Journal of Operation Research, 88(1).
[2] Hvattum, L. M., Løkketangen, A., & Laporte, G. (2006). Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Science, 40(4).
[3] Zhong, R. X., Sumalee, A., Pan, T. L., & Lam, W. H. K. (2013). Stochastic cell transmission model for traffic network with demand and supply uncertainties. Transportmetrica A: Transport Science, 9(7), 567-602.
[4] Sörensen, K., & Sevaux, M. (2009). A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling. Journal of Mathematical Modelling and Algorithms, 8(4), 387-407.