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

  • Hoang Xuan Huan University of Engineering and Technology, Vietnam National University, Hanoi
  • Nguyen Linh-Trung University of Engineering and Technology, Vietnam National University, Hanoi
  • Do Duc Dong Institute of Information Technology, Vietnam National University, Hanoi
  • Huu-Tue Huynh International University, Vietnam National University, Ho Chi Minh City
DOI: https://doi.org/10.21553/rev-jec.44

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.
Published
2013-06-01
Issue
Vol. 2, No. 3-4 (Jul-Dec, 2012)
Section
Regular articles
An author's submission implies that the manuscript has not been published previously, and is not currently submitted for publication elsewhere. Submission also implies that the Corresponding Author has consent of all authors (the Authors). Upon acceptance for publication transfer of copyright will be made to the Publisher of REV-JEC, who guarantees that full content of the published article is freely distributed on the Journal's website. The copyright transfer gives the Publisher of REV-JEC full authority to resolve any complaints of misuse or abuse (such as infringement or plagiarism) of the published article. The Authors have the freedom to redistribute and reuse the published article in any medium or format for any purpose, provided the original published article is properly cited. An article submission implies author agreement with this policy.