Směrování s klastry

Tato varianta VRP kombinuje stochastickou poptávku a dvoufázový přístup k plánování:

Krok 1 – Shlukování (clustering): zákazníci jsou rozděleni do územních obvodů, tzv. klastrů, obvykle na základě geografické blízkosti nebo zátěže.
Krok 2 – Směrování (routing): v každém klastru se plánuje samostatná trasa.

Poptávka zákazníků není známá přesně, ale až v průběhu obsluhy. Proto je důležité brát v úvahu riziko překročení kapacity vozidla a případné nutnosti návratu do depa k doplnění.

Model je vhodný při návrhu obvodů pro pravidelné rozvážkové trasy, například v městské logistice, zásobování obchodů nebo svozu odpadu, kde je výhodné strukturovat zákazníky do stálých oblastí.

Problémem se stochastickou poptávkou se rozumí kombinace směrování a klastrů (routing plus clustering) používaných kupříkladu při návrhu doručovacích obvodů (Haugland a kol., 2007). Problém obsahuje  sousedících obvodů, kde jsou všichni zákazníci ve stejném obvodu přiřazeni ke stejné trase. Před realizací požadavků se provádí proces shlukování. Pokud je poptávka zákazníka větší než zbývající kapacita, musí vozidlo nejprve dojet do depa, aby doplnilo kapacitu, než obslouží zákazníka. Tento problém směrování vozidla se stochastickými požadavky a omezením trvání lze nalézt v literatuře pod označením VRPSD DC (Erera a kol., 2010). Pro zpracování přehledu o přesných zásobách jsou zvažovány dvě alternativy – cesta zpět do skladu a doplnění kapacity nebo identifikace zásob těsně po příjezdu k dalšímu zákazníkovi.

Zajímavost

• Kombinace směrování a klastrů umožňuje rozdělit geografické oblasti na podskupiny, což zefektivňuje plánování tras a zajišťuje, že doručovací obvody jsou vyvážené a pokrývají specifické požadavky na poptávku.
• Tento přístup zvyšuje efektivitu distribuce, protože kladně ovlivňuje průměrnou vzdálenost mezi jednotlivými místy doručení a optimalizuje využívání kapacity vozidel.

Praktické využití

• Městská logistika – pro návrh doručovacích okruhů ve městech, kde je nutné efektivně rozdělit oblast na regiony a minimalizovat přeplněné trasy.
• Rozvoz potravin a maloobchodní doručení – aplikace ve firmách, které rozdělují městské oblasti do zón a potřebují optimalizovat dodávky pro jednotlivé zóny (např. v Amazon Flex).

Metody řešení

• ALNS
• Sweep algorithm (v kombinaci s fuzzy/pravděpodobnostním hodnocením)
• Shlukovací metoda s následným trasováním (Cluster-first, Route-second)
• Stochastické programování se simulací
• Monte Carlo simulace
• Hybridní metaheuristiky
• Re-optimalizační přístupy

Tento problém optimalizuje kombinaci směrování tras a clusteringu k efektivnímu rozdělení geografických oblastí na doručovací okruhy, čímž přispívá k efektivnější a nákladově optimalizované logistice. Je velmi vhodný pro aplikace, kde je důležité pokrýt velké geografické oblasti s flexibilní poptávkou.

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] Haugland, D., Ho, S. C., & Laporte, G. (2007). Designing delivery districts for the vehicle routing problem with stochastic demands. European Journal of Operational Research, 180(3).