Graph theory is a large mathematical discipline. Chinese postman problem falls under category of arc vehicle routing problems. Chinese postman problems are very extensive and difficult to calculate in practice. They belong to NP-hard problems. For this reason, heuristics are proposed to provide acceptably good solution in polynomial time. The focus of this thesis is to propose a randomized heuristic which does not follow deterministic rules but is ruled by random. Monte Carlo simulation is launched to find the best solution. Heuristic is formulated for undirected capacitated rural postman problem. It is programmed in VBA and validated on testing problems. At the end of the thesis is a case study about municipal garbage collection.
Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:193550 |
Date | January 2014 |
Creators | Rýdlová, Lenka |
Contributors | Pelikán, Jan, Fesenko, Anastasiya |
Publisher | Vysoká škola ekonomická v Praze |
Source Sets | Czech ETDs |
Language | Czech |
Detected Language | English |
Type | info:eu-repo/semantics/masterThesis |
Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.002 seconds