Heuristic and metaheuristic methods for travelling salesman problem
| Thesis title: | Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího |
|---|---|
| Author: | Burdová, Jana |
| Thesis type: | Diplomová práce |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Zouhar, Jan |
| Thesis language: | Česky |
| Abstract: | 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ší. |
| Keywords: | genetický algoritmus; úloha obchodního cestujícího; heuristické metody |
| Thesis title: | Heuristic and metaheuristic methods for travelling salesman problem |
|---|---|
| Author: | Burdová, Jana |
| Thesis type: | Diploma thesis |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Zouhar, Jan |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | travelling salesman problem; genetic algorithm; heuristic methods |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 23. 6. 2010 |
|---|---|
| Date of submission: | 5. 1. 2011 |
| Date of defense: | 3. 2. 2011 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/26964/podrobnosti |