陳素華 王飛 王瑋 賀凌霄

【摘要】本文結(jié)合地理信息系統(tǒng)（GIS）中的數(shù)字地形分析技術(shù)，利用航空或航天遙感技術(shù)獲得的地形數(shù)據(jù)，利用曲面擬合的方法，建立實(shí)際地形的規(guī)則網(wǎng)格數(shù)字高程模型（DEM）。并在此基礎(chǔ)上，采用Dijkstra算法的思想求解該地形曲面上兩點(diǎn)間的最短距離以求得電纜敷設(shè)的最優(yōu)路徑。最后，通過matlab仿真實(shí)驗(yàn)及其提供的圖形可視化界面的形式給出了在山區(qū)崎嶇不平的地形條件下兩地之間敷設(shè)電纜的最短距離及電纜走向圖。

【關(guān)鍵詞】數(shù)字高程模型;Dijkstra算法;電纜敷設(shè);最優(yōu)路徑

1.引言

隨著電網(wǎng)規(guī)模的不斷發(fā)展，考慮到城市規(guī)劃和供電可靠性等因素的影響架空線路的局限性日益明顯。從我國(guó)的國(guó)情出發(fā)，依據(jù)城市規(guī)劃對(duì)于繁華地區(qū)、重要地段、主要道路、大中型住宅小區(qū)和市容環(huán)境有特殊要求的地區(qū)，供電可靠性要求較高或重要負(fù)荷用戶，重點(diǎn)風(fēng)景旅游區(qū)的區(qū)段，沿海地區(qū)易受風(fēng)暴侵襲的主要城市的供電區(qū)域的配電網(wǎng)宜采用電纜線路。電纜線路是電力網(wǎng)的重要組成部分。國(guó)內(nèi)電纜線路建設(shè)起步較晚，從20世紀(jì)50年代開始電纜線路的研究，因此在適應(yīng)性、模型試驗(yàn)與系統(tǒng)仿真等方面還不成熟需要進(jìn)一步探索和研究。

本文結(jié)構(gòu)如下：第一節(jié)根據(jù)航空或航天遙感取得的實(shí)際地理數(shù)據(jù)，用全局?jǐn)M合的思想建立規(guī)則格網(wǎng)數(shù)字高程模型，實(shí)現(xiàn)對(duì)山區(qū)實(shí)際地形的三維空間模擬。第二節(jié)采用Dijkstra算法的思想求取曲面上兩點(diǎn)間的最短距離，并且利用GUI界面軟件平臺(tái)給出了敷設(shè)電纜的最短距離及最優(yōu)路徑。最后，第三節(jié)對(duì)本文采用的方法進(jìn)行了分析總結(jié)，指出了該種方法的不足以及需要改進(jìn)之處。

2.實(shí)際地形空間建模

電纜敷設(shè)一直以來都是電力建設(shè)中一項(xiàng)復(fù)雜、繁瑣的工作。和架空線路相比，其受外界因素（如雷害、風(fēng)害、鳥害等）影響小，具有供電可靠性高，電擊可能性小的特點(diǎn)。并且，由于電纜埋入地下，工程隱蔽，對(duì)市容環(huán)境影響較小，即使發(fā)生事故一般不會(huì)涉及人身安全。此外，電纜電容較大，很好地改善了線路的功率因數(shù)。在架空線路受限的情況下，敷設(shè)電纜不失為一種好的選擇。本文論述了如何在山區(qū)起伏不平的地形條件下找到敷設(shè)電纜的最優(yōu)路徑，從而為工程預(yù)算以及實(shí)際施工方案選擇提供了可行性依據(jù)。

2.1 地形數(shù)據(jù)的獲取

三維地形模擬可以生動(dòng)地描述地形特征還原真實(shí)環(huán)境，為電纜敷設(shè)提供科學(xué)的依據(jù)。因此，可以利用地理信息系統(tǒng)（GIS）中的數(shù)字地形分析技術(shù)來實(shí)現(xiàn)對(duì)電纜敷設(shè)環(huán)境的模擬。三維地形數(shù)據(jù)信息的獲取是通過攝影測(cè)量，以航空或航天遙感圖像為數(shù)據(jù)源，利用遙感立體像對(duì)，量取密集數(shù)字高程數(shù)據(jù)，建立數(shù)字高程模型（DEM）。

