張 超，李 欣，趙祥偉

(中國能源建設(shè)集團(tuán)江蘇省電力設(shè)計(jì)院有限公司，江蘇 南京 211102)

0 引言

輸電線路選線規(guī)劃是電網(wǎng)規(guī)劃設(shè)計(jì)的重要內(nèi)容，傳統(tǒng)的路徑選線通常包括圖上初選、搜資、初勘、設(shè)計(jì)方案、現(xiàn)場終勘、線路評定等工作[1]。由于前期的搜資和現(xiàn)場勘查需要花費(fèi)大量的時(shí)間、人力和物力，而且搜集到的地理信息常常無法保證時(shí)效性和準(zhǔn)確性。傳統(tǒng)的選線方法跟專業(yè)人員的能力和經(jīng)驗(yàn)密切相關(guān)，但線路設(shè)計(jì)考慮的因素和原則常常容易顧此失彼，無法得到最優(yōu)的路徑[2]。

隨著地理信息技術(shù)的快速發(fā)展以及智能路徑規(guī)劃算法的涌現(xiàn)，輸電線路智能路徑規(guī)劃逐漸得到業(yè)內(nèi)人士的關(guān)注。余鳳先[3]等應(yīng)用地理信息系統(tǒng)(geographic information system，GIS)具有的定性、定量、定位分析功能進(jìn)行九龍—石棉500 kV送電線路的優(yōu)選工作，朱義中[4]等將層次分析法應(yīng)用于地理信息系統(tǒng)輸電線路決策支持系統(tǒng)中，實(shí)現(xiàn)線路路徑的優(yōu)選，陳小紅[5]等引入元胞自動(dòng)機(jī)模型，確定輸電線路所要經(jīng)過的各個(gè)元胞及走向，最終形成輸電規(guī)劃的路徑，蘇海峰[6-8]等介紹了改進(jìn)蟻群算法和元胞自動(dòng)機(jī)模型在輸電線路路徑自動(dòng)選擇中的應(yīng)用。

Dijkstra算法是目前最短路徑規(guī)劃問題的基本算法，已廣泛應(yīng)用于公路、鐵路、輸電線路、油氣管道等的路徑規(guī)劃中。本文采用專家決策法確定地圖柵格綜合成本，并通過限制目標(biāo)搜索區(qū)域，減少無意義運(yùn)算，提高Dijkstra算法搜索效率，能有效改善輸電線路路徑規(guī)劃的效果。

1 Dijkstra算法

1.1 基本原理

Dijkstra算法是荷蘭科學(xué)家狄克斯特拉于1959年提出的啟發(fā)式搜索方法，故也叫狄克斯特拉算法。其基本思想是：從頂點(diǎn)V0出發(fā)，搜索從它到其他各頂點(diǎn)的最短路徑。把有向圖中的頂點(diǎn)集V分成兩個(gè)子集S和T，S為已求出最短路徑頂點(diǎn)的集合，T為尚未求出最短路徑的頂點(diǎn)集合；循環(huán)遍歷集合T，每次找出最短路徑的頂點(diǎn)放入集合S中，直到集合T為空。

圖1 Dijkstra算法示意圖

如圖1所示，設(shè)帶權(quán)有向圖G={V，E}，V=V0，V1，…Vn-1，用帶權(quán)的鄰接矩陣Arc表示 圖G；Arc[i][j]表 示 弧 (Vi，Vj)上 的 權(quán) 值，S表示已求出以為起點(diǎn)的最短路徑終點(diǎn)的集合；向量D的每個(gè)D[i]表示當(dāng)前求得的從起點(diǎn)V0到每個(gè)頂點(diǎn)Vi的最短路徑的長度，利用Dijkstra算法從源點(diǎn)s到終點(diǎn)t的步驟如圖2所示。

圖2 Dijkstra算法流程圖

不同于圖論和矢量GIS的傳統(tǒng)線型網(wǎng)絡(luò)最優(yōu)路徑搜索，基于柵格地形的最優(yōu)路徑搜索可以作為虛擬柵格網(wǎng)絡(luò)的最優(yōu)路徑搜索，是一種格網(wǎng)鄰域模型的路徑搜索。根據(jù)柵格單元隱含的鄰接關(guān)系，柵格數(shù)據(jù)模型可以通過連接相鄰的節(jié)點(diǎn)來抽象成柵格網(wǎng)絡(luò)。目前常用的格網(wǎng)鄰域模型有四、八和十六格網(wǎng)鄰域結(jié)構(gòu)，其中八鄰域模型不僅具有復(fù)雜度低，而且精確度高、時(shí)間性能好等優(yōu)點(diǎn)，本文采用八鄰域結(jié)構(gòu)(如圖3所示)。

圖3 八鄰域模型結(jié)構(gòu)圖

八鄰域模型實(shí)現(xiàn)Dijkstra算法的過程如圖4所示。

圖4 Dijkstra八鄰域模型算法流程圖

1.2 算法改進(jìn)

