MTSP 的改进模拟退火算法及其求解

毕少辰，石保东，刘小龙，张 蕾

（青岛理工大学a.理学院；b.管理学院，山东 青岛 266520）

0 引言

旅行商问题（Traveling Salesman Problem，TSP）是近代组合优化领域的一个典型难题。旅行商问题可以简单描述为：一个旅行商遍历城市节点集后返回原点的最优线路规划问题。旅行商问题有重要的实际意义和工程背景，在印制电路板转孔、卫星位置调整、电光缆布置、晶体结构分析等多领域得到应用。

受限于枚举的计算限制，近代研究学者提出了一系列针对TSP 问题的算法方案。总体上可以分为基于已有成熟启发式算法的改良算法和借助仿生学提出的新的启发式算法。其中模拟退火算法是求解TSP 较为成熟的算法，具有最值结果质量高、初值鲁棒性强、通用易实现等诸多优点。

模拟退火算法是现代优化算法，模拟退火算法的出现得益于材料统计力学的研究成果。在很多学者的研究中发现，粒子在高温状态下具有较高的能量，在缓慢降温的过程中，粒子能量逐渐减少，粒子的状态趋于稳定。模拟退火算法是基于物理学中固体物质的退火过程与一般优化问题的相似性，通过逐步迭代使中间解逐步向最优解收敛。基于模拟退火算法在求解旅行商问题上的优势，研究并优化一般模拟退火算法以求解多旅行商问题有很大的应用价值。

优化问题可以转化为目标函数的极值问题，对于多目标的优化问题，多目标优化时存在各优化目标之间的制约关系，在模拟退火改进过程中，优化一项目标会使另一项目标偏离。需要对优化的各个目标设置权重，协调各目标的影响程度。在实际问题中，考虑各种资源平衡的情况下，模拟退火算法使用起来往往得不到预期的最优规划。

多旅行商问题（MTSP）是经典旅行商问题的推广。在现实应用的过程中，多旅行商问题的影响因素往往更加复杂，单纯考虑运行路径的总长度会导致路径之间极不均衡。结合模拟退火算法在求解旅行商问题上的优势，本文通过改进模拟退火算法，在算法中引入综合目标函数，对总运行路径和其他影响因素进行综合评价。改进模拟退火算法，可以综合衡量多个因素对最终结果的影响程度。

1 模拟退火算法简介与改进

1.1 综合目标函数改进模拟退火算法

为解决路径长度与子路径均衡程度相冲突的问题，文章引入综合目标函数：

公式（1）（2）中，Z 为综合目标函数，用于综合衡量路径优劣程度，S 为路径总长度，J 为子路径的均衡度。a、b 分别为总路径与均衡度的权重系数。

总路径长度S 为：

L为第i 段子路径的长度。

期望反映变量的平均取值的大小，偏差与方差均是衡量源数据与期望的离散程度的度量值。应用统计学中标准方差的表示形式，均衡度可通过式（4）进行衡量：

为了统一量纲和简化计算，将均衡度J 定义为：

1.2 改进模拟退火算法流程

（1）给定初始温度T、降温系数α、终止温度T并通过固定关键节点插值法与蒙特卡洛算法给定较优初始解。

（2）根据关键节点划分子路径，计算各子路径长度L与各子路径均衡程度J。

（4）进行2 变换、3 变换（交换解序列中任意2 或3个节点的位置），得到新解。

（6）在同一温度下进行多次内循环，求得该温度下的较优解。

（7）按降温系数T-α·T 退火，当T=T时停止迭代。

2 数值算例

无线传感器网络（Wireless Sensor Network，WSN）在生活中被广泛应用。无线传感网络，需要传感器、数据中心和移动充电器三部分相互协同进行运作。高效的路由算法能有效降低网络能量消耗，延长网络寿命。为保证传感器有足够电量来正常工作，数据中心需要按时用充电器为传感器充电。传感器和数据中心分布在同一个二维平面内，数据中心与任意一个传感器、任意传感器之间都相互连通。数据中心和传感器的位置可以通过水准测量以坐标的形式确定，也可基于自身定位设备确定。

传感器电量消耗由充电器消耗和运行路程上的损耗两部分组成，为减少能量损失，需要规划移动充电器在传感器之间的最短运行路线。为提高充电工作的效率，网络中有四台移动充电器为传感器充电。求四台充电器运行的最佳运行路线。

在原有路径中设置D、D、D三个插入点作为充电器的出发点，得到距离矩阵。

单纯以总路程最短为要求，求最优解，就会导致4个传感器运行的线路极为不均衡。总路程最短情况下的不均衡运行线路见图1。

如图1 所示，总路程最短不一定能使各个充电器任务均衡。在4 个充电器总运行距离最短的情况下，求解出的不均衡的分布线路，虽然满足充电器总能量损失最小，但总的时间周期加长，使体系的总体充电效率变低。

图1 总路程最短变情况下的不均衡运行线路图

总路径长度S 为：

由于随机的位置交换，可能改变插入节点的位置。所以在新路径中，以插入的新节点出现的前后顺序划分四段子路径，将四段子路径的距离依次标记为L、L、L、L。

新得到的路径的四段子路径形成的距离矩阵表示为MaxL=（L，L，L，L）。

进行多次降温模拟，得到权重系数为1∶1 情况下，综合目标函数最小情况下的运行路径，如图2 所示。

图2 4 个充电器运行路径示意图

4 个充电器的运行路径长度分别为：

3 514.04 0 693 829 77 米、3 456.1 59 670 828 92米、3 780.35 8 008 895 60 米、3 488.70 6 674 434 52 米。

此时的总路径长度为14 239 米。

最优解时综合目标函数值Z＝14.68。

总路程极短（路径长度系数a 远大于均衡度系数b）情况下，运行路径的总长度为12.833 2 千米。由前文分析得出，在一条路径下运行距离最短，最短距离为11.483 2 千米。12.833 2 千米非常趋近于最优解。

在总路径均衡（路径长度系数a 远低于均衡度系数b）的情况下，四段子路程的距离分别为3.666 5 千米、3.529 2 千米、3.727 8 千米、3.712 2 千米。这里使用统计学中标准方差的表现形式，体现四段子路径对于均值的离散程度。

四段子路径的均衡度为d（X）=0.078 211 168，趋近零值，即四段子线路的长度非常接近。

实际应用中，可根据具体问题对“路径总长度”和“子路径均衡度”的不同需求，为两者选定不同的权重系数，从而求取相应条件下的最优解。

3 结论

本文改进的模拟退火算法，将多旅行商问题中的总路径长度与子路径均衡度同时参与迭代。综合目标函数Z，可以根据对“路径”和“均衡度”的重视程度设置权重。在求解路径长度和子路径的均衡度问题上，很容易通过系数的变化来掌控。通过这种方法可以求解多旅行商问题中“路径尽可能短”“路径尽可能均衡”以及“在尽可能均衡的条件下求最短”等类似问题。

例如：如果需要使总路径尽可能短，即可增加路径权重，降低均衡度权重。

同时保留了模拟退火算法在求解经典旅行商问题时其固有的全局寻优能力。最终求解方案的子路径均衡，每个旅行商运行完各自路径的时间相对接近，其综合效率较高；改进后的模拟退火算法在求解时间和求解精度上都有较好的表现。