3-opt
3-opt je rozšířením 2-opt: v každé iteraci se odstraní tři hrany a vzniklé segmenty se přeskupí v jednom z několika možných způsobů. To umožňuje větší změny struktury trasy a překonání lokálních minim, do kterých by 2-opt uvízl.
- Umožňuje výraznější zlepšení než 2-opt.
- Vhodné pro řešení TSP a VRP s větším počtem zákazníků.
- Lze kombinovat s jinými heuristikami (např. Insertion).
- Využití při detailním ladění rozvozních tras.
Zajímavosti a praktická využití
- Známý díky Lin-Kernighanovu přístupu pro TSP.
- Výborný pro jemné doladění tras v systémech vysoké kvality služeb.
- Využití v optimalizaci svozu odpadů, doručování nebo přeprav VIP klientely.
Omezení a limity
Výpočetně náročnější než 2-opt, zejména u delších tras, protože počet kombinací tří hran rychle roste. Není vhodný jako samostatný algoritmus pro velké VRP, ale spíše jako doplněk ke konstrukčním metodám.
Shrnutí
3-opt poskytuje vyšší kvalitu řešení než 2-opt, ale za cenu vyšší výpočetní složitosti. Je ideální pro ladění tras tam, kde je prostor pro další zlepšení a záleží na každém kilometru.
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] Lin, S., & Kernighan, B. W. (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, 21(2), 498–516.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň