Metoda TTT pro porovnání randomizovaných heuristik

Autor práce: Novotná, Petra
Typ práce: Bakalářská práce
Vedoucí práce: Pelikán, Jan
Osoba oponující práci: Fábry, Jan

Informace o vysokoškolské kvalifikační práci

Název práce: Metoda TTT pro porovnání randomizovaných heuristik
Typ práce: Bakalářská práce
Jazyk práce: Česky
Abstrakt: Pro praktické využití úlohy listonoše je navrhováno velké množství heuristik, které sice dosahují jen přibližného řešení, ovšem v reálném čase. Vzhledem k počtu možností řešení problému listonoše je pro řešitele důležitá výkonnost heuristiky, a proto je cílem práce porovnání výkonnosti algoritmů. První část práce je věnována teorii potřebné k pochopení způsobu porovnávání, kterým dále srovnávám výkonnost pěti modifikací randomizované heuristiky řešící rozvozní úlohy pomocí problému listonoše s kapacitami. Varianty řešení jsou spuštěny na několika různě složitých úlohách s nepovinnými hranami a s více vozidly vyjíždějícími z jednoho depa. Výsledky jsou zobrazeny v grafech a pro přesnější vyhodnocení je vypočtena pravděpodobnost vypovídající o schopnosti jedné modifikace dosáhnout zadané cílové hodnoty v kratším čase než druhá modifikace. Předpokladem je různá efektivnost při řešení úlohy malého a velkého rozsahu.
Klíčová slova: kapacitní úloha listonoše; randomizovaná heuristika; metoda time-to-target

Informace o studiu

Studijní program a Studijní obor: Kvantitativní metody v ekonomice/Matematické metody v ekonomii
Typ studijního programu: Bakalářský studijní program
Jméno přidělované hodnosti: Bc.
Instituce přidělující hodnost: Vysoká škola ekonomická v Praze
Název fakulty: Fakulta informatiky a statistiky
Název katedry: Katedra ekonometrie
Instituce archivující a zpřístupňující VŠKP: Vysoká škola ekonomická v Praze

Informace o vysokoškolské kvalifikační práci

Název práce: Metoda TTT pro porovnání randomizovaných heuristik
Překlad názvu: TTT method for the comparison of randomized heuristics
Typ práce: Bachelor thesis
Jazyk práce: Czech
Abstrakt: There are many heuristics proposed for practical uses of the postman problem, which reach only approximate solutions, however in real time. Regarding the number of solutions of the postman problem, the efficiency of the heuristic is important to the solver, and that is the reason why the goal of this thesis is to compare the efficiency of different algorithms. In the first part of the thesis, the theory for understanding the comparison is described, which is further used for comparing the efficiency of five modifications of randomized heuristics solving delivery problems using the postman problem with capacities. Variants of solutions are launched on several differently complicated problems with optional edges and with multiple vehicles departing from a single depot. The results are shown in plots. A probability of the ability of one modification to reach the given target value in shorter time than the second modification is computed for more precise evaluation. The assumption is different efficiency when solving a problem of small and large scale.
Klíčová slova: time-to-target method; capacitated postman problem; randomized heuristic

Informace o studiu

Studijní program a Studijní obor: Kvantitativní metody v ekonomice/Matematické metody v ekonomii
Typ studijního programu: Bakalářský studijní program
Jméno přidělované hodnosti: Bc.
Instituce přidělující hodnost: University of Economics, Prague
Název fakulty: Faculty of Informatics and Statistics
Název katedry: Department of Econometrics
Instituce archivující a zpřístupňující VŠKP: University of Economics, Prague

Informace o odevzdání a obhajobě

Datum zadání práce: 31. 3. 2015
Datum podání práce: 15. 5. 2015
Datum obhajoby: 04.02.2016

Soubory ke stažení

Hlavní práce52503_xnovp105.pdf [1,27 MB]
Veřejná příloha12667_xnovp105.xls [107,50 kB]
Oponentura45511_fabry.pdf [265,09 kB]
Hodnocení vedoucího52503_pelikan.pdf [179,89 kB]

Údaje ze systému InSIS

Identifikátor https://insis.vse.cz/zp/52503/podrobnosti