Tabu vyhledávání
Tabu vyhledávání, anglicky Tabu Search je pokročilá metaheuristika založená na lokálním prohledávání, která umožňuje algoritmu „vystoupit“ z lokálních optim tak,
že dočasně zakáže (tabu) návrat ke dříve navštíveným řešením.
Využívá paměťový mechanismus pro řízení vyhledávání a vyhýbání se cyklům.
- Vhodná pro VRP, TSP, rozvrhování i výrobní plánování.
- Pomáhá vyhnout se lokálním minimům.
- Vysoká flexibilita a možnost přizpůsobení doméně.
- Funguje velmi dobře i bez znalosti celé struktury problému.
Zajímavosti a praktická využití
- Úspěšně použita v městské logistice, svozu odpadu, doručování zásilek.
- Využívána v reálném čase při re-plánování tras.
- Základní rámec mnoha hybridních řešení (např. Tabu + 2-opt).
Omezení a limity
Metoda může být citlivá na volbu parametrů (délka tabu seznamu, kritéria aspirace) a bez dobrého nastavení se může pohybovat náhodně nebo se zpomalit.
Problémem může být i paměťová náročnost při velkých instancích.
Shrnutí
Tabu Search je robustní a výkonný nástroj pro řešení složitých VRP, zvláště když je potřeba se vyhnout pastem lokální optimality.
Díky paměťovým mechanismům je velmi vhodný pro kombinaci s dalšími heuristikami.
Zdroje:
[1] Doležal, J., & Fiala, P. (2012). Operační výzkum: Příklady a úlohy. Praha: Oeconomica.
[2] Gendreau, M., & Potvin, J.-Y. (2010). Handbook of Metaheuristics (2nd ed.). New York: Springer.
[3] Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. SIAM.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň