Comparison of metaheuristic methods by solving travelling salesman problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216275%3A25510%2F15%3A39899996" target="_blank" >RIV/00216275:25510/15:39899996 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Comparison of metaheuristic methods by solving travelling salesman problem

Popis výsledku v původním jazyce

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 evenwith 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.

Název v anglickém jazyce

Comparison of metaheuristic methods by solving travelling salesman problem

Popis výsledku anglicky

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 evenwith 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.

Druh

D - Stať ve sborníku

CEP obor

AH - Ekonomie

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 9th International Scientific Conference INPROFORUM: Common challenges - Different solutions - Mutual dialogue

ISBN

978-80-7394-536-7

ISSN

2336-6788

e-ISSN

—

Počet stran výsledku

5

Strana od-do

116-120

Název nakladatele

Jihočeská univerzita v Českých Budějovicích

Místo vydání

České Budějovice

Místo konání akce

České Budějovice

Datum konání akce

5. 11. 2015

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—