朱濤　何健　彭智

【摘 要】地理信息系統(tǒng)（GIS）已廣泛應(yīng)用于各領(lǐng)域，尤其在電網(wǎng)運行中顯得更加重要。輸電線路的巡視工作是保障電網(wǎng)安全可靠運行的重要基礎(chǔ)工作，為提高巡視效率水平，需制定科學(xué)合理的巡視路徑導(dǎo)航，本文在GIS數(shù)據(jù)的基礎(chǔ)上，提出基于層次搜索模型應(yīng)用于輸電線路的路徑導(dǎo)航，提高了巡檢效率。

【關(guān)鍵詞】GIS；輸電線路；路徑導(dǎo)航

0 引言

輸電網(wǎng)絡(luò)是電力系統(tǒng)網(wǎng)絡(luò)中的重要組成部分，輸電線路和設(shè)備一直暴露在自然環(huán)境中，由于輸電線路及桿塔部件長期受到風(fēng)吹日曬、電閃雷擊以及機械張力等的影響，會產(chǎn)生銹蝕、磨損、自爆等損壞，這些問題如果不能及時發(fā)現(xiàn)并維修，將會給輸電線路穩(wěn)定運行帶來極大隱患。所以，需要定期巡檢輸電線路，隨時掌握線路保護(hù)區(qū)的環(huán)境變化情況，迅速發(fā)現(xiàn)并消除隱患，防止重大事故發(fā)生，確保供電的安全與可靠。由于輸電網(wǎng)絡(luò)的分布具有廣域的地理空間特性，傳統(tǒng)的技術(shù)無法實現(xiàn)對它進(jìn)行有效管理與維護(hù)。隨著信息技術(shù)的發(fā)展，利用先進(jìn)的地理信息系統(tǒng)（Geographic Information System-GIS）技術(shù)實現(xiàn)輸電線路巡視成為了可能。

GIS是一門綜合性學(xué)科，結(jié)合地理學(xué)與地圖學(xué)以及遙感和計算機科學(xué)，已經(jīng)廣泛的應(yīng)用在不同的領(lǐng)域，是用于輸入、存儲、查詢、分析和顯示地理數(shù)據(jù)的計算機系統(tǒng)，它可以對空間信息進(jìn)行分析和處理[1]，對地球上存在的現(xiàn)象和發(fā)生的事件進(jìn)行成圖和分析。GIS技術(shù)把地圖這種獨特的視覺化效果和地理分析功能與一般的數(shù)據(jù)庫操作，例如：查詢和統(tǒng)計分析等集成在一起。

路徑導(dǎo)航問題是GIS分析和導(dǎo)航實現(xiàn)中最基本的問題，它一直是計算機科學(xué)、運籌學(xué)、交通工程學(xué)、地理信息科學(xué)等學(xué)科領(lǐng)域的一個研究熱點[2]，也是資源分配、路線設(shè)計及分析等優(yōu)化問題的基礎(chǔ)。現(xiàn)在對路徑規(guī)劃的研究，已經(jīng)不僅僅是傳統(tǒng)意義上的距離最短研究，而是發(fā)展引申到了時間、費用、線路容量等方面。當(dāng)今路徑導(dǎo)航系統(tǒng)的研究構(gòu)成主要是日本、歐洲、美國三大體系。與國外相比，國內(nèi)的路徑導(dǎo)航方面的研究相對落后?，F(xiàn)階段關(guān)于路徑優(yōu)化的研究有很多，其目的主要是為了能夠快速找到最優(yōu)路徑。通常采用的算法包括：Dijkstra[3]、Krushkal[4]、A*算法[5]。這一類算法在網(wǎng)絡(luò)節(jié)點規(guī)模較多、路段較多等情況下，存在搜索節(jié)點多、時間耗費較大等缺陷。在已有的研究中，有關(guān)輸電網(wǎng)絡(luò)的巡視路徑設(shè)計優(yōu)化問題研究并不多，輸電線路巡視路徑規(guī)劃問題是一個新的研究應(yīng)用領(lǐng)域。由于影響輸電線路走向的因素很多，主要有技術(shù)、經(jīng)濟成本、施工維護(hù)、生態(tài)、電氣等因素，這些因素在實際中大都是相互矛盾的。目前，這些算法都只是僅僅給出到達(dá)目標(biāo)的路線，都普遍缺少智能特點，不能具體根據(jù)實際輸電的情況進(jìn)行計算和分析。鑒于輸電線路的巡檢特殊性，與一般的路徑導(dǎo)航問題的研究思路具有較大的不同，本文基于實際輸電線路網(wǎng)絡(luò)情況，以GIS導(dǎo)航數(shù)據(jù)為基礎(chǔ)，采用層次搜索方法，實現(xiàn)輸電線路巡檢路徑導(dǎo)航最優(yōu)選擇，使路徑導(dǎo)航更科學(xué)、更合理，從而提高巡檢效率。

