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

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

(1.華北電網(wǎng)有限公司，北京市，100053;2.北京洛斯達(dá)科技發(fā)展有限公司，北京市，100120;3.武漢大學(xué)，武漢市，430072)

0 引言

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

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

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

1 數(shù)據(jù)模型設(shè)計與影響因子分析

1.1 數(shù)據(jù)模型設(shè)計

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

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

圖1 柵格數(shù)據(jù)模型及選線Fig.1 Raster data model and route selection

1.2 影響因子分析

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

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

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

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

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

2 算法設(shè)計

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

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

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

式中g(shù)k為禁止通過區(qū)時M=∞，否則為0。2個網(wǎng)格之間的距離成本為

當(dāng) gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向相同時有

當(dāng) gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向不同時有

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

當(dāng) gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向相同時有

當(dāng) gk－1和 gk的連線方向與 gk－2和 gk－1的連線方向不同時有

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

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

算法流程描述如下:

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

(2)從靜態(tài)格網(wǎng)數(shù)據(jù)中讀取Lkm×Lkm網(wǎng)格，從動態(tài)格網(wǎng)數(shù)據(jù)中調(diào)用協(xié)議區(qū)、禁止通過區(qū)等影響因素，與現(xiàn)有格網(wǎng)疊加分析，生成權(quán)重格網(wǎng)。

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

(4)讀取Mkm×Mkm格網(wǎng)，與L1通道疊置分析，調(diào)用動態(tài)數(shù)據(jù)中的道路、河流、礦山、自然保護(hù)區(qū)邊緣等非嚴(yán)格限制因素，再次生成權(quán)重格網(wǎng)。

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

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

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

3 實(shí)驗驗證

3.1 實(shí)驗區(qū)說明

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

圖2 實(shí)驗區(qū)Fig.2 Experimental area

3.2 可行性實(shí)驗

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

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

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

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

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

3.3 速度對比實(shí)驗

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

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

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

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

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

4 結(jié)語

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

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

［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，F(xiàn)ellow 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］鄭年波.面向動態(tài)導(dǎo)航的交通網(wǎng)絡(luò)數(shù)據(jù)模型與應(yīng)用算法研究［D］.武漢:武漢大學(xué)，2007.