Repetitive Nearest Neighbor Based Simulated Annealing Search Optimization Algorithm for Traveling Salesman Problem

The traveling salesman problem (TSP) is the most popular and most studied non-deterministic polynomial (NP) hard problem that has been used in various fields of science and technology. Due to the NP-hard nature, it is very difficult to solve this problem effectively and efficiently. For this reason, diverse appropriate optimization algorithms have been designed and developed in the last few decades. Among these algorithms, heuristic algorithms are much more suitable to tackle with this complex problem. In this paper, we propose a hybrid heuristic algorithm to solve the symmetric TSP problem by combining the search mechanism of repetitive nearest neighbor (RNN) heuristic and simulated annealing (SA) heuristic algorithms. In fact, a set of better routes are generated step by step by the RNN algorithm and these routes are improved through the iterative improvement process of the SA algorithm. The proposed algorithm is tested on a set of benchmark symmetric TSP datasets and compared with the basic RNN and SA algorithms as well as some other hybrid algorithms existing in the literature. It is demonstrated by the experimental results that the proposed algorithm is more effective than both the basic RNN and SA algorithms, and the obtained optimum results are in good agreement with the corresponding best-known optimum results. In addition, the proposed algorithm outperforms some other hybrid algorithms in terms of solution quality.