基于分層模型的輸電線路選線算法設計

康健民，袁敬中，肖少輝，趙俊生，劉震

(1.華北電網有限公司，北京市，100053;2.北京洛斯達科技發展有限公司，北京市，100120;3.武漢大學，武漢市，430072)

0 引言

輸電線路的路徑選擇是電網建設的前提，其設計的合理性影響著線路投資運行成本的大小與運行的可靠性。輸電線路的選擇要求選線人員要綜合考慮地形、地貌、地質、交通、環境以及各地、各部門的政策法規等多方面的因素。為了降低選線的難度，減輕選線人員的工作量，節省選線的時間及成本，利用計算機來選擇輸電線路成為電力設計人員和相關研究學者關注的目標。

國外在20世紀90年代就開始了這方面的研究，文獻［1］使用衛星影像來確定影像因素，并賦予一定權重，選出一條代價最小的路徑;文獻［2］研究了城區里輸電線路的自動選線方法;文獻［3-4］將地理信息系統中柵格結構的思想引入輸電線路的線路規劃中，選擇輸電線路;文獻［5-7］也在柵格數據的基礎上進行了選線的研究;文獻［8］提出了SPI方法以解決公共參與對線路選擇的不良影響;文獻［9］利用空間建模方法通過人工干預得到初選路徑，以此確定合理的布線走廊。然而，上述方法都是將所有數據、影響因子放在1個層次中考慮，沒有注意到由于不同區域的地形復雜度、地物不同，其影響因子也不同，這樣既影響選線的準確性，也會降低選線的速度。

基于以上問題，華北電網有限公司根據多年選線經驗，組織各方面專家討論研究，將人工選線過程中先粗選后細選的思想和動態導航中分層搜索的思想［10］運用到選線算法中，提出由粗到細、分層次、逐級運算的算法，同時在數據組織方面采用了將地理數據以柵格格網表示的思想，進行計算機智能選線研究。經過試驗分析表明，采用該算法不僅選擇的線路符合要求，而且其選線速度快于其他方法。

1 數據模型設計與影響因子分析

1.1 數據模型設計

由于矢量數據結構不能很好地表示地形信息(坡度、限制區等)［3］，因此在電力選線中大都采用柵格數據模型［3-9］。柵格數據模型是由多個規則的網格單元組成，將要進行選線的區域按一定規則進行劃分，形成相互連接的規則多邊形，每個多邊形稱為網格單元，每個網格單元都存儲經過此單元所花費的成本。可以對選線區域進行多種格網等級的劃分，網格單元越小，選出的路徑越具體，但花費的時間越多;從較大的網格單元中選出一條路徑花費的時間較少，但很多影響因子無法得到合理利用，所選路徑較為粗略、準確性差，無法應用到實際當中。

目前的柵格數據模型都是在1個尺度的網格單元上進行選線，無法兼顧選線時間長短和線路的準確性問題。為了解決這個問題，本文設計了多層次的數據模型，不同層次存放不同大小的格網單元。這樣在線路選擇時就能先在格網單元較大的層選出一條粗略路徑，然后在包括該粗略路徑覆蓋范圍的下一層內選出一條較細的路徑，直至選到最小的格網單元層，如圖1所示，圖1中包含斜線的網格為路徑經過的網格單元。

圖1 柵格數據模型及選線Fig.1 Raster data model and route selection

1.2 影響因子分析

輸電線路經過的地域范圍較廣，會遇到多種地形地貌，比如山地、不良地質帶、公路、河流、居民地、自然保護區等。如何劃分這些因素，并將這些因素量化為計算機能夠識別的形式是進行選線的前提。本文將影響因素分為以下4類:

(1)社會因素。社會因素主要包括禁止通過區和協商通過區。禁止通過區是指輸電線路不能穿過的區域，包括軍事區、大型工礦企業、易燃易爆物品聚集處、自然保護區的核心區等。該區域的成本值記為M=∞。協商通過區是指一些應盡量避免但卻無法避免穿過的區域，通過這種區域一般需要較高的成本，包括居民地、不良地質帶和露天礦場、重冰區、河流湖泊等，通過該區域的成本值記為C。

(2)自然因素。自然因素主要考慮地形方面對選線的影響，包括坡度和高程2個方面。坡度所造成的成本值記為S，高程造成的成本值記為H。

(3)經濟因素。在選取2地輸電線路時，應在考慮到其他因素的情況下保證線路最短，2個網格之間的距離成本記為D(g1，g2)。輸電線路的轉角塔的成本都比較高，線路應盡量避免方向的改變，轉角成本記為 D(g0，g1，g2)。

