Práce se zabývá optimalizací úloh spojených se svozem odpadu. Pro tento účel byl sestrojen matematický model spadající do kategorie Vehicle routing problems se zohledněním časových závislostí. Díky tomuto modelu je svozové vozidlo schopno přizpůsobit se aktuální dopravní situaci a adaptovat svou trasu v průběhu celého svozu. Tím se zajistí využití méně zatížených tras namísto hlavních cest, kde hrozí vyšší riziko časových zdržení. K dosažení optimálních výsledků bylo navrženo řešení ve formě svozových tras pro libovolnou denní dobu pomocí Clark & Wright Savings algoritmu a sady 25 optimalizačních operátorů, jako jsou například 2-opt, 3-opt nebo Or-opt.
Annotation in English
This thesis deals with optimizing waste collection tasks. For this purpose, a mathematical model belonging to the category of Vehicle Routing Problems was constructed, taking into account time dependencies. Thanks to this model, the waste collection vehicle is capable of adapting to the current traffic situation and adjusting its route throughout the entire collection process. This ensures the use of less congested routes instead of main roads, where would be a higher risk of time delays. To achieve optimal results, a solution in the form of waste collection routes for any given time of day was proposed, using the Clark & Wright Savings algorithm and a set of 25 optimization operators, such as 2-opt, 3-opt, and Or-opt.
Práce se zabývá optimalizací úloh spojených se svozem odpadu. Pro tento účel byl sestrojen matematický model spadající do kategorie Vehicle routing problems se zohledněním časových závislostí. Díky tomuto modelu je svozové vozidlo schopno přizpůsobit se aktuální dopravní situaci a adaptovat svou trasu v průběhu celého svozu. Tím se zajistí využití méně zatížených tras namísto hlavních cest, kde hrozí vyšší riziko časových zdržení. K dosažení optimálních výsledků bylo navrženo řešení ve formě svozových tras pro libovolnou denní dobu pomocí Clark & Wright Savings algoritmu a sady 25 optimalizačních operátorů, jako jsou například 2-opt, 3-opt nebo Or-opt.
Annotation in English
This thesis deals with optimizing waste collection tasks. For this purpose, a mathematical model belonging to the category of Vehicle Routing Problems was constructed, taking into account time dependencies. Thanks to this model, the waste collection vehicle is capable of adapting to the current traffic situation and adjusting its route throughout the entire collection process. This ensures the use of less congested routes instead of main roads, where would be a higher risk of time delays. To achieve optimal results, a solution in the form of waste collection routes for any given time of day was proposed, using the Clark & Wright Savings algorithm and a set of 25 optimization operators, such as 2-opt, 3-opt, and Or-opt.
Seznamte se s problematikou spojenou s matematickou optimalizací, a to zejména se zaměřením na odpadové hospodářství a modely svozu odpadu.
Zpracujte rešerši existujících modelů svozu odpadu s ohledem na problematiku modelování (časových) zdržení v dopravních sítích.
Popište tuto problematiku pomocí teorie grafů a sestavte jednoduchý matematický model pro plánování svozu. Tento model implementujte ve zvoleném optimalizačním softwaru (např. GAMS či Julia) a otestujte na vybraném datovém souboru.
Proveďte důkladnou diskuzi dosažených výsledků. Popište omezení a limity zvoleného přístupu a vytyčte směry pro případný další výzkum.
Research Plan
Seznamte se s problematikou spojenou s matematickou optimalizací, a to zejména se zaměřením na odpadové hospodářství a modely svozu odpadu.
Zpracujte rešerši existujících modelů svozu odpadu s ohledem na problematiku modelování (časových) zdržení v dopravních sítích.
Popište tuto problematiku pomocí teorie grafů a sestavte jednoduchý matematický model pro plánování svozu. Tento model implementujte ve zvoleném optimalizačním softwaru (např. GAMS či Julia) a otestujte na vybraném datovém souboru.
Proveďte důkladnou diskuzi dosažených výsledků. Popište omezení a limity zvoleného přístupu a vytyčte směry pro případný další výzkum.
Recommended resources
GENDREAU, M. a POTVIN, J.-Y. Handbook of Metaheuristics. Second edition. Springer (2010). ISBN: 978-1-4419-1663-1.
ROTHLAUF, F. Design of Modern Heuristics: Principles and Application. Springer (2011). ISBN: 978-3-540-72962-4.
GHIANI, G., LAPORTE, G. a MUSMANNO, R. Introduction to logistics systems planning and control. John Wiley & Sons (2004). ISBN: 0-470-84917-7.
TOTH., P. a VIGO, D. Vehicle Routing: Problems, Methods, and Applications. Second edition. SIAM (2014). ISBN: 978-1-611973-58-7.
BEN TICHA, H., ABSI, N., FEILLET, D., QUILLIOT. A. Vehicle routing problems with road-network information: State of the art. Networks, 72: 393-406 (2018). DOI: 10.1002/net.21808.
PIRES, A., MARTINHO, G., RODRIGUES, S. a GOMES, M.I. Sustainable Solid Waste Collection and Management. Springer (2019). ISBN: 978-3-319-93199-9.
Recommended resources
GENDREAU, M. a POTVIN, J.-Y. Handbook of Metaheuristics. Second edition. Springer (2010). ISBN: 978-1-4419-1663-1.
ROTHLAUF, F. Design of Modern Heuristics: Principles and Application. Springer (2011). ISBN: 978-3-540-72962-4.
GHIANI, G., LAPORTE, G. a MUSMANNO, R. Introduction to logistics systems planning and control. John Wiley & Sons (2004). ISBN: 0-470-84917-7.
TOTH., P. a VIGO, D. Vehicle Routing: Problems, Methods, and Applications. Second edition. SIAM (2014). ISBN: 978-1-611973-58-7.
BEN TICHA, H., ABSI, N., FEILLET, D., QUILLIOT. A. Vehicle routing problems with road-network information: State of the art. Networks, 72: 393-406 (2018). DOI: 10.1002/net.21808.
PIRES, A., MARTINHO, G., RODRIGUES, S. a GOMES, M.I. Sustainable Solid Waste Collection and Management. Springer (2019). ISBN: 978-3-319-93199-9.