1 層次搜索模型

層次搜索模型是在傳統(tǒng)Dijkstra模型的基礎(chǔ)上，采用雙重排序索引技術(shù)對算法進(jìn)行優(yōu)化，從而提高算法的速度，有效地解決計算一個節(jié)點到其他所有節(jié)點的最短路徑問題。

1.1 Dijkstra算法

算法的主要特點是以起始點為中心向外不斷擴展，一直擴展到終點為止。首先，按廣度優(yōu)先的方式進(jìn)行搜索，然后，依次求出源點到其它所有節(jié)點的最短距離，最終求出源點到終點的最短路徑。算法把起點到終點旳最短距離作為程序結(jié)束的條件，求出了以起始點為圓心，以起點到終點的最短距離為半徑，在這個半徑所形成的圓內(nèi)的所有節(jié)點和圓心之間的最短距離。但是這種算法，對于網(wǎng)絡(luò)空間分布廣泛而復(fù)雜的導(dǎo)航數(shù)據(jù)來說，計算效率很低。算法需要以多重循環(huán)的方式實現(xiàn)，循環(huán)過程中，而未經(jīng)過任何處理的計算數(shù)據(jù)是雜亂無序存放的，如果直接將數(shù)據(jù)進(jìn)行計算，每次循環(huán)中都需重復(fù)進(jìn)行遍歷，計算所有已標(biāo)識節(jié)點到所有未標(biāo)識節(jié)點的距離，以求出最小的距離。當(dāng)節(jié)點數(shù)逐漸增加時，這個過程將會變得越來越慢，嚴(yán)重影響計算速度和效率。為了改善這種情況，提高算法的速度，本文釆用了層次搜索模型對算法進(jìn)行優(yōu)化。

1.2 層次搜索算法

1.2.1 建立節(jié)點數(shù)據(jù)的排序索引拓?fù)浣Y(jié)構(gòu)

通常，在GIS和導(dǎo)航數(shù)據(jù)中，用一對“起點”和“終點”節(jié)點對表示一條路段，從而建立起了節(jié)點和路段數(shù)據(jù)之間的拓?fù)潢P(guān)系。所有節(jié)點和路段數(shù)據(jù)初始狀態(tài)下都是無序的，如果以無序數(shù)據(jù)為基礎(chǔ)進(jìn)行最短路徑計算，計算過程中每次通過一個節(jié)點查找路段時，都會花很多的時間到路段集中去查找，大大降低其算法的效率。建立節(jié)點和路段之間的數(shù)據(jù)索引可以有效地提高算法效率，其基本思想是節(jié)點按照序號排序，路段按照起點排序，在節(jié)點排序表中，記錄下以該節(jié)點為起點路段的地址形成節(jié)點索引表。

1.2.2 已標(biāo)識節(jié)點到未標(biāo)識節(jié)點距離升序排序

