求解旅行商问题的联合算子模拟退火算法  

Simulated annealing algorithm with joint operator for traveling salesman problem

作　　者：李昌兴 黄杉 LI Changxing;HUANG Shan(School of Science,Xi’an University of Posts and Telecommunications,Xi’an 710121,China;School of Communications and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

机构地区：[1]西安邮电大学理学院,陕西西安710121 [2]西安邮电大学通信与信息工程学院,陕西西安710121

出　　处：《西安邮电大学学报》2022年第4期89-94,共6页Journal of Xi’an University of Posts and Telecommunications

基　　金：陕西省社会科学联项目(2021ND0345);陕西省大学生创新创业训练计划项目(S202211664132)。

摘　　要：对模拟退火算法求解旅行商问题的反序、移位和交换操作算子的特征与相互关系进行研究,发现交换操作等价于两个嵌套的反序操作的叠加复合。利用这种等价关系,提出一种新的交换-反序联合算子模拟退火算法。该算法先分别计算两个嵌套的反序操作的路径差,再将两个路径差相加得到交换操作的路径差,同时获得3组新解。通过对Eil51、Eil76、Eil101和Ch150等不同规模的旅行商问题进行测试,仿真结果表明,联合算子模拟退火算法的性能优于使用现有的移位、交换、反序算子以及这些算子的组合方案的模拟退火算法。The relationships of reverse,shift and exchange operators are analyzed to solve the traveling salesman problem by the simulated annealing algorithm.It is found that the exchange operation is equivalent to the superposition and composition of two nested reverse order operations,based on which,a new exchange-reverse joint operator is proposed.The path difference of the two nested reverse operators is calculated respectively,and then the path difference of the exchange operator is obtained by adding the two path differences,which can achieve three new solutions simultaneously.Through the test of different scale of traveling salesman problems such as Eil51,Eil76,Eil101 and Ch150,simulation results show that the performance of the joint operator simulated annealing algorithm is better than that of the existing shift,exchange and reverse operators,as well as their combination scheme in the simulated annealing algorithm.

关 键 词：旅行商问题 模拟退火算法 反序操作 交换操作 联合算子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]