Solving the Traveling Salesman Problem using an improved ant colony algorithm based on the nearest neighbor algorithm

Abstract

In this paper, we address the Traveling Salesman Problem (TSP), which is an NP-hard problem. Many meta-methods have been applied to solve such a problem in the literature. In this work, the Ant Colony Optimization (ACO) algorithm is applied to TSP, which is one of the population-based competitive algorithms used to solve many generative optimization problems in various engineering fields. By optimizing its problem-dependent parameters setting, the overall performance of the Ant Colony algorithm is improved, and the execution time is reduced. We have found through experiments that the performance of the ACO algorithm needs to be enhanced. Therefore, we have developed a new algorithm (NN-ACO) by hybridizing the ACO algorithm with the nearest neighbor algorithm, which is a greedy algorithm that finds the candidate solution to the TSP using simple approximate heuristics. The results of the ACO algorithm and the hybrid ACO algorithm are compared together in terms of solution quality and execution time. Moreover, the result based on the linear programming formulation of the test problem is used to evaluate the quality of the solutions obtained using the applied meta-heuristic methods. In addition, the algorithm is applied to a benchmark set of TSP problems and its performance is compared with some other hybrid algorithms in the literature. The experimental results show that the proposed algorithm outperforms other hybrid algorithms in terms of solution quality.