在最短路徑計算的過程中，每次需要計算所有已標(biāo)記節(jié)點到所有未標(biāo)記節(jié)點的最短路徑，由于路徑距離沒有經(jīng)過排序處理，只能按序查找，計算效率低，特別是一旦數(shù)據(jù)量增加，檢索速度會急劇下降。為了提高計算速度，節(jié)省時間，本文對所有已標(biāo)識節(jié)點到所有未標(biāo)識節(jié)點的距離采取按升序排序的方法處理，在計算過程中，不需要每次都重新計算所有已標(biāo)識節(jié)點到所有未標(biāo)識節(jié)點的距離，只需要移除本次被標(biāo)識節(jié)點相關(guān)的距離。同時，按序加入被標(biāo)識的節(jié)點到其他未標(biāo)識節(jié)點的距離，大量減少了每次被標(biāo)識節(jié)點以外的其他節(jié)點的路徑計算。采用這種方法在計算最短路徑時，取出排在最前面的距離，完全不需要再計算其他標(biāo)識和未標(biāo)識節(jié)點間的距離，大大提高了算法效率。

1.2.3 實現(xiàn)過程

算法實現(xiàn)過程主要經(jīng)歷下面4步：

（1）預(yù)處理

預(yù)處理內(nèi)容主要包括標(biāo)識起點為已標(biāo)識節(jié)點，其最短路徑為0；起點以外的每個節(jié)點作為未標(biāo)識節(jié)點，并假設(shè)最短路徑初值為無窮大。

（2）計算最短距離的節(jié)點

將所有未標(biāo)識節(jié)點到已標(biāo)識節(jié)點的排序距離中取出第一條記錄，即最短距離，將其中未標(biāo)識的端點標(biāo)識為己標(biāo)識節(jié)點，移除這個節(jié)點相關(guān)的距離，同時，按升序加入這個被標(biāo)識的節(jié)點到其他未標(biāo)識節(jié)點的距離。

（3）判斷禁止節(jié)點

如果節(jié)點中有禁止連接的節(jié)點，修改起點到該節(jié)點的最短距離值。

（4）迭代處理

重復(fù)第2、3步計算，即可求得從起點到其他各點的最短路徑。

1.3 層次搜索算法在GIS中的應(yīng)用

在GIS實際應(yīng)用中，需要計算最短距離的兩節(jié)點通常是用戶指定的兩個輸電線路最感興趣點或地標(biāo)點，一般來說這些節(jié)點都不在具體某條路段的端點處，在計算過程中則需要利用算法尋找計算起始點和終止點最短距離的路段，然后路段起止點進(jìn)行最短路徑計算。具體的過程如下：

（1）計算起始點和終止點間的最短路段

算法基本思想是，以起始點或者終止點為圓心，采用擴大和縮小半徑方法，通過圓覆蓋的方式進(jìn)行遞歸查找有交點的路段，直到查找到符合要求的路段，然后查找到的路段中，利用點到直線的距離公式，求起始點或者終止點到這些路段的距離，距離最小的路段即為所需要路段。

（2）確定路段端點

距離起始點或終止點最近的路段確定以后，需要確定使用路段的哪個端點作為最短路徑。對于起始點，使用距離最近路段的終點作為計算最短路徑的起點；而對于終止點，使用距離最近路段的起點作為計算最短路徑的終點。

（3）計算兩端點間總距離

首先，在計算起始點到離其最近路段的距離之后，計算起始點到最近路段終點的距離；然后，計算起始點最近路段的終點到終點最近路段起點之間的最短距離之后，計算出終點端最短路段的起點到起點最近路段的終點之間的最短距離；最后，計算出最短路段起點和終點間的距離。

2 輸電線路巡視路徑導(dǎo)航設(shè)計

2.1 GIS數(shù)據(jù)預(yù)處理

