Solving the Traveling Salesman Problem with Ant Colony Optimization: A Revisit and New Efficient Algorithms

Abstract

Ant colony optimization (ACO) techniques are known to be efficient for combinatorial optimization. The traveling salesman problem (TSP) is the benchmark used for testing new combinatoric optimization algorithms. This paper revisits the application of ACO techniques to the TSP and discuss some general aspects of ACO that have been previously overlooked. In fact, it is observed that the solution length does not reflect exactly the quality of a particular edge belong to the solution, but it is only used for relatively evaluating whether the edge is good or bad in the process of reinforcement learning. Based on this observation, we propose two algorithms– Smoothed Max-Min Ant System and Three-Level Ant System– which not only can be easily implemented but also provide better performance, as compared to the well-known Max-Min Ant System. The performance is evaluated by numerical simulation using benchmark datasets.