由于用規(guī)則格網(wǎng)高程矩陣表示的數(shù)字高程模型適合計(jì)算機(jī)處理和存儲(chǔ)且容易與航空、遙感等影像數(shù)據(jù)結(jié)合，它已成為一種通用的數(shù)字高程數(shù)據(jù)的組織標(biāo)準(zhǔn)?？梢允褂肅AD語句VBA語句提取地形途中的高程點(diǎn)，形成高程數(shù)據(jù)文件。也可以利用遠(yuǎn)程視頻監(jiān)控定位地理信息系統(tǒng)（ABGIS）加載圖形影像文件得到包含經(jīng)度緯度和高程數(shù)據(jù)格式為（B，H，L）文本文件，其中B表示緯度，L為經(jīng)度，H為該點(diǎn)的高程，這樣就可以建立該地區(qū)的規(guī)則格網(wǎng)數(shù)字高程模型。

2.2 空間模型的建立

根據(jù)電纜敷設(shè)國(guó)家標(biāo)準(zhǔn)GB50217-94第5.3.3直埋敷設(shè)于非凍土地區(qū)時(shí)，電纜外皮至地面深度不得小于0.7m;當(dāng)位于車行道或耕地時(shí)，應(yīng)適當(dāng)加深，且不宜小于1m。假設(shè)把某地區(qū)分成25*25的均勻網(wǎng)格區(qū)域，網(wǎng)格之間距離為0.3m，每個(gè)網(wǎng)格的坐標(biāo)值對(duì)應(yīng)該點(diǎn)的數(shù)字高程值（DEM）。從理論上講，任何復(fù)雜的曲面都可以用高次多項(xiàng)式以任意經(jīng)度去逼近（Phillios and Taylor，1972）。在整個(gè)DEM區(qū)域內(nèi)，可以通過調(diào)用matlab中的sftool工具箱得到統(tǒng)一的數(shù)學(xué)曲面函數(shù)，進(jìn)而得到曲面擬合實(shí)際地形如圖1所示。

圖1 matlab模擬的實(shí)際地形圖

圖2 網(wǎng)格區(qū)域的有向圖

圖3 曲面上的最短路徑

3.曲面兩點(diǎn)間的最短距離

在如圖1所示的地形環(huán)境下，在兩地之間敷設(shè)電纜也就涉及到如何求取空間曲面上兩點(diǎn)間的最短距離的問題。曲面上兩點(diǎn)的最短距離，即測(cè)地線是微分幾何研究的范疇，如果根據(jù)得到的曲面函數(shù)求解測(cè)地線需要解復(fù)雜的微分方程，而實(shí)際上除了一小部分有規(guī)律、比較特殊的微分方程，絕大多數(shù)微分方程都沒有解析解（即精確值），只能數(shù)值分析法來得到近似解，應(yīng)用神經(jīng)網(wǎng)絡(luò)或遺傳算法來求解此類問題時(shí)計(jì)算量非常大，程序復(fù)雜，占用計(jì)算機(jī)內(nèi)存大，而且有時(shí)只能得到局部最優(yōu)解。因此本文利用Dijstra算法的思想來求解空間曲面上兩點(diǎn)間的最短距離，在滿足要求精度的前提下能夠得到全局最優(yōu)解。

Dijstra算法是典型的單源最短路徑算法，用于計(jì)算有向圖中單個(gè)源節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。該算法一般有兩種表述方式，一種是用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN，CLOSE表的方式，這里選擇用永久和臨時(shí)標(biāo)號(hào)方式。

圖4 最短距離及路徑的GUI顯示界面

該算法的輸入包含一個(gè)有權(quán)重的有向圖G，以及G中的一個(gè)源節(jié)點(diǎn)Vs，以V表示G中所有節(jié)點(diǎn)的集合，引入一個(gè)輔助向量D，它的每個(gè)分量D表示當(dāng)前所找到的從起始點(diǎn)到每個(gè)終點(diǎn)的最短路徑的長(zhǎng)度，在算法整個(gè)過程中D的值是在不斷逼近最終結(jié)果。每一個(gè)圖中的邊都是兩個(gè)節(jié)點(diǎn)所形成的有序元素對(duì)——（Vi，Vj）表示從節(jié)點(diǎn)Vi到Vj有路徑相連。以E表示所有邊的集合，邊的權(quán)重由權(quán)重函數(shù)w：E→[0，∞]定義。因此，w（Vi，Vj）就是從節(jié)點(diǎn)Vi到節(jié)點(diǎn)Vj的距離。已知有V中有節(jié)點(diǎn)Vs及Vt，Dijkstra算法可以找到從源節(jié)點(diǎn)Vs到終點(diǎn)Vt的最短路徑。

