Abstract
Ant colony optimization (ACO) is a kind of powerful and popular randomized search heuristic for solving combinatorial optimization problems. This paper investigates the performance of two ACO algorithms, called and , on the travelling salesman problem with distance one and two (TSP(1,2)) which is an NP-complete problem. It is shown that two ACO algorithms obtain an approximation ratio of with regard to the optimal solutions in expected polynomial runtimes. We also study the influence of pheromone information and heuristic information on the approximation performance. Finally, we construct an instance and demonstrate that ACO outperforms the local search algorithms on this instance.
Acknowledgments
The authors thank the anonymous reviewers and the editor for their valuable comments and suggestions that help improve this paper.
Disclosure statement
No potential conflict of interest was reported by the authors.