An Improved Algorithm for Single-Cluster TSP Based on ACO

Authors

  • Jianbing Lin College of Information Engineering, Putian University, Putian 351100, China
  • Zhixiong Chen College of Mathematics, Putian University, Putian 351100, China

Abstract

Significant distributing characteristics of nodes in a graph may lead to different convergence and affect the performance of the Travelling Salesman
Problem (TSP). Regarding this, the concepts of domain and density are defined in view of the dense local distribution of nodes in a graph in TSP, and
an improved Ant Colony Optimization (ACO) algorithm named SC-ACO is proposed for TSP using a single cluster feature. In this article, the basic
principles and strategies of an SC-ACO algorithm are introduced, and the pheromone and next node selection probability are processed via the final
domain to distinguish the different behaviors of ants inside and outside the regions with dense nodes. The specific construction process of the SC-ACO
algorithm is then described in detail. Finally, this article creates simulated experiments for TSP using SC-ACO and ACS algorithms, with test results
showing that SC-ACO has obvious advantages over the ACS algorithm in solving TSP problems that have a single cluster and a large scale of nodes.

Keywords: cluster; TSP; SC-ACO; domain; density

Cite As

J. Lin, Z. Chen, “An Improved Algorithm for Single-Cluster TSP Based on ACOâ€, Engineering Intelligent Systems, vol. 28 no. 4, pp. 197-204, 2020.



Downloads

Published

2020-12-01

Issue

Vol. 28 No. 4 (2020): International Journal of Engineering Intelligent Systems

Section

General Submission

License

The submission of a paper implies that, if accepted for publication, it will not be published elsewhere in the same form, in any language, without the prior consent of the publisher. Before publication, authors are requested to assign copyright to CRL Publishing Ltd. This allows CRL to sanction photocopying, and to authorize the reprinting of issues or volumes according to demand. Authors' traditional rights will not be jeopardized by assigning Copyright in this way, as they retain the right to reuse the material following publication, and to veto third-party publication.