Return to search

Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího / Heuristic and metaheuristic methods for travelling salesman problem

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.

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:75095
Date January 2010
CreatorsBurdová, Jana
ContributorsKalčevová, Jana, Zouhar, Jan
PublisherVysoká škola ekonomická v Praze
Source SetsCzech ETDs
LanguageCzech
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0015 seconds