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.
Anotace v angličtině
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.
Klíčová slova
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.
Anotace v angličtině
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.
Klíčová slova
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.
Zásady pro vypracování
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.
Seznam doporučené literatury
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.
Seznam doporučené literatury
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.
Přílohy volně vložené
-
Přílohy vázané v práci
-
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Student v krátké prezentaci seznámil komisi s výsledky své bakalářské práce. Po přečtení posudků vedoucího a oponenta následovala diskuze, ve které byly položeny následující dotazy:
dr. Dulík: Kde berete časy průjezdnosti, které používáte pro optimalizaci?
dr. Dulík: Není k dispozici na získávání těchto údajů nějaké API na Google mapách?
dr. Dulík: Musel by být GANS součástí aplikace, kterou by měl např. řidič u sebe?
Student na položené dotazy odpověděl a reagoval pohotově.