朱涛　何健　彭智

【摘 要】地理信息系统（GIS）已广泛应用于各领域，尤其在电网运行中显得更加重要。输电线路的巡视工作是保障电网安全可靠运行的重要基础工作，为提高巡视效率水平，需制定科学合理的巡视路径导航，本文在GIS数据的基础上，提出基于层次搜索模型应用于输电线路的路径导航，提高了巡检效率。

【关键词】GIS；输电线路；路径导航

0 引言

输电网络是电力系统网络中的重要组成部分，输电线路和设备一直暴露在自然环境中，由于输电线路及杆塔部件长期受到风吹日晒、电闪雷击以及机械张力等的影响，会产生锈蚀、磨损、自爆等损坏，这些问题如果不能及时发现并维修，将会给输电线路稳定运行带来极大隐患。所以，需要定期巡检输电线路，随时掌握线路保护区的环境变化情况，迅速发现并消除隐患，防止重大事故发生，确保供电的安全与可靠。由于输电网络的分布具有广域的地理空间特性，传统的技术无法实现对它进行有效管理与维护。随着信息技术的发展，利用先进的地理信息系统（Geographic Information System-GIS）技术实现输电线路巡视成为了可能。

GIS是一门综合性学科，结合地理学与地图学以及遥感和计算机科学，已经广泛的应用在不同的领域，是用于输入、存储、查询、分析和显示地理数据的计算机系统，它可以对空间信息进行分析和处理[1]，对地球上存在的现象和发生的事件进行成图和分析。GIS技术把地图这种独特的视觉化效果和地理分析功能与一般的数据库操作，例如：查询和统计分析等集成在一起。

路径导航问题是GIS分析和导航实现中最基本的问题，它一直是计算机科学、运筹学、交通工程学、地理信息科学等学科领域的一个研究热点[2]，也是资源分配、路线设计及分析等优化问题的基础。现在对路径规划的研究，已经不仅仅是传统意义上的距离最短研究，而是发展引申到了时间、费用、线路容量等方面。当今路径导航系统的研究构成主要是日本、欧洲、美国三大体系。与国外相比，国内的路径导航方面的研究相对落后。现阶段关于路径优化的研究有很多，其目的主要是为了能够快速找到最优路径。通常采用的算法包括：Dijkstra[3]、Krushkal[4]、A*算法[5]。这一类算法在网络节点规模较多、路段较多等情况下，存在搜索节点多、时间耗费较大等缺陷。在已有的研究中，有关输电网络的巡视路径设计优化问题研究并不多，输电线路巡视路径规划问题是一个新的研究应用领域。由于影响输电线路走向的因素很多，主要有技术、经济成本、施工维护、生态、电气等因素，这些因素在实际中大都是相互矛盾的。目前，这些算法都只是仅仅给出到达目标的路线，都普遍缺少智能特点，不能具体根据实际输电的情况进行计算和分析。鉴于输电线路的巡检特殊性，与一般的路径导航问题的研究思路具有较大的不同，本文基于实际输电线路网络情况，以GIS导航数据为基础，采用层次搜索方法，实现输电线路巡检路径导航最优选择，使路径导航更科学、更合理，从而提高巡检效率。

1 层次搜索模型

层次搜索模型是在传统Dijkstra模型的基础上，采用双重排序索引技术对算法进行优化，从而提高算法的速度，有效地解决计算一个节点到其他所有节点的最短路径问题。

1.1 Dijkstra算法

算法的主要特点是以起始点为中心向外不断扩展，一直扩展到终点为止。首先，按广度优先的方式进行搜索，然后，依次求出源点到其它所有节点的最短距离，最终求出源点到终点的最短路径。算法把起点到终点旳最短距离作为程序结束的条件，求出了以起始点为圆心，以起点到终点的最短距离为半径，在这个半径所形成的圆内的所有节点和圆心之间的最短距离。但是这种算法，对于网络空间分布广泛而复杂的导航数据来说，计算效率很低。算法需要以多重循环的方式实现，循环过程中，而未经过任何处理的计算数据是杂乱无序存放的，如果直接将数据进行计算，每次循环中都需重复进行遍历，计算所有已标识节点到所有未标识节点的距离，以求出最小的距离。当节点数逐渐增加时，这个过程将会变得越来越慢，严重影响计算速度和效率。为了改善这种情况，提高算法的速度，本文釆用了层次搜索模型对算法进行优化。

1.2 层次搜索算法

1.2.1 建立节点数据的排序索引拓扑结构

通常，在GIS和导航数据中，用一对“起点”和“终点”节点对表示一条路段，从而建立起了节点和路段数据之间的拓扑关系。所有节点和路段数据初始状态下都是无序的，如果以无序数据为基础进行最短路径计算，计算过程中每次通过一个节点查找路段时，都会花很多的时间到路段集中去查找，大大降低其算法的效率。建立节点和路段之间的数据索引可以有效地提高算法效率，其基本思想是节点按照序号排序，路段按照起点排序，在节点排序表中，记录下以该节点为起点路段的地址形成节点索引表。

1.2.2 已标识节点到未标识节点距离升序排序

在最短路径计算的过程中，每次需要计算所有已标记节点到所有未标记节点的最短路径，由于路径距离没有经过排序处理，只能按序查找，计算效率低，特别是一旦数据量增加，检索速度会急剧下降。为了提高计算速度，节省时间，本文对所有已标识节点到所有未标识节点的距离采取按升序排序的方法处理，在计算过程中，不需要每次都重新计算所有已标识节点到所有未标识节点的距离，只需要移除本次被标识节点相关的距离。同时，按序加入被标识的节点到其他未标识节点的距离，大量减少了每次被标识节点以外的其他节点的路径计算。采用这种方法在计算最短路径时，取出排在最前面的距离，完全不需要再计算其他标识和未标识节点间的距离，大大提高了算法效率。

