Vkládací heuristiky
Vkládací heuristiky patří mezi tzv. konstruktivní přístupy, které budují trasu postupným přidáváním zákazníků do zatím neúplného řešení. Rozhodujícím faktorem je výběr zákazníka a pozice, kam bude vložen – podle minimálního navýšení nákladů, vzdálenosti nebo jiného kritéria.
- Dobře funguje pro úlohy s různým počtem zákazníků a kapacitními omezeními.
- Umožňuje snadnou implementaci vlastních pravidel výběru.
- Může být adaptována pro časová okna i více vozidel.
- Poskytuje rychlé a stabilní výsledky i pro větší instance.
Zajímavosti a praktická využití
- Používá se jako základ v kombinaci s lokálním vylepšováním (např. 2-opt).
- Často využívána v plánovačích zásobovacích linek a expresních rozvozů.
- Zvláště oblíbená při modelování VRP s časovými okny (VRPTW).
Omezení a limity
Kvalita výsledku velmi závisí na výběrovém pravidlu – pokud je použito nevhodné kritérium (např. pouze minimální vzdálenost), může být řešení výrazně horší než optimální. Metoda navíc neprovádí žádnou globální optimalizaci ani zpětné úpravy.
Shrnutí
Vkládací heuristiky nabízejí flexibilní a přehledný způsob tvorby tras. Jsou ideální pro situace, kde je třeba rychle vytvořit plán rozvozu a je možné ho dále vylepšovat.
Zdroje:
[1] Řezanková, H., & Húsek, D. (2007). Kvantitativní metody v manažerském rozhodování. Praha: Professional Publishing.
[2] Winston, W. L. (2004). Operations Research: Applications and Algorithms (4th ed.). Belmont, CA: Thomson/Brooks/Cole.
[3] Toth, P., & Vigo, D. (Eds.). (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). Philadelphia: Society for Industrial and Applied Mathematics (SIAM).
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň