Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího
| Název práce: | Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího |
|---|---|
| Autor(ka) práce: | Burdová, Jana |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Zouhar, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | Tato diplomová práce se zabývá otázkou nalezení minimální trasy pro úlohu obchodního cestujícího. Obchodní cestující musí projít každé místo právě jednou a vrátit se zpět do výchozího místa. Tento problém může být znázorněn jako úloha teorie grafů, kde místa odpovídají uzlům, cesty hranám a vzdálenosti mezi uzly ohodnocení hran. Optimální cesta úlohy obchodního cestujícího odpovídá nejkratšímu Hamiltonovu cyklu v grafu. Jedná se o klasickou NP-úplnou úlohu. Není znám žádný algoritmus, který řeší tuto úlohu v polynomiálním čase. Tento problém je možné řešit pomocí různých aproximačních algoritmů, které jsou rychlejší, ale méně kvalitní, než optimalizace. Mezi aproximační algoritmy, kterým se tato práce věnuje, patří například: metoda nejbližšího souseda, metoda minimální kostry grafu, Christofidova metoda, 2 opt., genetický algoritmus a další. |
| Klíčová slova: | genetický algoritmus; úloha obchodního cestujícího; heuristické metody |
| Název práce: | Heuristic and metaheuristic methods for travelling salesman problem |
|---|---|
| Autor(ka) práce: | Burdová, Jana |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Zouhar, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | Minimal length of a travelling salesman's problem had been studied in this diploma these. Travelling salesman must come trough each place just once and then go back to the starting place. This problem can be illustrated as a problem of graph theory, such that places are the vertices, roads are the edges, distances of roads are the lengths of edges. The optimal travelling salesman's problem tour is the shortest Hamiltionian cycle in the graph. It is a classical NP-complete problem. There is no algorithm that solves this problem in polynomial time. This problem can be solved by using various approximation algorithms, they offer less time consumption and lowest quality than optimization. This diploma these had been dedicated to approximation algorithms, for example: nearest neighbor method, minimal spanning tree method, Christofide's method, 2-opt., genetic algorithm, etc. |
| Klíčová slova: | travelling salesman problem; genetic algorithm; heuristic methods |
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: | 23. 6. 2010 |
|---|---|
| Datum podání práce: | 5. 1. 2011 |
| Datum obhajoby: | 3. 2. 2011 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/26964/podrobnosti |