(4)交通因素。為方便施工及維護，所選線路應盡量靠近交通設施。由于高速公路及鐵路作為主干路，為避免電線對其造成影響，當交叉時以接近90°為宜;一般公路可以不考慮交叉角。運輸成本記為T。

2 算法設計

基于人工選線中的流程和動態導航中為解決運算時間所采取的方法，本文提出一種基于分層模型的輸電線路選線算法。該算法考慮了3個層次L1、L2、L3，3個層次的網格單元大小遞減:G(L1)＞G(L2)＞G(L3)。該算法在不同的層次考慮了不同的影響因子，具體過程為:調用第1個層次的網格和各影響因子對應的數據進行疊加分析，生成成本格網，然后調用最短路徑算法選出通道，在通道的覆蓋區域調用下一層次格網，直至選出一條優化路徑。在相同的層次，不同的影響因子對選線的影響不同，要賦予相應的成本。在不同的層次，相同的影響因子對選線的作用也可能不同，因此也需要根據層次的不同改變該影響因子的成本。

在對成本格網進行運算時，網格gk－1和到相鄰格gk的成本值稱為可達性成本值，用F(gk－1，gk)表示。由于不同的層次考慮的影響因子不同，可達性成本值在不同層次的計算式也就不同，分別由式(2)、(6)、(9)計算。每個網格單元都有8個相鄰格網(U={gN，gNE，gE，gSE，gS，gSW，gW，gNW})，網格 gk∈∞ 到起始網格gorigin的成本值用W(gorign，gk)表示。

(1)在L1層需考慮距離因素。gk－1到gk的可達性成本值由式(2)計算。(Xk，Yk)、(Xk－1，Yk－1)分別為gk、gk－1的地理位置，C(gk－1)和 C(gk)分別為協商區中gk－1和gk所占的成本值。

式中gk為禁止通過區時M=∞，否則為0。2個網格之間的距離成本為

當 gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向相同時有

當 gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向不同時有

(2)在L2層需考慮距離因素以及交通方便程度，gk－1到gk的可達性成本值為

當 gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向相同時有

當 gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向不同時有

(3)在L3層需要在L2通道的基礎上選出一條輸電線路，影響因素更復雜。要考慮社會因素中的障礙物、自然因素、經濟因素、交通因素。gk－1到gk的可達性成本值為

式中:D(gk－1，gk，gk+1)為轉角成本值，若沒有轉角則D(gk－1，gk，gk+1)=0。

算法流程描述如下:

(1)初始化起點、終點和線路必須通過的中間點。

(2)從靜態格網數據中讀取Lkm×Lkm網格，從動態格網數據中調用協議區、禁止通過區等影響因素，與現有格網疊加分析，生成權重格網。

(3)調用最短路徑算法，得出線路可行性通道L1。

(4)讀取Mkm×Mkm格網，與L1通道疊置分析，調用動態數據中的道路、河流、礦山、自然保護區邊緣等非嚴格限制因素，再次生成權重格網。

(5)調用最短路徑算法，得出線路初選通道L2。

(6)讀取Nkm×Nkm格網，與得到的通道疊置分析，調用動態數據中的高速公路鐵路、地形(坡度、高程)、居民地、河流湖泊數據，再次生成計算格網。

(7)調用最短路徑算法，得出備選線路。其中，Lkm×Lkm、Mkm×Mkm、Nkm×Nkm分別對應著大、中、小尺度的網格單元。

3 實驗驗證

3.1 實驗區說明

本文選取的實驗區東西寬約98 km，南北長約34 km，如圖2所示。實驗區內包含山地、平原、地質公園、森林公園、自然保護區、湖泊、高速公路、鐵路、一般公路、密集的村鎮、電力線，地形地貌復雜，算法所考慮到的影響因素都包含在實驗區內。實驗區包含1條中標路徑，本文將用該中標路徑與本文所用算法提取出的線路做對比，以驗證此算法的合理性，然后與Dijksra算法在準確性和精度方面進行對比。

圖2 實驗區Fig.2 Experimental area

3.2 可行性實驗

實驗說明:本實驗采用網格單元為2 km×2 km、1 km×1 km和0.25 km×0.25 km的分層模型，利用本文提出的算法，在實驗區選出1條輸電線路，選線結果如圖3、4所示。

圖3 備選路徑1Fig.3 No.1 candidate path

圖4 備選路徑2Fig.4 No.2 candidate path

