Sweep algorithm
Česky rovněž znám jako Algoritmus zametání je založen na geometrickém principu. Zákazníci se seřadí podle úhlu vzhledem k depu a poté se seskupují do tras metodou "zametání kružnice". Slouží k rychlému vytvoření tras podle prostorové blízkosti.
- Jednoduchá implementace při známých souřadnicích zákazníků.
- Dobře funguje při rovnoměrném rozmístění zákazníků.
- Vhodný pro kapacitně omezené VRP bez časových oken.
- Rychlé řešení pro základní plánování.
Zajímavosti a praktická využití
- Oblíbený v městské logistice a obsluze okrajových částí měst.
- Často používán jako první krok pro další lokální zlepšení (např. 2-opt).
- Vhodný pro vizualizaci efektu prostorového seskupování.
Omezení a limity
Výsledky jsou citlivé na rozmístění zákazníků a jejich vzdálenost od depa. Při nerovnoměrné distribuci zákazníků nebo komplikovaném terénu může dojít ke vzniku zbytečně dlouhých tras nebo nevhodných seskupení.
Shrnutí
Sweep algoritmus je výborný pomocník pro první návrh rozvozních tras, pokud jsou zákazníci rozmístěni v rovině. Je rychlý, názorný a často poskytuje překvapivě kvalitní výchozí řešení.
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ň