Comparison of metaheuristic methods by solving travelling salesman problem
Konferenční objektOtevřený přístuppeer-reviewedpostprintDatum publikování
2015
Autoři
Vedoucí práce
Oponent
Název časopisu
Název svazku
Vydavatel
Jihočeská univerzita v Českých Budějovicích
Abstrakt
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.
Rozsah stran
p. 116-120
ISSN
2336-6788
Trvalý odkaz na tento záznam
Projekt
Zdrojový dokument
Proceedings of the 9th International Scientific Conference INPROFORUM: Common challenges - Different solutions - Mutual dialogue
Vydavatelská verze
Přístup k e-verzi
Práce není přístupná
Název akce
INPROFORUM 2015: 9th International Scientific Conference (05.11.2015 - 06.11.2015)
ISBN
978-80-7394-536-7
Studijní obor
Studijní program
Signatura tištěné verze
Umístění tištěné verze
Přístup k tištěné verzi
Klíčová slova
Travelling salesman problem, Metaheuristic optimization, Tabu search, Simulated annealing, Genetic algorithm, Ant colony optimization algorithm, Úloha obchodního cestujícího, Metaheuristické metody, Tabu search, Simulované žíhání, Genetický algoritmus, Metoda mravenčí kolonie