Shlukovací metoda s následným trasováním
Tato dvoufázová heuristika v angličtině známa jako Cluster-First, Route-Second Heuristics řeší VRP tak, že nejprve rozdělí zákazníky do skupin (shluků) podle zvoleného kritéria – například geografické blízkosti, kapacity nebo časových oken. V druhé fázi pak pro každý shluk řeší trasu samostatně, obvykle pomocí TSP heuristiky nebo jiného VRP algoritmu. Princip vychází z myšlenky, že lokální řešení menších skupin je jednodušší a rychlejší než řešení celého problému najednou.
- Vhodné pro problémy s velkým počtem zákazníků.
- Umožňuje snadno rozdělit úlohu mezi více vozidel.
- Flexibilní – lze kombinovat s jinými metodami (např. Sweep nebo Insertion).
- Snižuje výpočetní náročnost tím, že řeší menší podproblémy.
Zajímavosti a praktická využití
- Používá se v městské distribuci, kde jsou zóny obsluhovány samostatně.
- Umožňuje přirozeně rozdělit zákazníky mezi týmy řidičů nebo vozidel.
- Běžně využívána v plánovacích softwarových nástrojích jako první krok.
Omezení a limity
Hlavním omezením je, že první fáze (shlukování) významně ovlivňuje celkové řešení. Pokud dojde k nevhodnému rozdělení zákazníků, mohou vzniknout nerovnoměrně zatížené nebo neefektivní trasy. Metoda také často ignoruje globální optimalitu a optimalizuje pouze lokálně v rámci jednotlivých skupin.
Shrnutí
Metoda "shluk nejprve, trasa poté" nabízí praktický způsob, jak zjednodušit řešení rozsáhlých VRP. Díky své modularitě a kombinovatelnosti se často uplatňuje v systémech plánování rozvozu, kde je důležitá rychlost a přehlednost řešení.
Zdroje:
[1] Toth, P., & Vigo, D. (Eds.). (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). Philadelphia: Society for Industrial and Applied Mathematics (SIAM).
[2] Winston, W. L. (2004). Operations Research: Applications and Algorithms (4th ed.). Belmont, CA: Thomson/Brooks/Cole.
[3] Řezanková, H., & Húsek, D. (2007). Kvantitativní metody v manažerském rozhodování. Praha: Professional Publishing.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň