刘云龙1 王盈钦2 廖 旭3
（1.长沙理工大学物理与电子科学学院 湖南 长沙 410000；
2.长沙理工大学计算机与通信工程学院 湖南 长沙 410000；3.长沙理工大学数学与统计学院 湖南 长沙 410000）
摘要：本文构建基于 TSP、MTSP 问题的动态规划模型，运用改良圈算法、蚁群算法、模拟退火算法、遗传算法对无线可充电传感器网络路线规划问题进行求解。本文将移动充电器能量消耗最小化等价为行走路径最短问题。借助球面距离公式计算出各点之间的距离，利用改良圈算法构造一个哈密尔顿回路，得出近似最短路径；之后利用蚁群优化算法，进行大量具有重复性的试验，选取其中最短路径作为最优解；其次通过模拟退火算法对最优解进行检验。最终确定 MC 行走最短路径和路径长度。
关键词： TSP；MTSP；蚁群算法；模拟退火算法；遗传算法
一、问题背景
随着传感器技术、无线通讯技术等互联网技术的高速发展，无线传感器网络 WSN 在生活的各个领域都扮演着重要的角色。而能量则是影响 WSN 生命周期最重要的一个因素。为了使 WSN 持续不断地运作，就必须保证 WSN 时刻有充足的能量。介于环境能源的不稳定性和依赖性，电池的持续稳定供电能力受到高度重视，从而诞生了无线可充电传感器网络 WRSN。
二、问题分析
在只派一个移动充电器对所有节点充电的情况下，要使能耗最小化，等同于移动充电器行走路程最短。这是一个典型的 TSP 问题，通过不断改良初始 Hamilton 圈来得到一个具有较小权值的哈密尔顿回路，但该方法得出的结果一般不是最优解。继而运用蚁群算法，通过比较最终路径距离来选取相对较短的路径，从而得到最优解。
三、传感器网络最优化路径模型构建与求解
3.1 模型简介
本题求解无线可充电传感器网络最优路径，其实质为 TSP 问题，抽象构建出个节点地理坐标，计算得各节点之间距离，产生距离矩阵并通过大量有限次迭代，从距离矩阵中产生一个近似最优化路径。
3.2 模型建立
（1）球面距离
基于传统欧几里得距离的 TSP 问题思路出发，本文采用非欧几何球面距离。地理学上人们将地球看作一个标准的圆球体，从地球球心出发，规定水平和垂直两个平面，将水平面垂直于轴线上下形成一组平行平面、将垂直平面绕轴线旋转，即得到数条经纬线。这数条经纬线便构成一个三维坐标系，地球表面的任何一位置均可由经纬度所组成的信息来表示。
故在将地球视为正球体和忽略各地海拔高度差异情况下，假设球面有两处位置分别为 A(xi,yi)、B(xj,yj)，x 表示纬度、y 表示经度，以地球的平均半径 R=6371km 表示正球体的半径，则球面上两点的距离公式 可表示为：
.jpg)
（2）算法模型构建
将所有数据可视化，各节点经纬度导入地图中，为方便分析，将节点坐标抽象至二维坐标系近似代替。基于上述的节点地理坐标散点图，为了求得最优化路径，首先需要求的任意两节点间的距离。
本文首先采用解决 TSP 问题常用的改良圈算法进行简单高效的运算，但因为改良圈算法常不能得到最优解，故接着采用蚁群算法优化，通过大量迭代求出最优解。
利用改良圈算法所构成的是一个哈密顿回路，即指定数据中心为起点，途中无重复地经过其他所有节点，并最终回到起点数据中心。假设有 n 各节点；xij 表示从节点 i 到节点 j 的路程；rij 表示判断是否从第 i 个节点走到第 j 个节点的 01 型变量；A 为目标函数表示最短出行距离，其公式如下：
.jpg)
基于以上以构建的目标函数和改良圈算法可以求取出一个 Hamilton 圈，接着在1 ≤ i < i + 1 < j ≤ n 条件下修改 A 可得具有较小权的新 Hamilton 圈但 Hamilton 算法的一大缺点便是，根据该算法求得的一般是近似最优解，几乎很难得到最优解，因此在求得近似最优解的基础上，引出蚁群优化算法从而求得最优解。
本文从以上算法构建描述中总结出蚁群算法的执行过程，其执行过程如下图1所示：
.jpg)
图 1 蚁群算法流程图
3.3 模型求解
根据改良圈算法近似最优的特点，猜测上文结果并非最优化结果，继而运用蚁群智能优化算法验证猜测，并得出最优解。
蚁群算法属于随机优化算法，因其开始和过程都是随机的数值，故每轮运行产生的结果基本都会有差异，而在大数量次数运行情况下，其结果大致收敛方向是一致的。编写 MATLAB 程序（见附录 D），多次运行调整迭代数比较寻找最优解，由于需要大数量次运行比较才能获得最优解，因此本文基于蚁群算法作近百次试验。但介于数据较多，在大量的实验数据中，我们选取下列具有代表性的二十组试验数据以便展开进一步的分析，其最优化路径如图2所示：
.jpg)
图 2 蚁群算法最优路径
可以观测到最短距离收敛轨迹随迭代次数增加而不断降低最终趋于平稳、平均距离的结果不尽相同但有显著的收敛趋势，证明了了迭代过程的正确性。
3.4 模型检验
图 3 模拟退火算法
.jpg)
本文运用模拟退火算法，在相同假设条件下，进行最优化路径求解验证。
取不同初始温度及迭代次数进行运算，发现迭代次数在一定范围内对最优化结果影响不大 ，而初始温度 T0 对最优化结果影响较大，因此要选择合适的初始温度。本文构建模拟退火算法时，设置最大迭代次数为 250，在任一温度下最大迭代次数为 200，通过多次运行，得出最优化路径图。
与基于蚁群优化算法得出的最优路径作对比，发现两图完全重合，即所得最优化路径，从侧面验证了基于蚁群算法得出的最优解的合理性和正确性。
六、模型评价
本文通过建立、检验算法模型，较好地模拟了实际情况，并对相应问题给出了具体解答。
模型一较灵活地运用 Hamilton、AG、SA 算法模型，由 Hamilton 算法作引，AG、SA 算法得果，多个算法相互比照，使结果更具有代表性意义。
本文着眼全局，对模型进行相应程度的简化，对现实问题中路径设定的评估和范围性规划提供了简易且不失严谨性的策略。
参考文献：
[1]WU Haohua, CAO Qian. 基于球面距离的旅行商问题及其应用 [J]. 物流科技, 2019,042(001):1013.
[2]曹政. 基于蚁群与分簇算法的无线传感器网络路径寻优与恢复算法研究 [D]. 2016.
[3]孙波, 刘士彩, 王玉潇, 等. 基于 Hamilton 回路的交通线路规划 [J]. 汽车与安全, 2018,000(010):9296.
[4]李运涛, 余粟. 模拟退火智能算法在 TSP 问题中的应用 [J]. 产业与科技论坛, 2017(3).
[5]邱军林, 周永权, 张亚红. 基于 GA 的 MTSP 问题实现 [J]. 微计算机信息, 2010,26(006):224225.