Approximation performance of ant colony optimization for the TSP(1,2) problem

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 ${\mathrm{MMAS}}_{\mathrm{Ord}}^{\ast }$ and ${\mathrm{MMAS}}_{\mathrm{Arb}}^{\ast }$, 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 $3/2$ 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.

Keywords:

• ant colony optimization
• approximation performance
• runtime analysis
• TSP(1,2)
• NP-complete

2010 AMS Subject Classifications:

• 68W20
• 68W40

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.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant numbers 61170081, 61175127 and 61472143].