Solving the Traveling Salesman Problem by an Efficient Hybrid Metaheuristic Algorithm

The traveling salesman problem (TSP) is the problem of finding the shortest tourthrough all the nodes that a salesman has to visit. The TSP is probably the mostfamous and extensively studied problem in the field of combinatorial optimization.Because this problem is an NP-hard problem, practical large-scale instances cannotbe solved by exact algorithms within acceptable computational times. So, anefficient hybrid metaheuristic algorithm called ICATS is proposed in this paper. Thefirst stage of the ICATS is to solve the TSP by the imperialist competitive algorithm(ICA), and then the TS is used for improving solutions. This process avoids thepremature convergence and makes better solutions. Computational results onseveral standard instances of TSP show efficiency of the proposed algorithmcompared with the genetic algorithm (GA), bee colony optimization (BCO), andparticle swarm optimization (PSO).

کلیدواژه ها:

Tabu search ، Imperialist competitive algorithm ، Traveling salesman problem ، NP-hard problems