基于邮递员问题的变电站巡视路线探究

彭光超

(南方电网深圳供电局有限公司，深圳，518000)

0 引言

目前，我国变电站巡视工作是由变电运行人员完成，主要记录在变电站巡视记录本或PDA 等电子设备中，而巡视路线往往依靠工作经验来制定。随着电网规模的日益壮大，按照以往的经验制定设备巡视路线往往会造成多走回头路的现象，造成资源浪费。因此，对变电站设备巡视路线制定进行新的研究显得十分重要。目前我国变电运行巡视工作存在的问题主要有以下几点：（1）运行人员缺少必要的知识储备和衡量标准。我国变电站发展虽然比较迅速，但是相关的教育程度还不达标，尤其是早期的变电站工作人员，其知识水平参差不齐，同时缺少统一的巡视检查标准。（2）巡视人员责任心不同。因为变电站的占地面积大，需要巡视的设备种类繁多而且数量众多，再加上巡视人员的责任心不同，因此，实际工作中常会出现工作人员没有到位、错检、漏检等现象。（3）巡视的路径规划方法不科学。由于近年来国民经济的飞速增长，供电企业人员增长与电力系统的发展之间的矛盾日益突出；目前变电站巡视人员制定巡视路线都是凭借工作经验，没有科学有效的判定依据，导致有些巡视路线不是最佳巡视路线。（4）巡视周期内重复性缺陷数量大。在某些地区，电力设备更新换代较慢。设备经过长期运行后使用寿命大大降低，设备缺陷率较高，且多为重复缺陷。

1 路径规划简介

路径规划技术被广泛应用于许多领域。在高科技领域的应用是：移动机器人技术；无人机规避障碍物飞行；防反弹攻击等。在日常生活领域的应用主要有：以GIS 为指导的道路设计；车载GPS 系统中的路径选择；导游软件中路线选择；变电站或其他需要巡视作业的部门进行路径规划等。在管理决策领域的应用有：最短路、最大流问题，物流管理中的车辆路径问题(Vehicle Routing Problems)。在通信技术中的应用有信号塔选址、网络拓扑路线、路由等问题。

从环境信息性质不同的角度来说，可以将路径规划分成两种：一种是全局规划，它的基础是先验完整信息；另一种局部规划，它侧重传感器实时感知的信息。动态路径规划一般按照以下三个步骤进行：1)环境建模。把已知的环境信息抽象后建立数学模型。环境模型建立好以后，计算机才能进行路径规划计算。通俗地说，就是将实际存在的物理空间抽象成数字信息，以使计算机可以进行处理。2)路径搜索。路径搜索依据优化条件，应用路径规划的算法在所有路径中寻找并产生一条最优路径。3)路径平滑。通过环境建模、路径搜索后得到的路径仅是理论上的可行方案，在应用中需要考虑实际情况，再经过处理、平滑等“深加工”，最后得出可行的路径。但是在离散域的路径规划问题中是可以省略路径平滑这一步骤的，前提是在环境建模和路径搜索前已经进行了了很好的路径可行性分析。

路径规划的方法非常的多，不同的方法其优缺点也不相同，不同的优缺点也决定了各种方法的适用范围。目前国际上通用的分类方法是从各种算法被发现的先后顺序以及算法的基本原理来分类，按照此原则当前常用于各领域的路径规划算法分四种即传统算法、图形学方法、智能仿生学算法和其他算法。

2 邮递员问题及奇偶点作业法

变电站巡视路线类似于图论中的邮递员问题，某邮递员出发送信，要从邮局出发，而且至少通过一次辖区内的每一条街道，最后要回到出发的邮局，以这些条件为前提，邮递员要怎样选择路线，才能保证走得路线最短？巡视人员工作时同样是在一片区域内行走，这就需要在众多路线中寻找最优路线，在保证工作质量的同时寻求耗时最短的路线。邮递员问题的求解方法是Fleury算法，将行走区域看成一个Euler 图，求其Euler 环游；若该图不是Euler 图，则通过某些方法使其变换成Euler 图进行求解；下面就应用管梅谷教授的奇偶点作业法简要介绍求解过程。

使用奇偶点作业法是以下述定理为基础的。

定理 设C 是一条经过赋权连通图G 的每条边至少一次的回路，则C 是G 的最优回路。当且仅当C 对应的Euler 图满足：

奇偶点作业法基本步骤：

