Academic Journals Database
Disseminating quality controlled scientific knowledge

Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: quality, uncertainty and speed

Author(s): Marek Antosiewicz | Grzegorz Koloch | Bogumił Kamiński

Journal: Journal of Theoretical and Applied Computer Science
ISSN 2299-2634

Volume: 7;
Issue: 1;
Start page: 46;
Date: 2013;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: metaheuristic algorithms | travelling salesman problem

We compare six metaheuristic optimization algorithms applied to solving the travelling salesman problem. We focus on three classical approaches: genetic algorithms, simulated annealing and tabu search, and compare them with three recently developed ones: quantum annealing, particle swarm optimization and harmony search. On top of that we compare all results with those obtained with a greedy 2-opt interchange algorithm. We are interested in short-term performance of the algorithms and use three criteria to evaluate them: solution quality, standard deviation of results and time needed to reach the optimum. Following the results from simulation experiments we conclude that simulated annealing and tabu search outperform newly developed approaches in short simulation runs with respect to all three criteria. Simulated annealing finds best solutions, yet tabu search has lower variance of results and converges faster.
RPA Switzerland

RPA Switzerland

Robotic process automation


Tango Jona
Tangokurs Rapperswil-Jona