Comparison of metaheuristic methods by solving travelling salesman problem

Abstract

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.