1)按照一个方案找到图中所有奇顶点（必为偶数个），然后进行两两配对直至得到的新图中，没有了奇顶点。

2)按照1 中的方法重复计算，直到得到的图中重复边总长度变短。

3)根据定理中的条件（2）反复执行步骤2。

3 实例验证

3.1 变电站实例

图1 某变电站站内设备平面图

某变电站有500kV、220kV、35kV 三个电压等级，。500kV 变压器有3 台，500kV 输电线路有4 回， 220kV 输电线路有10 回，占地面积35000 平方米；其站内设备平面图如图1 所示。

3.2 变电站平面图形

根据图论理论，设每个区域内RFID 标签为图G 中的顶点，记为 V (G ) ，其中 v1=主控室定位点，v2=500kV 设备区域定位点，v3=#5 主变区域定位点，v4=35kV5M 区域定位点，v5=220kV 设备区域定位点，v6=#4 主变区域定位点，v7=#3 主变区域定位点，v8=35kV3M 区域定位点，v9=35kV4M 区域定位点，v10=站用电区域定位点。各设备区域间的道路记为图G 中的边，记为 E ( G )，即根据查阅图纸资料，确定图G 的每一条边的权数(单位：米)如下：w12= 9，w23= 11，w34= 8，w45= 26，w59= 17，w69=10,w26=8,w25=19,w35=28,w13=14,w27=18,w7,10=22,w78=10,w89=9,w1,10=7。这样就将变电站的平面图抽象为无向图G ，如图2。

图2

图3

根据奇偶点作业法，首先判断图G 是否为Euler 图。图G中，顶点 v1, v2, v7,v9是奇度点。所以图G 非欧拉图。此时求解欧拉回路需要添加重复边。给 v1,v2的一条链增加一条重复边；给 v7,v9的一条链 v7, v8,v9，每条边增加一条重复边，且使得增加的重复边权数和最小。由此得到图3，此时图3 中无奇点，图3已是欧拉图。

3.3 检验过程

对图3 进行检验，计算已添加重复边的每个圈的权数和与每个圈所含重复边的权数和。如表1 所示。

表1 图3 的检验表

从表1 可以看出，所有含有重复边的圈所含重复边的权数和都没有超过本圈的权数和的一半。所以该方案是最优方案。

3.4 求解过程

3.5 对比分析

通过上面的分析可以得出新的巡视路线，为了评价新制定的巡视路线的优劣性，我们进行了两次巡视。一次按照以往制定好的巡视路线Line1 进行巡视，一次按照新制定的巡视路线Line2进行巡视，将两次巡视中人员走动的距离，消耗时间进行对比，对比结果如表2 所示。

表2 结果对比表

从表2 中可以看出，按照新的巡视路线Line2 进行巡视，可缩短走动距离87 米，节约时间33 分钟。按照两人巡视，一天一次巡视来计算，共可节约时间60 分钟；在某些特殊情况下，譬如事故状态，特殊保供电等情况下，变电站的巡视次数会大为增加，由此带来的时间节约效果更加明显。按照此方法制定的巡视路线会进一步提高人员的工作效率，也有利于缓解生产一线人员的工作压力。

4 结语

本文通过分析我国变电站的巡视工作现状，总结其存在的问题；简要介绍了邮递员问题及奇偶点作业法。最后以某变电站为实例，对其巡视路线进行研究，验证了邮递员问题在变电站巡视路线规划问题中的应用，且节约效果明显。本文通过应用管理科学、图形学等学科知识，寻求变电站巡视最佳路线，希望对电力企业实现巡视工作的高质量和高效率有所帮助。

[1] 周俊，变电设备状态检修策略及应用研究[D]，保定，华北电力大学，2006.

[2] Edmonds J，Johonson E L.Matching，Euler tour and the Chinese postman[J].Mathematical Programming，1973,5:88-124.

[3] 管梅谷，奇偶点图上作业法[J]，数学学报，1960，10（3）：263-266.

[4] 李仪光，何斌斌，罗杰等，深圳供电局输变电设备状态巡视策略的研究[J]，机电工程技术，2011,40(6)，71-73.

[5] 贺鹏，殷亚君，最短路径算法浅析[J]，甘肃科技，2010(1)：42—43.

[6] 王兴亮，变电站设备状态巡视模式探讨[J]，中国高新技术企业，2011,24：92-98