Tato bakalářská práce se zabývá modelováním svozových úloh s dopravními omezeními. Nejprve jsou popsány pojmy jako optimalizace v odpadovém hospodářství, matematická optimalizace, teorie výpočetní složitosti a vehicle routing problem. Sestrojený matematický model se řadí do kategorie úloh značených v anglické terminologii názvem time-dependent vehicle routing problem, patřící do třídy složitosti NP - Úplné. Výstupem práce je implementace matematického modelu v jazyce GAMS, který řeší optimalizaci pomocí smíšeného celočíselného programování. Závěrem jsou demonstrovány výsledky výpočtů v podobě přiložených grafů a map a jsou nastíněny možné cesty pro pozdější implementaci reálnými daty.
Annotation in English
This thesis deals with modelling waste collection problems with traffic constraints. First, concepts of optimization in waste management, mathematical programming, computational complexity theory, and vehicle routing problem are described. The developed mathematical model belongs to the category of time-dependent vehicle routing problems, a family of NP - complete problems. Next, mixed integer programming implementation in GAMS language is done. In conclusion, the results are demonstrated in attached graphs and maps and possibilities of real data usage are outlined.
Keywords
odpadové hospodářství, svoz odpadu, matematická optimalizace, smíšené celočíselné programování, MIP, teorie výpočetní složitosti, NP - Úplné, time-dependent vehicle routing problem, VRP, GAMS, dopravní omezení
Tato bakalářská práce se zabývá modelováním svozových úloh s dopravními omezeními. Nejprve jsou popsány pojmy jako optimalizace v odpadovém hospodářství, matematická optimalizace, teorie výpočetní složitosti a vehicle routing problem. Sestrojený matematický model se řadí do kategorie úloh značených v anglické terminologii názvem time-dependent vehicle routing problem, patřící do třídy složitosti NP - Úplné. Výstupem práce je implementace matematického modelu v jazyce GAMS, který řeší optimalizaci pomocí smíšeného celočíselného programování. Závěrem jsou demonstrovány výsledky výpočtů v podobě přiložených grafů a map a jsou nastíněny možné cesty pro pozdější implementaci reálnými daty.
Annotation in English
This thesis deals with modelling waste collection problems with traffic constraints. First, concepts of optimization in waste management, mathematical programming, computational complexity theory, and vehicle routing problem are described. The developed mathematical model belongs to the category of time-dependent vehicle routing problems, a family of NP - complete problems. Next, mixed integer programming implementation in GAMS language is done. In conclusion, the results are demonstrated in attached graphs and maps and possibilities of real data usage are outlined.
Keywords
odpadové hospodářství, svoz odpadu, matematická optimalizace, smíšené celočíselné programování, MIP, teorie výpočetní složitosti, NP - Úplné, time-dependent vehicle routing problem, VRP, GAMS, dopravní omezení
1. Seznamte se s pojmy z oblasti matematické optimalizace, zejména se zaměřením na odpadové hospodářství a modely svozu odpadu.
2. 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.
3. Sestavte jednoduchý matematický model pro plánování svozu, naimplementujte jej ve zvoleném optimalizačním softwaru a výpočetně otestujte na zvolené úloze.
4. 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
1. Seznamte se s pojmy z oblasti matematické optimalizace, zejména se zaměřením na odpadové hospodářství a modely svozu odpadu.
2. 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.
3. Sestavte jednoduchý matematický model pro plánování svozu, naimplementujte jej ve zvoleném optimalizačním softwaru a výpočetně otestujte na zvolené úloze.
4. 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
GHIANI, Gianpaolo, Gilbert LAPORTE a Roberto MUSMANNO. Introduction to logistics systems planning and control. Hoboken, NJ, USA: J. Wiley, c2004. ISBN 0-470-84917-7.
TOTH., Paolo a Daniele VIGO. Vehicle Routing, Problems, Methods, and Applications. Second edition. SIAM, 2014. ISBN: 978-1-611973-58-7.
BEN TICHA, Hamza, Nabil ABSI, Dominique FEILLET a Alain QUILLIOT. Vehicle routing problems with road-network information: State of the art. Networks. 2018, č. 72, s. 393-406. ISSN 0028-3045.
PIRES, Ana, Graça MARTINHO, Susana RODRIGUES a Maria Isabel GOMES. Sustainable Solid Waste Collection and Management. Springer, 2019. ISBN: 978-3-319-93199-9.s.
SCHRIJVER, Alexander. Theory of linear and integer programming. Chichester: Wiley, c1986. ISBN 978-0-471-98232-6.
Recommended resources
GHIANI, Gianpaolo, Gilbert LAPORTE a Roberto MUSMANNO. Introduction to logistics systems planning and control. Hoboken, NJ, USA: J. Wiley, c2004. ISBN 0-470-84917-7.
TOTH., Paolo a Daniele VIGO. Vehicle Routing, Problems, Methods, and Applications. Second edition. SIAM, 2014. ISBN: 978-1-611973-58-7.
BEN TICHA, Hamza, Nabil ABSI, Dominique FEILLET a Alain QUILLIOT. Vehicle routing problems with road-network information: State of the art. Networks. 2018, č. 72, s. 393-406. ISSN 0028-3045.
PIRES, Ana, Graça MARTINHO, Susana RODRIGUES a Maria Isabel GOMES. Sustainable Solid Waste Collection and Management. Springer, 2019. ISBN: 978-3-319-93199-9.s.
SCHRIJVER, Alexander. Theory of linear and integer programming. Chichester: Wiley, c1986. ISBN 978-0-471-98232-6.
