New Imperialist Competitive Algorithm to solve the travelling salesman problem

Abstract

Imperialist Competitive Algorithm (ICA), which is a new socio-politically motivated global search strategy, is one of the intelligent computational algorithms. ICA has always been used to solve continuous problems. In this paper, however, ICA is applied to the travelling salesman problem (TSP), which is one of the most important discrete problems. The proposed algorithm is tested on 14 standard instances consisting of 50–199 nodes used in the literature. The computational results show that the ICA results are competitive with the results of other meta-heuristic algorithms used for solving the TSP. Furthermore, the proposed algorithm has been able to produce solutions which are very close to best-known solutions (BKS) for most of the instances in which 11 BKS are also found within a reasonable time.

Keywords:

• Imperialist Competitive Algorithm
• travelling salesman problem
• local search
• order crossover

2010 AMS Subject Classification:

• 68T20