Problém obchodního cestujícího a metoda GENIUS

Autor práce: Škopek, Michal
Typ práce: Diplomová 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: Problém obchodního cestujícího a metoda GENIUS
Typ práce: Diplomová práce
Jazyk práce: Česky
Abstrakt: Cílem diplomové práce je vysvětlit Problém obchodního cestujícího a vytvořit program, který bude počítat speciální metodu GENIUS. Problém obchodního cestujícího je popsán z několika hledisek. Nejprve z hlediska historického k objasnění souvislostí s určitými metodami a následně je popsán z hlediska výpočetních metod. Pro popis těchto metod byly vybrány zástupci jak exaktních metod tak i heuristických. Stěžejní částí diplomové práce je popis heuristiky GENIUS, ke které je vytvořen speciální počítačový program. Tento program pracuje nejprve s algoritmem GENI a následně s post-optimalizačním algoritmem US. Program je popsán z uživatelského pohledu a je k němu vytvořen manuál. Program je otestován na dvou základních příkladech. Výsledky, dané výpočtem pomocí programu pracujícím s heuristikou GENIUS, jsou srovnány s výsledky získanými pomocí exaktních algoritmů.
Klíčová slova: TSP; Problém obchodního cestujícího; GENIUS; Heuristiky

Informace o studiu

Studijní program a Studijní obor: Kvantitativní metody v ekonomice/Matematické metody v ekonomii
Typ studijního programu: Magisterský studijní program
Jméno přidělované hodnosti: Ing.
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: Problém obchodního cestujícího a metoda GENIUS
Překlad názvu: Travelling salesman problem and method GENIUS
Typ práce: Master thesis
Jazyk práce: Czech
Abstrakt: The target of this thesis is to explain the Travelling Salesman Problem and also create a special program, which will be able to make calculations using the heuristics GENIUS. The Travelling Salesman Problem will be described from two different points of view. The first one is the historical description of the idea of the Travelling Salesman Problem and later will be the problem will be described with some of the very wide number of the calculation methods. For the explanation of the methods, in the thesis there has been chosen some of the algorithms which belong to that methods. The heuristics and also the exact algorithms will be explained. The focus of this thesis is on the heuristics called GENIUS and also in the creation of the program which can calculate it. The program works first with the GENI algorithm and after that it works with US post-optimization algorithm. The program will be described from the point of view of the user and the manual will be written as well. The program will be tested on two different examples and will be compared with the exact algorithm.
Klíčová slova: Travelling Salesman Problem; heuristics; TSP; GENIUS

Informace o studiu

Studijní program a Studijní obor: Kvantitativní metody v ekonomice/Matematické metody v ekonomii
Typ studijního programu: Magisterský studijní program
Jméno přidělované hodnosti: Ing.
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: 26. 5. 2009
Datum podání práce: 30. 6. 2010
Datum obhajoby: 07.09.2010

Soubory ke stažení

Hlavní práce20797_xskom15.pdf [1,01 MB]
Veřejná příloha4232_xskom15.zip [146,61 kB]
Oponentura17815_fabry.pdf [153,54 kB]
Hodnocení vedoucího20797_pelikan.pdf [31,56 kB]

Údaje ze systému InSIS

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