Login for students

Login for employees

Publication detail

Comparison of metaheuristic methods by solving travelling salesman problem
Authors: Míča Ondřej
Year: 2015
Type of publication: článek ve sborníku
Name of source: Proceedings of the 9th International Scientific Conference INPROFORUM: Common challenges - Different solutions - Mutual dialogue
Publisher name: Jihočeská univerzita v Českých Budějovicích
Place: České Budějovice
Page from-to: 116-120
Titles:
Language Name Abstract Keywords
cze Porovnání metaheuristických metod prostřednictvím řešení úlohy obchodního cestujícího Úloha obchodního cestujícího je základní úlohou operačního výzkumu. Jedná se o NP-těžkou úlohu. Počet přípustných řešení úlohy je velmi vysoký - roste s faktoriálem počtu uzlů v dopravní síti. Proto ani se současnou výpočetní technikou nelze řešit úlohu obchodního cestujícího pomocí exaktního řešení v rozumném čase. Proto se k řešení používají metaheuristické metody, které jsou schopné poskytnout dostatečně kvalitní řešení v reálném čase. Tento příspěvek se zaměřuje na čtyři základní metaheuristické metody: tabu search, simulované žíhání, genetický algoritmus a metodu mravenčí kolonie. Ke srovnání efektivnosti zkoumaných algoritmů je použita odchylka mezi nejlepším získaným a optimálním řešením. Úloha obchodního cestujícího; Metaheuristické metody; Tabu search; Simulované žíhání; Genetický algoritmus; Metoda mravenčí kolonie
eng Comparison of metaheuristic methods by solving travelling salesman problem Travelling salesman problem (TSP) belongs in basic problems of operations research. It is a NP-hard problem. The number of possible solutions of this problem is very high – it increases with the factorial of the number of the nodes at the graph. So even with nowadays computers it takes very large amount of time to solve TSP with exact methods. Therefore TSP is now usually solved with a heuristic (or metaheuristic) techniques, which provides a satisfactory solution in real-time. This paper focuses on four classical metaheuristic methods: tabu search, simulated annealing, genetic algorithm and ant colony optimization algorithm, and compares all algorithms using difference between best given solution and optimal solution as evaluation criterion. Computational results on several standard instances of TSP show efficiency of all scrutinized methods. Travelling salesman problem; Metaheuristic optimization; Tabu search; Simulated annealing; Genetic algorithm; Ant colony optimization algorithm

Departments

Other Parts

Map

en.mapy.cz

Services

Popular Links

© 2023 University of Pardubice, Studentská 95, 532 10 Pardubice 2
Phone: +420 466 036 111, 466 036 112, 466 036 113
Webmaster, RSS
Data box ID: f5vj9hu
Accessibility Statement
CC BY-NC-ND 4.0Creative CommonsAttributionNonCommercialNoDerivatives