SOLVING THE TRAVELING SALESMAN PROBLEM BY AN EFFICIENT HYBRID METAHEURISTIC ALGORITHM

Abstract

The traveling salesman problem (TSP) is the problem of finding the shortest tour through all the nodes that a salesman has to visit. The TSP is probably the most famous and extensively studied problem in the field of combinatorial optimization. Because this problem is an NP-hard problem, practic al large-scale instances cannot be solved by exact algorithms within acceptable com putational times. So, an efficient hybrid metaheuristic algorithm called ICA TS is proposed in this paper. The first stage of the ICATS is to solve the TSP by the imperialist competitive algorithm (ICA), and then the TS is used for improving soluti ons. This process avoids the premature convergence and makes better solutions. C omputational results on several standard instances of TSP show efficiency othe proposed algorithm compared with the genetic algorithm (GA), bee colon y optimization (BCO), and particle swarm optimization (PSO).