A hybrid algorithm combining glowworm swarm optimization andcomplete 2-opt algorithm for spherical travelling salesman problems

作者：Chen, Xin; Zhou, Yongquan^*; Tang, Zhonghua; Luo, Qifang

来源：Applied Soft Computing, 2017, 58: 104-114.

DOI：10.1016/j.asoc.2017.04.057

• Travelling salesman problem
• Glowworm swarm optimization
• Complete 2-opt algorithm
• Spherical TSP
• Approximate algorithm

The Travelling Salesman Problem (TSP) is one of the most well-known combinatorial optimization problems and has attracted a lot of interests from researchers. Many studies have proposed various methods for solving the two-dimensional TSP. In this study, we extend the two-dimensional TSP to the three-dimensional TSP, namely the spherical TSP in which all points (cities) and paths (solutions) are on the surface of a sphere. A hybrid algorithm based on the glowworm swarm optimization (GSO) and the complete 2-opt algorithm is proposed, in which the carriers of the luciferin are transformed from glowworms to edges between cities, and the probabilistic formula and the luciferin updating formula are modified. In addition, the complete 2-opt algorithm is performed to optimize the selected optimal routes every few iterations. Numerical experimental results show that the proposed algorithm has a better performance than the basic GSO in solving the spherical TSP. Meanwhile, the complete 2-opt algorithm can speed up the convergence rate.

• 出版日期2017-9
• 单位大连理工大学; 广西民族大学