Proměnlivé vyhledávání v sousedství
Variable Neighbourhood Search - VNS je rámec, který pracuje s několika různými typy lokálních heuristik a sousedství.
Na rozdíl od klasických metod se neomezí na jedno okolí, ale systematicky ho mění, což zvyšuje šanci na únik z lokálního optima.
Postupuje střídáním zlepšování a rušivých operací.
- Vhodné pro velké a strukturované úlohy jako VRP, kombinované VRP.
- Silná schopnost překonávat lokální minima.
- Flexibilní a rozšiřitelný rámec – snadná kombinace s 2-opt, Or-opt, apod.
- Dobře funguje i v hybridních algoritmech.
Zajímavosti a praktická využití
- Úspěšně používán v oblasti návrhu dopravních systémů a doručovacích linek.
- Populární volba při řešení vícekriteriálních VRP.
- Často implementován jako základní framework pro vlastní algoritmy studentů a vývojářů.
Omezení a limity
Hlavní výzvou u VNS je návrh vhodných sousedství a přechodových pravidel. Bez pečlivého návrhu se může algoritmus „motat“ mezi
podobnými řešeními nebo být zbytečně výpočetně náročný.
Shrnutí
VNS je výkonný a strukturovaný přístup k lokální optimalizaci, který dokáže systematicky prohledávat složité prostory řešení.
Díky své adaptabilitě je velmi cenným nástrojem při řešení praktických distribučních problémů.
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] Hansen, P., & Mladenović, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130(3), 449–467.
[3] Doležal, J., & Fiala, P. (2012). Operační výzkum: Příklady a úlohy. Praha: Oeconomica.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň