An Approach for Solving Traveling Salesman Problem using Hybrid Ant Colony Optimization

Abstract

Traveling salesman problem (TSP) is one of the most famous combinatorial optimization (CO) problems, which has wide application background. Ant Colony Optimization (ACO) is a heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization problems and taken as one of the high performance computing methods for TSP. ACO has very good search capability for optimization problems, but it still has some drawbacks for solving TSP. These drawbacks will be more obvious when the problem size increases. The present paper proposes an ACO algorithm with nearest neighbor (NN) heuristic approach and information entropy which is conducted on the configuration strategy for the adjustable parameters to improve the efficiency of ACO in solving TSP. The performance of ACO also depends on the appropriate setting of parameters. Then, ACO for TSP has been improved by incorporating local optimization heuristic. Algorithms are tested on benchmark problems from TSPLIB and test results are presented. From our experiments, the proposed algorithm has superior search performance over traditional ACO algorithms do.