Dijkstra算法能夠計(jì)算出兩點(diǎn)之間最短路徑的最優(yōu)解，而且魯棒性很強(qiáng)，但隨著節(jié)點(diǎn)數(shù)量的增大，它的計(jì)算效率會降低。由1.1節(jié)可知，Dijkstra算法采用帶權(quán)的鄰接矩陣存儲圖形數(shù)據(jù)，占用大量內(nèi)存空間；并且它是一種盲目或無向搜索算法，對于具有n個(gè)節(jié)點(diǎn)的圖，它的算法時(shí)間復(fù)雜度為O(n2)，計(jì)算時(shí)間和存儲開銷都比較大。本文采用限制搜索區(qū)域[9]加載部分柵格模型，提高搜索效率，降低搜索時(shí)間。

Dijkstra算法的搜索過程類似于以起點(diǎn)為圓心不斷向外擴(kuò)展的一系列同心圓，是一種無向搜索，它沒有考慮終點(diǎn)所在的位置或方向，因此在不斷向外搜索的過程中，其他頂點(diǎn)與終點(diǎn)被搜索到的概率相同。當(dāng)起點(diǎn)和終點(diǎn)距離較遠(yuǎn)時(shí)，會產(chǎn)生大量無意義的搜索，降低搜索效率，收斂時(shí)間大大增加。起點(diǎn)到終點(diǎn)之間除了距離關(guān)系外，還有方向的關(guān)系，兩點(diǎn)之間的直線線段代表了最短路線的趨勢方向，即最短路徑順著這個(gè)趨勢方向的概率極大。因此，為了減少無意義的搜索，以起點(diǎn)和終點(diǎn)作為矩形區(qū)域?qū)蔷€的兩個(gè)頂點(diǎn)，只遍歷矩形范圍內(nèi)的柵格。當(dāng)發(fā)生矩形內(nèi)的路徑被障礙物阻擋而需繞至矩形外的情況時(shí)，本文采取的方案是逐步擴(kuò)大矩形的范圍，直到搜索到最優(yōu)路徑。

1.3 模擬實(shí)驗(yàn)

圖5中紅色圓圈代表障礙物，藍(lán)色米字代表起點(diǎn)，紅色米字代表終點(diǎn)。為了提高搜素效率，通過在周邊設(shè)置障礙物的方式，阻止或減少無效的路徑尋找。

圖5 模擬最短路徑

2 輸電線路智能選線Dijkstra算法建模

2.1 柵格數(shù)據(jù)準(zhǔn)備

由于線路設(shè)計(jì)人員搜集到的資料通常都是遙感影像，而Dijkstra算法搜索最短路徑是建立在柵格基礎(chǔ)上的，所以需要對遙感影像進(jìn)行柵格化處理。進(jìn)行柵格化之前，需要對遙感影像進(jìn)行地物分類，如房屋、道路、河流、農(nóng)田、林地等，根據(jù)這些環(huán)境因素對輸電線路選線的影響程度分別賦予不同的權(quán)重。

2.2 路徑成本計(jì)算

Dijkstra算法采用“節(jié)點(diǎn)/聯(lián)系”模型來表達(dá)，每個(gè)柵格被認(rèn)為是一個(gè)節(jié)點(diǎn)，兩個(gè)相鄰節(jié)點(diǎn)用“聯(lián)系”來連結(jié)，這個(gè)“聯(lián)系”被表示為成本或代價(jià)。由于使用八鄰域模型，故從某個(gè)節(jié)點(diǎn)出發(fā)會有8個(gè)方向，這8個(gè)方向又可分為兩類，直線方向(上下左右)和斜線(對角)方向。每個(gè)柵格都被賦予相應(yīng)的權(quán)重值，即線路經(jīng)過此柵格的成本代價(jià)，用costi(i為柵格編號)表示。如圖1中直線方向的“聯(lián)系”值就是相鄰兩個(gè)柵格成本的平均值，如A、B兩點(diǎn)間的聯(lián)系成本為costAB=(costA+costB)/2，A、C兩點(diǎn)間的聯(lián)系成本為costAC=1.414×(costA+costC)/2，A、E兩點(diǎn)間的累計(jì)聯(lián)系成本為costAE=costAC+1.414×(costC+costE)/2。

