Clarke-Wrightova metoda
Clarke-Wrightova metoda, známá také jako Savings heuristic, je jedna z nejstarších a nejpoužívanějších konstrukčních heuristik pro VRP. Využívá princip úspor (savings), kdy se výhodnost spojení dvou zákazníků do jedné trasy měří pomocí úspory oproti samostatné obsluze z depa. Zákazníci se postupně slučují podle velikosti dosažené úspory.
- Rychlá a snadno implementovatelná metoda pro VRP bez časových oken.
- Výsledky jsou často velmi blízké optimálnímu řešení.
- Lze ji upravit i pro omezení kapacity a více vozidel.
- Dobře škáluje při větším počtu zákazníků.
Zajímavosti a praktická využití
- Používá se jako výchozí řešení pro metaheuristiky (např. Tabu Search).
- Využívána v plánování tras zásobovacích vozidel, svozu odpadu či rozvozu zboží.
- Základní verze lze rozšířit i na více dep (MDVRP) nebo otevřený VRP.
Omezení a limity
Metoda pracuje pouze s lokálními úsporami a nezohledňuje globální strukturu tras, což může vést ke vzniku suboptimálních řešení v případech s komplikovaným geografickým uspořádáním nebo při přísnějších omezeních (např. časová okna). Rovněž citlivě reaguje na pořadí zákazníků a jejich rozmístění.
Shrnutí
Clarke-Wrightova metoda je klasická a stále velmi relevantní heuristika, která díky své jednoduchosti a dobrému výkonu nachází uplatnění i v moderní distribuční praxi. Je ideálním vstupem do světa heuristických metod.
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] Doležal, J., & Fiala, P. (2012). Operační výzkum: Příklady a úlohy. Praha: Oeconomica.
[3] Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of Operations Research, 61, 227–262.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň