4.5 Article

A novel state transition simulated annealing algorithm for the multiple traveling salesmen problem

期刊

JOURNAL OF SUPERCOMPUTING
卷 77, 期 10, 页码 11827-11852

出版社

SPRINGER
DOI: 10.1007/s11227-021-03744-1

关键词

2opt; Elementary breakpoint operator; Multiple traveling salesmen problem; State transition simulated annealing algorithm

资金

  1. National Natural Science Foundation of China [21606159]
  2. Key Research and Development Program of Shanxi Province [201803D121039]

向作者/读者索取更多资源

This study introduces an intelligent algorithm for solving the multiple traveling salesman problem using metropolitan criteria and basic matrix operations to generate the solution space, while enhancing the ability to capture the global optimal solution by introducing the 2opt neighborhood search structure. Experimental results demonstrate the superior performance of this method in MTSP.
In this study, we consider the multiple traveling salesman problem (MTSP) with multiple depots, closed paths, and a constraint on the number of cities visited by each traveling salesman. In our previous study, we proposed a state transition simulated annealing algorithm (STASA) that employs the Metropolitan criterion for simulated annealing to solve the traveling salesman problem (TSP). The results obtained were significantly improved according to our previous experiments. In the present study, we propose a new intelligent operator to solve the MTSP called an elementary breakpoint operator, which can generate the solution space for MTSP through elementary matrix operations. A neighborhood search structure called 2opt, which can improve the quality of the solution by connecting two shorter non-adjacent arcs, is then introduced into STASA to enhance the ability to capture the global optimal solution. Finally, comparative experiments were conducted based on a wide range of TSPLIB benchmark instances using our proposed algorithm and other algorithms, and the results demonstrated the superior performance of our proposed approach compared with all other state-of-the-art approaches for MTSP.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据