Improved Ant Colony System for the Traveling Salesman Problem


The KIPS Transactions:PartB , Vol. 12, No. 7, pp. 823-828, Dec. 2005
10.3745/KIPSTB.2005.12.7.823,   PDF Download:

Abstract

Ant Colony System (ACS) applied to the traveling salesman problem (TSP) has demonstrated a good performance on the small TSP. However, in case of the large TSP, ACS does not yield the optimum solution. In order to overcome the drawback of the ACS for the large TSP, the present study employs the idea of subpath to give more information to ants by computing the distance of subpath with length w. In dealing with the large TSP, the experimental results indicate that the proposed algorithm gives the solution much closer to the optimal solution than does the original ACS. In comparison with the original ACS, the present algorithm has substantially improved the performance. By utilizing the proposed algorithm, the solution performance has been enhanced up to 70% for some graphs and around at 30% for averaging over all graphs.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
I. K. Kim and M. Y. Yun, "Improved Ant Colony System for the Traveling Salesman Problem," The KIPS Transactions:PartB , vol. 12, no. 7, pp. 823-828, 2005. DOI: 10.3745/KIPSTB.2005.12.7.823.

[ACM Style]
In Kyeom Kim and Min Young Yun. 2005. Improved Ant Colony System for the Traveling Salesman Problem. The KIPS Transactions:PartB , 12, 7, (2005), 823-828. DOI: 10.3745/KIPSTB.2005.12.7.823.