A modified two-part wolf pack search algorithm for the multiple traveling salesmen problem

作者：Chen, Yongbo; Jia, Zhenyue; Ai, Xiaolin; Yang, Di; Yu, Jianqiao^*

来源：Applied Soft Computing, 2017, 61: 714-725.

DOI：10.1016/j.asoc.2017.08.041

• Multiple travelling salesmen problem (MTSP)
• Modified two-part wolf pack search (MTWPS) algorithm
• Transposition and extension (TE) operation
• Convergence rate
• Reachability

This paper proposes a modified two-part wolf pack search (MTWPS) algorithm updated by the two-part individual encoding approach as well as the transposition and extension (TE) operation for the multiple travelling salesmen problem (MTSP). Firstly, the two-part individual encoding approach is introduced into the original WPS algorithm for MTSP, which is named the two-part wolf pack search (TWPS) algorithm, to minimize the size of the problem search space. Secondly, the analysis of the convergence rate performance is presented to illustrate the reasonability of the maximum terminal generation of the novel TWPS algorithm deeply. Then, based on the definition of the global reachability, the TWPS algorithm is modified by the TE operation further, which can greatly enhance the search ability of the TWPS algorithm. Finally, focusing on the objective of minimizing the total travel distance and the longest tour, comparisons of the robustness and the optimality between different

• 出版日期2017-12
• 单位北京理工大学