Original title: Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího
Translated title: Heuristic and metaheuristic methods for travelling salesman problem
Authors: Burdová, Jana ; Kalčevová, Jana (advisor) ; Zouhar, Jan (referee)
Document type: Master’s theses
Year: 2010
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
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ší. 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: genetic algorithm; heuristic methods; travelling salesman problem; genetický algoritmus; heuristické metody; úloha obchodního cestujícího

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/23543

Permalink: http://www.nusl.cz/ntk/nusl-75095


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Master’s theses