2-opt
2-opt je jednoduchá, ale velmi účinná lokální heuristika určená ke zkrácení trasy. V každém kroku se odstraní dvě hrany v aktuálním řešení a nahradí se tak, aby vznikla nová trasa s menší délkou. Opakuje se, dokud nelze provést další zlepšení. Používá se pro TSP i VRP.
- Efektivní zlepšovač existující trasy.
- Nízká výpočetní náročnost.
- Vhodný pro implementaci do jakéhokoliv algoritmu s iterací.
- Zkracuje trasy a eliminuje křížení.
Zajímavosti a praktická využití
- Často využíván jako post-processing po Sweep nebo Clarke-Wright metodě.
- Vhodný pro GPS plánovače tras.
- Funguje velmi dobře u symetrických vzdálenostních matic.
Omezení a limity
2-opt zlepšuje řešení pouze pomocí výměn dvou hran, což omezuje možnosti změny struktury. U složitějších tras nemusí najít globální optimum, protože se „zasekne“ v lokálním minimu.
Shrnutí
2-opt je základní lokální heuristika, která i přes svou jednoduchost dokáže výrazně zkrátit trasy. Je ideálním nástrojem pro ladění již existujících řešení VRP i TSP.
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] 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ň