本研究论文《基于模拟退火蚁群算法的机器人路径规划方法》由袁佳泉、李胜、吴益飞、郭健四位作者完成，作者单位均隶属于南京理工大学自动化学院。该研究发表于2019年10月的《计算机仿真》期刊第36卷第10期。
本研究的学术背景聚焦于机器人学与自动化领域的路径规划问题。随着电力系统自动化水平提升，变电站数量激增，传统人工巡检方式面临劳动强度大、效率低、恶劣天气难以作业等挑战。因此，变电站智能巡检机器人应运而生，而高效的路径规划是其实现自主导航、提升巡检效率的核心技术。当前的路径规划方法，如分层A*算法、Hopfield神经网络、遗传算法及基本蚁群算法等，在应用于变电站半结构化环境时，分别存在搜索空间划分复杂、神经网络参数难以确定、计算量大或易陷入局部最优解（局部最优）等问题。在此背景下，本研究旨在针对变电站巡检任务的特点，提出一种能够同时优化路径长度和经过节点数量的高效路径规划方法，以节省巡检时间，优化巡检路线。
研究的详细工作流程可分为三个主要部分：环境建模、局部路径规划和全局路径规划。
首先，在环境建模阶段，研究分析了变电站的地图特征。鉴于栅格地图在大型环境中存储需求大，而拓扑地图（拓扑地图）能够忽略环境细节、以节点和连接关系紧凑表示环境，本研究采用拓扑地图对变电站环境进行建模。具体而言，将变电站中的巡检设备位置（如设备点）和机器人需要改变运动状态的关键位置（如十字路口）抽象为图中的节点，将节点间可通行的直线路径抽象为边，从而构建了变电站的简化拓扑模型。该模型通过邻接矩阵进行数据表示，为后续应用图论算法奠定了基础。
其次，在局部路径规划阶段，研究将巡检任务分解为局部与全局两个子问题。针对任意两个给定巡检点之间的最短路径规划问题，研究采用了经典的Dijkstra算法。该算法以构建的拓扑地图为基础，通过逐步扩展最短路径节点集的方式，计算出图中任意两个巡检点之间的最短距离、具体路径序列以及该路径所经过的节点数量。这个过程为后续的全局规划提供了精确的“点对点”距离和“绕路代价”数据。
第三，也是本研究的核心，即全局路径规划阶段。在获得所有巡检点间两两最短路径后，问题被转化为一个需要访问所有指定巡检点（包括起点充电室）并返回起点的多目标旅行商问题（Multi-Objective TSP）。其优化目标有两个：一是总路径距离最短，二是总经过的节点数最少（以减少停顿和转向）。为求解此复杂问题，研究创新性地提出了一种双层启发式算法框架。
首先，研究引入“偏离度”概念将多目标优化转化为单目标优化。偏离度公式为：d = w1(d-d)/d + w2(n-n)/n，其中d和n分别是当前解的路径总长和经过节点总数，d*和n*是已知或迭代中发现的最佳值，w1和w2是权重系数（研究中分别设为0.7和0.3）。偏离度越小，表示当前解的综合满意度越高。这个值被用作评价解优劣和指导算法搜索的核心指标。
其次，研究设计并实现了模拟退火蚁群算法（Simulated Annealing Ant Colony Algorithm）作为求解器。该算法融合了蚁群算法（Ant Colony Algorithm）的群体协作、正反馈寻优能力和模拟退火算法（Simulated Annealing）的概率突跳特性以避免早熟收敛。具体工作流程如下：1）初始化蚁群参数及模拟退火温度。每只蚂蚁从固定起点（充电室）出发，依据状态转移概率公式选择下一个未访问的巡检点。此处的启发式信息η被设计为综合考虑标准化后的距离和节点数的函数，即η_ij = 1/(w1*d_ij’ + w2*n_ij’)，引导蚂蚁偏好距离短、中间节点少的路径。2）每只蚂蚁构建完一条完整路径（一个解）后，会立即对路径上的信息素进行局部更新，旨在降低该路径对后续蚂蚁的吸引力，增加探索新路径的可能性。3）当所有蚂蚁完成一次迭代（构建出m个解）后，从中找出偏离度最小的当前最优解。4）进入模拟退火环节：以该当前最优解为基础，通过节点“互换、逆转、平移”等操作产生新解。依据模拟退火准则，以一定概率接受劣质新解（该概率由新解与旧解的偏离度差值和当前温度共同决定），从而帮助算法跳出局部最优陷阱。5）仅对本次迭代中找到的（或经过退火优化后的）全局最优路径进行全局信息素增强更新，加快算法向优质区域收敛。6）降低温度参数，重复步骤2-5，直至温度降至设定阈值，输出最终的最优巡检点访问序列。最后，将此全局最优序列中的每一段“巡检点对”，用第一阶段Dijkstra算法计算出的具体最短路径进行替换和拼接，从而得到机器人最终可执行的最优巡检路线。
本研究的主要结果通过两个仿真算例进行了验证。第一个算例基于一个包含25个节点（12个巡检点，13个关键点）的变电站示例模型。对于“正常巡检”任务（从充电室出发，访问全部12个巡检点后返回），模拟退火蚁群算法规划出的全局路径顺序为1->2->10->3->11->12->6->5->9->8->7->4。经局部路径填充后，得到总长度为2120米、经过节点数为13的完整路径，其计算出的偏离度为0，表明该解在两个优化目标上均达到了当前模型下的最优平衡。对于“特殊巡检”任务（从15号点出发，访问指定的3、5、6、7号点），算法规划出的路径为15->7->5->6->3，总长1320米，经过5个节点，偏离度为0.1。结果显示了算法在不同任务模式下的有效性和灵活性。第二个算例针对更大规模（150个节点）的场景，并将优化目标聚焦于单一的最短路径（设w1=1）。通过对比模拟退火算法、基本蚁群算法和本文提出的混合算法的迭代曲线，结果表明，模拟退火蚁群算法能够收敛到更优的解，且收敛速度更快，证明了其在解决大规模路径规划问题时的优越性能。
本研究的结论是，针对变电站巡检机器人的路径规划需求，所提出的基于模拟退火蚁群算法的双层启发式方法能够有效地进行规划。该方法首先利用Dijkstra算法精确求解局部最短路径，继而通过融合偏离度评价、模拟退火机制的改进蚁群算法解决多目标全局优化问题。仿真结果表明，该方法能够快速规划出路径相对更短、经过节点相对更少的最优或近优巡检路径。
本研究的价值主要体现在科学价值与应用价值两个方面。在科学价值上，研究提供了一种解决多目标TSP问题的有效混合启发式算法思路，创新性地将偏离度作为信息素更新和退火接受准则的引导，为相关组合优化问题提供了参考。在应用价值上，该方法直接面向变电站巡检这一实际工业场景，所规划的路径有助于显著提升巡检机器人的工作效率和连续性，降低运维成本，对推动电力系统智能化巡检具有直接的工程意义。
本研究的亮点在于：第一，研究目标具有明确的工程针对性，聚焦于变电站半结构化环境下的多目标（距离与节点数）路径规划，问题定义清晰。第二，方法设计具有创新性，提出了“Dijkstra局部规划 + 模拟退火蚁群全局规划”的双层框架，并引入偏离度将双目标巧妙地转化为单目标进行优化。第三，算法改进有效，通过模拟退火机制增强了基本蚁群算法的全局搜索能力，避免了早熟收敛；通过偏离度指导的信息素更新策略，加速了算法收敛速度。第四，验证充分，不仅通过典型变电站模型验证了方法的可行性，还通过大规模算例对比实验证明了其相对于基准算法的性能优势。此外，研究对拓扑地图的采用、对问题分解（局部与全局）的思路，都具有较强的合理性和实用性。