從源點(diǎn)到終點(diǎn)，產(chǎn)生累計(jì)成本柵格數(shù)據(jù)以找到最佳路徑，就是一個(gè)從源柵格開始向外探索的過程。如從源柵格A出發(fā)，首先搜尋相鄰的東、西、南、北、東北、西北、東南、西南幾個(gè)方向的8個(gè)柵格，用上面的公式計(jì)算相應(yīng)的聯(lián)結(jié)成本。由于這8個(gè)鄰域柵格均可以到達(dá)源柵格，所以將他們放入OPEN列表中，然后對這8個(gè)柵格逐一擴(kuò)展，將他們的鄰域柵格加入OPEN列表，同時(shí)將這8個(gè)柵格加入CLOSE列表，代表已經(jīng)遍歷完畢。源柵格不一定要求是相連的，所有不相鄰的柵格對于OPEN列表的貢獻(xiàn)是相等的，只有具有最低成本的柵格才會被選擇，其鄰域柵格才可以被擴(kuò)展，而無需考慮是從哪個(gè)源柵格開始計(jì)算的。逐漸向外擴(kuò)展的過程中，如果發(fā)現(xiàn)某柵格有多個(gè)后向聯(lián)結(jié)柵格，那么將具有最低聯(lián)結(jié)成本的柵格安排到CLOSE列表中。計(jì)算累計(jì)成本時(shí)，這些成本也會計(jì)算新的被列入CLOSE列表中的柵格成本值，即使鄰域柵格是從另外一個(gè)源柵格開始計(jì)算的。如果新的累計(jì)成本值比當(dāng)前值大，則該值不計(jì)入；如果新累計(jì)值小，則當(dāng)前位置柵格的累計(jì)成本會被新累計(jì)值代替，這表明根據(jù)新柵格發(fā)現(xiàn)了成本更低的一條路徑，所以將其安排進(jìn)CLOSE列表。如果擴(kuò)展柵格有多個(gè)源柵格，擴(kuò)展過程將繼續(xù)將最低成本柵格加入到OPEN列表中，而不用顧及是從哪個(gè)柵格開始的，直到找到最終的最低成本也就是最優(yōu)路徑。

3 實(shí)例分析

3.1 實(shí)驗(yàn)數(shù)據(jù)來源及處理

本文采用的實(shí)例數(shù)據(jù)來源于江蘇某220 kV線路工程，如圖6所示，該線路地處江蘇北部平原地帶，地勢平坦，地物以田地、房屋、道路、河道為主。因?yàn)檩旊娋€路跨越房屋會產(chǎn)生較大的拆遷賠償費(fèi)用，故線路設(shè)計(jì)原則上盡量不跨越房屋，道路上不允許立塔，河道尤其是通航河道立塔條件較差，一般情況下田地最適合立塔。基于上述分析及專業(yè)工作經(jīng)驗(yàn)，本文對田地、房屋、林木、河流賦予的權(quán)重或成本值分別為1、4、3、2。

圖6 實(shí)驗(yàn)區(qū)域的影像

首先對遙感影像進(jìn)行矢量化，該過程也是一個(gè)地物分類的過程，本文將該區(qū)域的地物分為田地、房屋、林木、河流4類，如圖7所示，其中淺綠色表示田地，粉色表示房屋，深綠色表示林木，藍(lán)色表示河流。每種地物矢量化后，在屬性表中添加權(quán)重值的屬性。分類結(jié)束后，需進(jìn)行柵格化，考慮到柵格邊長太長，會導(dǎo)致分辨率低，地物抽象失真；柵格邊長太短，會導(dǎo)致分辨率過高，柵格數(shù)量過多，搜索過程過長，因此柵格邊長應(yīng)取值適當(dāng)，本文將柵格的邊長為50 m。劃分柵格以后，將每個(gè)柵格的權(quán)重屬性賦予柵格中心，這樣就完成了路徑搜索前的數(shù)據(jù)準(zhǔn)備工作。

圖7 矢量化后的效果圖

3.2 選線結(jié)果分析

設(shè)置起點(diǎn)和終點(diǎn)，并限制優(yōu)先搜索區(qū)域，便可以進(jìn)行最短路徑尋找，結(jié)果如圖8所示。可以看出，該路徑避開了房屋和林木，而且距離較短，基本符合最優(yōu)路徑要求。

圖8 最短路徑柵格效果圖

傳統(tǒng)的Dijkstra算法耗時(shí)2.61 s，改進(jìn)后的Dijkstra算法路徑搜索效率耗時(shí)為1.82 s，相比傳統(tǒng)算法提高了30%，效果顯著。算法效率的提高程度與路徑起終點(diǎn)在整幅圖中的分布位置有關(guān)，當(dāng)兩個(gè)點(diǎn)在圖的中間位置時(shí)，效率改善程度最高；在對角位置時(shí)，改善程度最低。

在很多情況下，運(yùn)用智能路徑規(guī)劃算法得出的路徑往往還需要進(jìn)行適當(dāng)?shù)娜斯じ深A(yù)，因?yàn)樵趯?shí)際的輸電線路工程中，要考慮的因素不止本文中所提到的幾種，還包括地質(zhì)、覆冰以及轉(zhuǎn)角數(shù)量等很多其他因素。

4 結(jié)語

輸電線路路徑設(shè)計(jì)是一個(gè)復(fù)雜耗時(shí)的工作，結(jié)合地理信息技術(shù)能夠大幅提高線路路徑設(shè)計(jì)效率。本文使用地理信息技術(shù)，將遙感影像分類并柵格化，采用智能路徑規(guī)劃Dijkstra算法，并使用MATLAB編程實(shí)現(xiàn)，在輸電線路設(shè)計(jì)工作中取得了不錯(cuò)的效果。進(jìn)一步地以線路起點(diǎn)和終點(diǎn)作為矩形區(qū)域?qū)蔷€的兩個(gè)頂點(diǎn)，只遍歷矩形范圍內(nèi)的柵格，減少無意義的耗時(shí)搜索，效率比傳統(tǒng)算法提升30%，改善效果顯著，能夠在輸電線路選線設(shè)計(jì)中發(fā)揮較大的作用。