基于枚举法的变电站巡检机器人巡视路线优化
2021-02-24张永涛于倩倩肖智彬孙秋芹徐雯俐
张永涛，于倩倩，肖智彬，孙秋芹，张 轲，徐雯俐
（1.国网河南省电力公司周口供电公司，河南 周口 466000；2.国网湖南省电力有限公司检修公司，长沙 410004；3.湖南大学 电气与信息工程学院，长沙 410082；4.国网山西省电力公司晋城供电公司，山西 晋城 048000）
0 引言
变电站设备分布较广，且数量众多，在高温、大负荷运行和新设备投入运行前以及大风、雾天、冰雪、冰雹、雷雨后，巡视任务尤其繁重，适宜采用巡检机器人代替运维人员对设备进行巡检[1-2]。变电站巡检机器人除了用于日常巡视外，还可以实现远方状态识别、远方异常确认、缺陷定点跟踪等一系列功能[3]。巡检机器人的使用不仅有利于提高运维人员的效率和质量，还可以降低运维人员的劳动强度和工作风险[4]，有效保障设备安全可靠运行[5-6]。机器人巡检是智能和无人值守巡检技术的发展方向，具有广阔的发展空间和应用前景[7-8]。
目前，变电站巡检机器人的巡视路线通常是在确定机器人生产厂家后，由工作人员根据实际情况进行规划[9]。生产厂家主要考虑的是巡检道路的修建成本以及目前变电站的可利用空间，通常未考虑最佳巡视路线的规划问题[10]。
合理的路径规划不但要求其能够遍历所有巡检点，还需要满足最短路径和最短作业时间。变电站巡检机器人巡视路线优化问题与图论中“中国邮递员问题”相似，该问题的求解分为构造欧拉图和求解欧拉回路两部分。连通图中，节点所连接边的个数称为该节点的度。构造欧拉图就是解决变电站巡检路线拓扑结构图中度为奇数节点的配对问题。
构造欧拉图的方法主要有求最小生成树的算法、奇偶点图上作业法以及最小权完美匹配算法。通过构造最小生成树解决节点的配对问题，其方法主要有如下2 类[11-12]：
（1）在连通图的奇点处作出标记，使用避圈法或破圈法求连通图的最小生成树，将与奇点相连的边尽可能多地保留下来，在奇点处添加重复边，完成奇度节点的配对。
（2）去掉连通图中度为偶数的节点，使用避圈法或破圈法求剩余节点的最小生成树，可以得到奇度节点的配对方案。
上述方案中最小生成树的总权数最小，但节点配对需要的只是该最小生成树的一部分，不能保证取出的几段权数之和最小[12]。
奇偶点图上作业法则通过选择距离最近的两奇度数节点进行配对，重复上述步骤对剩余节点进行配对[13]，或去掉已配对节点的关联边后，对剩余节点进行配对[14]，但配对完成后还需要采用判优准则进行验证，以调整配对方案。奇偶点图上作业法通俗易懂，当拓扑图较复杂时，计算量也很大。
最小权完美匹配算法对待配对节点的数量没有要求，计算速度快，但应用于巡检机器人巡视路线优化问题，对节点进行配对优化时会出现节点重复配对的现象，准确度不高[11，15]。从研究现状来看，巡检路线图中奇度节点的配对优化方法仍待进一步研究。
本文根据变电站巡检机器人巡视路线图中节点配对问题的特点，将枚举法应用于巡视路线优化，具有优化速度快，准确率高等优点，最后将枚举法推广到多巡检区域奇度节点配对。
1 模型建立
某220 kV 变电站巡检路线如图1 所示，为研究方便，将巡检道路划分为主干道和支路；为了提高算法的优化效果，对原巡检道路进行补充，以形成更多的回路。
图1 某220 kV 变电站巡视路线