由實驗結果可知，備選路徑1和2的長度均為82.427 km，中標路徑長度為80.299 km，備選路徑比中標路徑多出了2.128 km，這是因為本文提出的算法為了規避陡坡而產生額外距離。3條路徑都通過山地和平原，其中坡度大于30°的長度均為0，坡度在10°～30°的路徑長度與各路徑總長度之比分別為0.164 3、0.16、0.160 9，這說明備選路徑與中標路徑經過的區域大都是坡度平緩區。備選路徑未通過居民地和河流湖泊，而中標路徑卻通過9個村莊和2個湖泊，這表明本文的方法能準確地避開居民地等障礙物。備選路徑和中標路徑都與各等級的交通線交叉，都是在交通便利區施工。

通過以上分析可知，利用本文的方法所選出的輸電線路，能合理地避開居民地、湖泊以及一些禁止通過區域，并且在地形平坦或坡度較緩的區域通過，和人工選線的結果無異，甚至優于人工選線的結果，比如能夠成功地避開居民地，而且選線速度遠遠高于人工選線。

3.3 速度對比實驗

實驗說明:本實驗先利用Dijkstra算法，在網格單元大小為0.25 km×0.25 km的格網上選出一條輸電線路，并記錄選線時間T1，然后采用分層模型算法在網格單元為 2km×2km、1km×1km和0.25 km×0.25 km的數據模型上，以相同的起止點選出另一條線路，并記錄選線時間T2，以驗證在準確性相同的條件下，本文的方法在速度上是否具有優勢。

(1)選線結果:Dijkstra算法選線的結果如圖5所示，選線耗費時間T1=20 min，分層算法選線的結果如圖6所示，選線耗費時間T2=50 s。

圖5 Dijkstra算法選線結果Fig.5 Result of route selection by Dijkstra method

圖6 分層算法選線結果Fig.6 Result of route selection by layered method

(2)實驗結果分析:由圖5、6可知，2種方法選取的線路基本一致。但2種算法選線所花費的時間卻差異較大。這主要是由于分層算法采用分層的數據模型，先在2 km×2 km、1 km×1 km的格網上選出1條通道，然后在0.25 km×0.25 km格網上只對該通道所在范圍進行運算，這比起直接在0.25 km×0.25 km的網格上運算將大大節約運算量，從而節省時間。

4 結語

本文為解決一般選線算法時間和準確性不能兼顧的問題，提出了基于分層模型的輸電線路選線算法，并用實驗驗證了該算法不僅可行，而且節約時間。列出了該算法需要考慮的影響因子，并將其進行了分類，首次考慮了線路與鐵路、高速公路、河流的夾角問題，從而使路徑盡量與其夾角大于45°。提出了一種分層次、逐級計算的選線方法，該方法綜合考慮了多種影響因子，能快速地選出輸電線路，降低了輸電線路的選取所花費的時間和成本。

人工選線是憑借選線人員的經驗進行，計算機選線則是根據分配的權重來選出合理的線路，而權重則來源于選線人員的經驗，因此，如何將選線人員的經驗量化為知識庫，從而供計算機在選線過程中參考，更準確地確定各個影響因素在不同情況下、不同網格尺度下的權重，將是下一步工作的重點。

［1］Miguel V，Hector G，Sarmiento.Image processing application maps optimal transmission routes［J］.IEEE Computer Applications in Power，1996，3(1):33-39.

［2］West N A，Dwolatzky B，Meyer A S.Terrain-based routing of distribution cables［J］.IEEE Computer Applications in Power，1997，4(1):42-47.

［3］Cláudio，Monteiro.GIS spatial analysis applied to electric line routing optimization［J］.IEEE Trans On Power Delivery，2005，20(2):13-18.

［4］Cláudio，Monteiro.Compromise seeking for power line path selection based on economic and environmental corridors［J］.IEEE Trans On Power Systems，2005，20(3):20-25.

［5］Salman A，Hamid E，Valadan Z M.A new method for path finding of power transmission lines in geospatial information system using raster networks and minimum of mean algorithm［J］.World Applied Sciences Journal，2008，3(2):269-277.

［6］Volkan Y，Recep N.Developingageospatialmodelforpower transmission line routing［C］//Proceedings of the 3rd Africon Conference.Ezulwini Valley，Swaziland:IEEE，1992:59-64.

［7］Schmidt A J.Implementing a GIS methodology for siting high voltage electric transmission lines［J］.Papers in Resource Analysis，2009，11(2):58-63.

［8］Ward J，Fellow I，Ted G，et al.A New method for public involvement in electric transmission-line routing［J］.IEEE Trans On Power Delivery，2009，24(4):33-38.

［9］劉春霞，王家海.基于空間分析的送電線路選線方法［J］.測繪工程，2008，17(3):28-30.

［10］鄭年波.面向動態導航的交通網絡數據模型與應用算法研究［D］.武漢:武漢大學，2007.