1.2.3 实现过程

算法实现过程主要经历下面4步：

（1）预处理

预处理内容主要包括标识起点为已标识节点，其最短路径为0；起点以外的每个节点作为未标识节点，并假设最短路径初值为无穷大。

（2）计算最短距离的节点

将所有未标识节点到已标识节点的排序距离中取出第一条记录，即最短距离，将其中未标识的端点标识为己标识节点，移除这个节点相关的距离，同时，按升序加入这个被标识的节点到其他未标识节点的距离。

（3）判断禁止节点

如果节点中有禁止连接的节点，修改起点到该节点的最短距离值。

（4）迭代处理

重复第2、3步计算，即可求得从起点到其他各点的最短路径。

1.3 层次搜索算法在GIS中的应用

在GIS实际应用中，需要计算最短距离的两节点通常是用户指定的两个输电线路最感兴趣点或地标点，一般来说这些节点都不在具体某条路段的端点处，在计算过程中则需要利用算法寻找计算起始点和终止点最短距离的路段，然后路段起止点进行最短路径计算。具体的过程如下：

（1）计算起始点和终止点间的最短路段

算法基本思想是，以起始点或者终止点为圆心，采用扩大和缩小半径方法，通过圆覆盖的方式进行递归查找有交点的路段，直到查找到符合要求的路段，然后查找到的路段中，利用点到直线的距离公式，求起始点或者终止点到这些路段的距离，距离最小的路段即为所需要路段。

（2）确定路段端点

距离起始点或终止点最近的路段确定以后，需要确定使用路段的哪个端点作为最短路径。对于起始点，使用距离最近路段的终点作为计算最短路径的起点；而对于终止点，使用距离最近路段的起点作为计算最短路径的终点。

（3）计算两端点间总距离

首先，在计算起始点到离其最近路段的距离之后，计算起始点到最近路段终点的距离；然后，计算起始点最近路段的终点到终点最近路段起点之间的最短距离之后，计算出终点端最短路段的起点到起点最近路段的终点之间的最短距离；最后，计算出最短路段起点和终点间的距离。

2 输电线路巡视路径导航设计

2.1 GIS数据预处理

由于输电网络空间分布复杂，在进行输电线路数据采集时，经常会碰到一个点分出多条线，多条线有着不同的走向，其中每条线又随时会分出多条线继续向下发展的情况。所以，通过采集的GIS数据是无法直接被利用进行路径选择和导航。这些数据在路径导航计算之前必须进行整理、优化、归类和排序等步骤的预处理，预处理后的数据进集成，作为路径导航需要的节点和路段数据。

2.2 路径规划

路径规划采用本文提出的层次搜索模型，根据用户输入的各个节点位置，提供节点间的最优距离。该功能模块在导航系统中主要由数据显示模块和数据解码模块组成。用户通过人机界面引导用户在数字地图上找到需要规划的路径位置，输入导航路径的各个点位数据，并将规划完成的导航路径存入路径数据库中。数据显示模块，主要负责根据系统的参数配置将用户规划的导航路径以可视化的方式显示出来；数据解码模块，主要负责将接收到的远程传送的编码数据恢复为导航路径数据。用户可以通过终端在系统界面上完成手动路径的绘制和规划。

2.3 实时导航

在路径优化模块的基础上进行实时导航。实时导航功能模块主要由轨迹记录模块、数据显示模块和偏航报警模块组成。其中，轨迹记录模块，负责实时接收当前位置信息，并记录和保存历史轨迹信息；数据显示模块，负责将当前位置信息和历史轨迹信息按照系统参数设定，并可视化显示；偏航报警模块，负责计算当前位置与导航路径的偏移量，当偏移量大于系统设定的最大阀值时向用户报警。用户输入输出操作将通过人机界面交互完成。

以层次搜索模型为基础的路径导航应用系统，为巡检工作人员提供可视化的巡检路线导航，在很短的时间内为巡检工作人员提供最优的巡检路线，路径导航界面如图1所示。

3 结束语

基于GIS的路径导航在输电线路巡视中起着非常重要的作用，也是今后一个主要的发展和研究方向。本文从这样的实际需求出发，以实际GIS数据为基础，提出基于层次搜索模型应用于输电线路的路径导航，提高了路径规划的速度，从而进一步提高了巡检工作效率。

【参考文献】

[1]宋斌.基于地理信息系统技术的电力线路巡检系统的设计与实现[D].成都：电子科技大学，2011.

[2]崔铁军.地理信息服务导论[M].科学出版社，2008.

[3]Fan D K，Shi P. Improvement of Dijkstras Algorithm and Its Application in Route Planning[C].In the Proceedings of the Seventh International Conferecne on Fuzzy Systems and Knowledge Discovery， 2010，4（2）：1901-1904.

[4]Shashikiran V，Kumar T T S，Kumar N S，et al. Dynamic Road Traffic Management Based on Krushkals Algorithm[C].In the Proceedings of the forth IEEE International Conference on Recent Trends in Information Technology， 2011：200-204.

[5]王海梅，周献中.直线优化A*算法在最短路径问题中的改进与实现[J].工程图学学报，2009，6（3）：121-126.

[责任编辑：王楠]