Víceoddílové VRP
Tato verze problému obsahuje stochastické požadavky zákazníků, které se stanou známou veličinou až po stanovení trasy. Problém je obvykle modelován jako dvoustupňový (Yang a kol., 2000; Cordeau a kol., 2007).
Základní CVRPSD představil Laporte (2002). Zde je použita formulace pomocí rekurzivní funkce. Teoreticky jsou uvažovány dva typy rozdělení poptávky – Poissonovo a normální rozdělení.
Ve víceoddílových VRP se stochastickými požadavky (Mendoza a kol., 2010 a 2011; Goodson, 2015) má každý zákazník stochastickou poptávku po různých produktech, která se řídí známým rozdělením pravděpodobnosti. Tyto produkty jsou přepravovány v samostatných oddílech ve vozidlech. Rekurzivní funkci představuje cesta do skladu, jakmile je naplněna kapacita některého z oddílů ve vozidle.
Zajímavost
- Efektivní řešení tohoto problému vede ke snížení přepravních nákladů a minimalizaci rizika kontaminace.
- Náročnost spočívá v kombinaci dvou faktorů: víceoddílového rozdělení a nejistoty poptávky.
- Moderní přístupy využívají simulační metody a robustní optimalizaci k minimalizaci rizika překročení kapacit.
Praktické využití
- Distribuce potravin (např. oddělení chlazených a mražených produktů).
- Přeprava nebezpečných chemikálií, kde je nutné striktní oddělení látek.
- Léčiva a zdravotnický materiál, kde se různé léky a vybavení nesmí míchat.
Metody řešení
Víceoddílový kapacitní VRP se stochastickými požadavky (MC-CVRPSD) kombinuje dva komplexní aspekty: vozidla s oddělenými komorami a neurčitou poptávku zákazníků. Každý zákazník může požadovat více druhů produktů současně, přičemž každá komora vozidla má omezenou kapacitu. Poptávka v jednotlivých komorách je náhodná, což zvyšuje náročnost plánování tras i rezervy v kapacitě. Tento model je prakticky využitelný v potravinářské logistice, chemickém průmyslu, distribuci pohonných hmot i odpadovém hospodářství.
Zdroj:
[1] Yang, W.-H., Mathur, K., Ballou, R. H. (2000). Stochastic vehicle routing problem with restocking. Transportation Science, 34(1).
[2] Cordeau, J.-F., Laporte, G., Savelsbergh, M. W., Vigo, D. (2007). Vehicle routing, chapter 6. In: Barnhart C, Laporte G (eds) Transportation, vol 14. Elsevier, Amsterdam
[3] Laporte, G., Louveaux, F. V., & Van Hamme, L. (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research, 50(3).
[4] Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., & Velasco, N. (2010). A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers & Operations Research, 37(11).
[5] Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., & Velasco, N. (2011). Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands. Transportation science, 45(3).
[6] Goodson, J. C. (2015). A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands. European Journal of Operational Research, 241(2).