Algoritmus nedominovaného třídění II
Algoritmus nedominovaného třídění II (NSGA-II) je evoluční vícekriteriální optimalizační metoda, která pracuje s populací řešení a třídí je podle tzv. dominance – řešení, která nejsou překonána žádným jiným ve všech cílech, jsou považována za lepší. NSGA-II udržuje diverzitu v populaci a postupně konverguje ke Pareto optimální frontě.
- Výborný pro VRP s konfliktními cíli (např. náklady vs. emise vs. doba obsluhy).
- Pracuje s celou množinou řešení, nikoli jedním kompromisem.
- Udržuje širokou škálu různorodých řešení (diverzita).
- Automaticky vyváží kvalitu a rozmanitost.
Zajímavosti a praktická využití
- Oblíbená metoda ve výzkumu vícekriteriálních VRP.
- Uplatnění při návrhu zelené logistiky (náklady vs. uhlíková stopa).
- Vhodná i pro kombinované VRP s více sklady a servisními úrovněmi.
Omezení a limity
NSGA-II vyžaduje větší výpočetní náročnost, zejména při třídění a hodnocení rozsáhlých populací. Dále je potřeba definovat vhodné kódování řešení a operátory (křížení, mutace), jinak může dojít ke stagnaci.
Shrnutí
NSGA-II je silný nástroj pro simultánní optimalizaci více cílů, který umožňuje získat kvalitní a různorodá řešení. Patří mezi nejvíce používané vícekriteriální evoluční algoritmy v logistice a plánování tras.
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] Řezanková, H., & Húsek, D. (2007). Kvantitativní metody v manažerském rozhodování. Praha: Professional Publishing.
[3] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň