Original title:
Kapacitní problém listonoše
Translated title:
Capacitated Arc Routing Problem
Authors:
Franc, Zdeněk ; Pelikán, Jan (advisor) ; Fesenko, Anastasiya (referee) Document type: Master’s theses
Year:
2014
Language:
cze Publisher:
Vysoká škola ekonomická v Praze Abstract:
[cze][eng] Úloha čínského listonoše s kapacitním omezením má v reálném životě řadu uplatnění. Cílem úlohy je minimalizovat celkové náklady při splnění požadavků hran. Úloha čínského listonoše s kapacitním omezením je rozšířením úlohy čínského listonoše, která je speciálním typem okružních úloh. V této závěrečné práci je nejprve vysvětlena problematika úlohy čínského listonoše i její rozšíření. Následně je ilustrována aplikace matematických modelů na modelovém příkladu. V praxi se ale tyto matematické modely hledající optimální řešení příliš nepoužívají, proto je v této práci navržen a naprogramován randomizovaný heuristický algoritmus pro řešení těchto úloh. Následně byla tato heuristika aplikována na reálný příklad z praxe týkající se svozu komunálního odpadu v Poděbradech.The Capacitated Arc Routing Problem has many applications in real life. The aim of this problem is to minimize the total cost at fulfilment of the requirements of arcs. The Capacitated Arc Routing Problem is an extension of the Chinese Postman Problem, which is a special type of the Vehicle Routing Problems. In this thesis is explained the issue of the Chinese Postman Problem and its extensions at first. Subsequently the applications of mathematical models are illustrated on a model example. However these mathematical models, which are searching the optimal solution, do not use so much in reality. Therefore the randomized heuristic algorithm for solving these problems is suggested and programmed in this thesis. Subsequently this heuristic was applied to case study of garbage collection in Podebrady city.
Keywords:
Capacitated Arc Routing Problem; CARP; randomized heuristic; VBA; CARP; kapacitní problém čínského listonoše; randomizovaná heuristika; VBA
Institution: University of Economics, Prague
(web)
Document availability information: Available in the digital repository of the University of Economics, Prague. Original record: http://www.vse.cz/vskp/eid/45980