基于GIS的輸電線路巡視路徑導航研究

朱濤　何健　彭智

【摘 要】地理信息系統（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.

[責任編輯：王楠]