Randomizovaná heuristika pro úlohu listonoše s kapacitami
| Název práce: | Randomizovaná heuristika pro úlohu listonoše s kapacitami |
|---|---|
| Autor(ka) práce: | Rýdlová, Lenka |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Pelikán, Jan |
| Oponenti práce: | Fesenko, Anastasiya |
| Jazyk práce: | Česky |
| Abstrakt: | Teorie grafů je obsáhlá matematická disciplína. Spadá pod ní úloha čínského listonoše patřící do třídy rozvozních úloh. Úlohy čínského listonoše jsou v praxi velmi rozsáhlé a náročné na výpočet. Patří do kategorie NP-obtížných úloh. Z tohoto důvodu jsou navrhované heuristiky, které v polynomiálním čase poskytují přijatelně dobrá řešení. Cílem této práce je navrhnout randomizovanou heuristiku, která se neřídí deterministickými pravidly, ale náhodou. Provádí se Monte Carlo simulace, z které se vybírá nejlepší řešení. Heuristika je formulována pro neorientovanou kapacitní úlohu listonoše s nepovinnými hranami. Je naprogramována ve VBA a ozkoušena na testovacích úlohách. Na konci práce je zpracována případová studie na svoz komunálního odpadu. |
| Klíčová slova: | Monte Carlo; heuristika; úloha čínského listonoše |
| Název práce: | A Randomized Heuristic for the Capacitated Postman Problem |
|---|---|
| Autor(ka) práce: | Rýdlová, Lenka |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Pelikán, Jan |
| Oponenti práce: | Fesenko, Anastasiya |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | heuristic; Monte Carlo ; Chinese postman problem |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 25. 3. 2014 |
|---|---|
| Datum podání práce: | 25. 6. 2015 |
| Datum obhajoby: | 3. 6. 2015 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/47310/podrobnosti |