算法過程如下：

（1）初始化D[Vs]=0，所有的點(diǎn)設(shè)為沒有擴(kuò)展過，在沒有擴(kuò)展過的點(diǎn)中取一距離最小的點(diǎn)Vi，將其狀態(tài)設(shè)為以擴(kuò)展。

（2）對(duì)于每個(gè)與Vi相鄰的點(diǎn)Vj，如果D[Vi]+ w（Vi，Vj）

（3）重復(fù)步驟1和2，直到到達(dá)終點(diǎn)Vt，此時(shí)D[Vt]就是Vs到Vt的最短路徑。

圖1所示的實(shí)際地形投影到水平面上的圖形看成是由25*25個(gè)網(wǎng)格點(diǎn)組成的有向圖，如圖2所示，每個(gè)網(wǎng)格點(diǎn)從1到625分別編號(hào)，每個(gè)網(wǎng)格點(diǎn)的數(shù)值為該點(diǎn)的高程值Hi。該有向圖的關(guān)聯(lián)矩陣為625*625的對(duì)角線為零的稀疏對(duì)稱矩陣G，其中元素Gij為編號(hào)為i的點(diǎn)到編號(hào)為j的點(diǎn)之間的距離。這里用相鄰的網(wǎng)格點(diǎn)間的直線距離代替其曲線距離，不相鄰的網(wǎng)格點(diǎn)間的距離設(shè)為無窮大。

在matlab的GUI圖形可視化界面分別輸入源節(jié)點(diǎn)和目的節(jié)點(diǎn)的編號(hào)，則可得到兩節(jié)點(diǎn)間的最短路徑距離及最優(yōu)路徑樹。例如在圖1所示的地形曲面上求第159點(diǎn)到第454點(diǎn)的最短距v離及路徑，執(zhí)行dijstra算法，通過matlab仿真得到最短路徑如圖3所示。通過GUI圖形化可視界面顯示最短路徑及距離如圖4所示。

4.結(jié)論

本文利用航空或航天取得的遙感地理信息（GIS）數(shù)據(jù)為基礎(chǔ)，結(jié)合Dijkstra算法求空間曲面上最短路徑的思想，應(yīng)用matlab仿真解決實(shí)際地形條件下電纜敷設(shè)的優(yōu)化設(shè)計(jì)，并通過GUI圖形化可視界面顯示出實(shí)際地形環(huán)境下的最短路徑及兩地的最短距離數(shù)值，從而為工程預(yù)算以及實(shí)際施工提供了可行性依據(jù)。然而在實(shí)際電纜敷設(shè)過程中，不但要考慮實(shí)際的地形地貌因素，還要考慮到要避免與供排水管道及熱力管的交叉、工礦建筑物的跨越、道路及附屬設(shè)施等的影響，因此應(yīng)用該種方法解決電纜敷設(shè)還要考慮到以上附加因素。此外，對(duì)于三維地形模擬和Dijkstra算法的精度和時(shí)間復(fù)雜度之間如何權(quán)衡需要進(jìn)一步分析和研究。

參考文獻(xiàn)

[1]張海榮.地理信息系統(tǒng)原理與應(yīng)用[D].中國(guó)礦業(yè)大學(xué)出版社，2007.

[2]李志林，朱慶.數(shù)字高程模型（第二版）[D].武漢：武漢大學(xué)出版社，2003.

[3]吳守亮.基于Matlab的三維數(shù)字地形模擬及空間分析[J].測(cè)繪工程，2011，20（3）.

[4]俞集輝，孫渝江，聶黎.Floyd Dijkstra算法在電纜敷設(shè)設(shè)計(jì)中的應(yīng)用[J].重慶大學(xué)學(xué)報(bào)，1999，22（2）.

作者簡(jiǎn)介：陳素華（1983—），女，河北廊坊人，工程師，研究方向：電力調(diào)度自動(dòng)化。