由于輸電網(wǎng)絡(luò)空間分布復(fù)雜，在進(jìn)行輸電線路數(shù)據(jù)采集時，經(jīng)常會碰到一個點分出多條線，多條線有著不同的走向，其中每條線又隨時會分出多條線繼續(xù)向下發(fā)展的情況。所以，通過采集的GIS數(shù)據(jù)是無法直接被利用進(jìn)行路徑選擇和導(dǎo)航。這些數(shù)據(jù)在路徑導(dǎo)航計算之前必須進(jìn)行整理、優(yōu)化、歸類和排序等步驟的預(yù)處理，預(yù)處理后的數(shù)據(jù)進(jìn)集成，作為路徑導(dǎo)航需要的節(jié)點和路段數(shù)據(jù)。

2.2 路徑規(guī)劃

路徑規(guī)劃采用本文提出的層次搜索模型，根據(jù)用戶輸入的各個節(jié)點位置，提供節(jié)點間的最優(yōu)距離。該功能模塊在導(dǎo)航系統(tǒng)中主要由數(shù)據(jù)顯示模塊和數(shù)據(jù)解碼模塊組成。用戶通過人機界面引導(dǎo)用戶在數(shù)字地圖上找到需要規(guī)劃的路徑位置，輸入導(dǎo)航路徑的各個點位數(shù)據(jù)，并將規(guī)劃完成的導(dǎo)航路徑存入路徑數(shù)據(jù)庫中。數(shù)據(jù)顯示模塊，主要負(fù)責(zé)根據(jù)系統(tǒng)的參數(shù)配置將用戶規(guī)劃的導(dǎo)航路徑以可視化的方式顯示出來；數(shù)據(jù)解碼模塊，主要負(fù)責(zé)將接收到的遠(yuǎn)程傳送的編碼數(shù)據(jù)恢復(fù)為導(dǎo)航路徑數(shù)據(jù)。用戶可以通過終端在系統(tǒng)界面上完成手動路徑的繪制和規(guī)劃。

2.3 實時導(dǎo)航

在路徑優(yōu)化模塊的基礎(chǔ)上進(jìn)行實時導(dǎo)航。實時導(dǎo)航功能模塊主要由軌跡記錄模塊、數(shù)據(jù)顯示模塊和偏航報警模塊組成。其中，軌跡記錄模塊，負(fù)責(zé)實時接收當(dāng)前位置信息，并記錄和保存歷史軌跡信息；數(shù)據(jù)顯示模塊，負(fù)責(zé)將當(dāng)前位置信息和歷史軌跡信息按照系統(tǒng)參數(shù)設(shè)定，并可視化顯示；偏航報警模塊，負(fù)責(zé)計算當(dāng)前位置與導(dǎo)航路徑的偏移量，當(dāng)偏移量大于系統(tǒng)設(shè)定的最大閥值時向用戶報警。用戶輸入輸出操作將通過人機界面交互完成。

以層次搜索模型為基礎(chǔ)的路徑導(dǎo)航應(yīng)用系統(tǒng)，為巡檢工作人員提供可視化的巡檢路線導(dǎo)航，在很短的時間內(nèi)為巡檢工作人員提供最優(yōu)的巡檢路線，路徑導(dǎo)航界面如圖1所示。

3 結(jié)束語

基于GIS的路徑導(dǎo)航在輸電線路巡視中起著非常重要的作用，也是今后一個主要的發(fā)展和研究方向。本文從這樣的實際需求出發(fā)，以實際GIS數(shù)據(jù)為基礎(chǔ)，提出基于層次搜索模型應(yīng)用于輸電線路的路徑導(dǎo)航，提高了路徑規(guī)劃的速度，從而進(jìn)一步提高了巡檢工作效率。

【參考文獻(xiàn)】

[1]宋斌.基于地理信息系統(tǒng)技術(shù)的電力線路巡檢系統(tǒng)的設(shè)計與實現(xiàn)[D].成都：電子科技大學(xué)，2011.

[2]崔鐵軍.地理信息服務(wù)導(dǎo)論[M].科學(xué)出版社，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]王海梅，周獻(xiàn)中.直線優(yōu)化A*算法在最短路徑問題中的改進(jìn)與實現(xiàn)[J].工程圖學(xué)學(xué)報，2009，6（3）：121-126.

[責(zé)任編輯：王楠]