基于WebGIS 的油田應急搶險最短路徑算法研究

任偉建，左方晨，康朝海，王瓊，霍鳳財

(東北石油大學 電氣信息工程學院，黑龍江 大慶 163318)

網絡分析作為網絡地理信息系統(WebGIS)最主要的功能之一，是地理信息系統(GIS)的重要組成部分，在電子導航、交通旅游、城市規劃、電力、通信等各種管網及管線的布局設計中發揮著重要的作用。而最短路徑是WebGIS網絡分析最基本、最關鍵的問題，在交通網絡結構的分析、交通運輸線路的選擇、通信線路的建造與維護、運輸貨流的最小成本分析、城市公共交通網絡的規劃等方面，都有直接應用的價值[1]。

隨著人們對安全、環境的重視以及油田突發事件的增多，油田應急系統的研究和應用越來越廣泛。油田應急救援過程應能夠及時、有效地將應急資源運送到事故現場，這就涉及最短路徑問題。但在應急搶險的過程中，最短路徑需要綜合考慮路徑的屬性、資源運送的時效性、安全性、經濟性等因素。為此，在搶險過程中，采用合適的最短路徑搜索算法，盡量減少計算機的運算時間，是研究最短路徑的一個重要方向[2]。

最短路徑算法主要包括圖論基本方法[3]、啟發式搜索方法[4]、動態規劃方法[5]、神經網絡方法[6]等。啟發式搜索方法多采用A*算法，但由于其執行時間通常為指數級，故一般較少采用；動態規劃方法是一種解決多階段決策問題的有效方法，但其動態決策過程中需要存儲大量的階段狀態信息，故該算法目前主要適于普通小型試驗級網絡的最短路徑處理；神經網絡方法是一種新興的算法，但由于其不成熟性，計算效率也較低，故較少采用；在實際過程中使用最多的是圖論基本方法，其中較為常用的就是迪杰斯特拉(Dijkstra)算法。由于Dijkstra算法能適應網絡拓撲的變化，性能穩定，因而在計算機網絡拓撲路徑選擇以及WebGIS中得到了廣泛的應用。目前在國內外有許多學者對Dijkstra算法進行了許多卓有成效的研究、改進和優化[7-9]，其中有兩種改進后算法的測試效果較好，分別是： DKA(the Dijkstra’s algorithm implemented with approximate buckets)和DKD(the Dijkstra’s algorithm implemented with double buckets)，適合對2個節點間的最短路徑問題進行求解。當面對大型的網絡、對時效要求很高的問題時，這些算法的搜索效率會嚴重地降低，也不能滿足問題解決的需要。筆者針對WebGIS網絡分析中的最短路徑問題，在Dijkstra算法的基礎上，對其數據結構和計算方法作了一系列的改進，優化了系統的性能并采用面向對象的方式實現了該算法，算法效率得到了明顯提高。

1 傳統Dijkstra算法

Dijkstra算法是Dijkstra E W于1959年提出的一種按路徑長度遞增的次序產生最短路徑的算法，被認為是解決單源點間最短路徑問題比較經典而且有效的算法。其基本思想是生成1棵以固定起點為根的最短路徑生成樹[10]。根到樹中每個節點的路徑即為根到該點的最短路徑，因為傳統Dijkstra算法所求問題的網絡中不存在負權，所以這棵最短路徑生成樹在生成過程中，將對各節點按其距固定起點的遠近以及點間的鄰接關系來逐個加入到樹中，先近后遠。

Dijkstra的表述通常有兩種方式： 用永久和臨時標號方式(Dijkstra算法也被稱為標號作業法，通過不斷地迭代產生出所有的永久標號)；用OPEN，CLOSE表方式。文中采用的是永久和臨時標號方式，算法的過程如下[11，16]：

設G=(V，E)是1個帶權值有向圖(這里權值可以是長度，也可以是時間、費用等)，把圖中節點集合V分成2組： 第1組為已求出最短路徑的節點集合(用S表示，初始時S中只有1個起始節點，以后每求得1條最短路徑，就將其加入到節點集合S中，直到全部節點都加入到S中，算法結束)；第2組為剩余的還沒確定的最短路徑節點的集合(用U來表示)，依據最短路徑長度的遞增順序把第2組中的節點依次地加入到集合S中。在加入的過程中，總保持從起始節點v到S中各個節點的最短路徑的長度不大于從起始節點v到U中任何節點的最短路徑的長度。此外，每一個節點都對應著一個長度，S中節點的長度就是從v到此節點的最短路徑的距離；U中節點的長度，是從v到此節點只包括S中的節點為中間節點的當前最短路徑長度。

1.1 Dijkstra算法的標號

對圖中的某點vj賦予2個標號(l，k)，第1個標號l表示從起點v0到vj最短路徑的長度；第2個標號k表示在v0到vj的最短路徑上的vj前面1個鄰點的下標，從而找到起點v0到終點的最短路徑及v0到終點vt的距離。算法的基本步驟如下：

1) 給起點v0以標號(0，k)，表示v0到v0的距離為0，v0為起點。

2) 找出已標號的點的集合S，未標號的點的集合U以及弧的集合{(vm，vn)|vm∈S，vn∈U}(m，n∈j)，這里弧的集合是指所有從已標號的點到未標號的點的弧的集合，其中vm表示已經標號的節點，vn表示與vm相鄰未標號的節點。

3) 如果{(vm，vn)|vm∈S，vn∈U}是空集，則計算結束。如果終點vt已標號(l，k)，則v0到終點vt的距離為l，而從v0到vt的最短路徑，則可以從vt反向追蹤到起點v0而得到。如果上述集合不是空集則轉下一步。

4) 對于上述集合中的每一條弧，計算sm n=l+cm n(cm n表示已標號節點vm到未標號節點vn的距離)，在所有sm n中，找到其值為最小的弧。則給此段弧的終點v標以雙標號(sm n，k)，返回步驟2)，以此類推。

若在步驟4)中，使得sm n值為最小的弧有多條，則這些弧的終點既可以任選1個標定，也可以都予以標定，若這些弧中有些弧的終點為同1點，則此點應有多個雙標號，以便最后可找到多條最短路徑。

1.2 Dijkstra算法的應用

例如求圖1中v0到v3的最短路徑：

圖1 Dijkstra算法示意

1) 給起點v0以標號(0，k)，表示v0到v0的距離為0，v0為起點。

2) 找出已標記節點S={v0}，未標號點的集合U={v1，v2，v3}以及弧的集合{(vm，vn)|vm∈S，vn∈U}={(v0，v1)，(v0，v2)}。

s01=l0+c01=0+1=1

s02=l0+c02=0+4=4

Min(s01，s02)=s01=1

這樣給弧(v0，v1)的終點v1標以(1， 0)，表示v0到v1的距離為1，并且在v0到v1的最短路徑中v1前面的1個點是v0。

3) 此時S={v0，v1}，U={v2，v3}，弧集合{(vm，vn)|vm∈S，vn∈U}={(v0，v2)， (v1，v2)， (v1，v3)}。

s02=l0+c02=0+4=4

s12=l1+c12=1+2=3

s13=l1+c13=1+5=6

Min(s02，s12，s13)=s12=3

這樣給弧(v1，v2)的終點v2標以(3， 1)，表示v0到v2的最短距離為3，并且在v0到v2的最短路徑中v2前面的1個點是v1。

4) 這時S={v0，v1，v2}，U={v3}，弧集合{(vm，vn)|vm∈S，vn∈U}={(v1，v3)， (v2，v3)}。

s13=l1+c13=1+5=6

s23=l2+c23=3+2=5

Min(s13，s23)=s23=5

這樣給弧(v2，v3)的終點v3標以(5， 2)，表示v0到v3的最短距離為5，并且在v0到v3的最短路徑中v3前面的1個點是v2。

5) 這時S={v0，v1，v2，v3}，弧集合{(vm，vn)|vm∈S，vn∈U}=φ，計算完成，如圖2所示。

圖2 Dijkstra算法標號示意

根據v3的標號可得v0到v3的距離是5，最短路徑為v0—v1—v2—v3。

按標記法實現Dijkstra算法的過程中，核心步驟就是從未標記的點中選擇1個權值最小的弧段，即1.1節所述算法的2)～4)。這是一個循環比較的過程，如果不采用任何技巧，未標記點將以無序的形式存放在1個鏈表或數組中。那么要選擇1個權值最小的弧段就必須把所有的點都掃描一遍，在大數據量的情況下，這無疑是制約計算速度的瓶頸。

2 Dijkstra算法的優化

Dijkstra算法是目前大多數系統解決最短路徑問題的基礎。Dijkstra算法的優點是程序設計簡單、通用性強，但不是專門針對特定2個點的，而在WebGIS中，往往是尋找2個特定點間的最短路徑，此時Dijkstra算法的效率會降低，而且Dijkstra算法采用的鄰接數據矩陣結構，占用空間十分巨大，嚴重浪費了計算機的資源，影響計算速度，不適合WebGIS節點量巨大的實際情況。因此在WebGIS應用中，對Dijkstra算法的改進是十分必要的。筆者從WebGIS的存儲空間以及算法的本身出發對Dijkstra算法提出了優化和改進，使之更適合WebGIS中針對固定2個點間最短路徑的實際情況。

2.1 WebGIS存儲空間的優化

最短路徑優化研究應盡量減少算法占用的存儲空間。WebGIS中的數據(如道路、管網、線路等)要進行最短路徑的計算，就必須將其按節點和邊的關系抽象為圖的結構，這在WebGIS中稱為構建網絡的拓撲關系(這里的拓撲關系僅記錄了線與節點的關系而無線與面的關系，是不完備的拓撲關系)[12]。對于圖3所示的電子地圖，要計算圖中2個點間的最短路徑，需將圖3中道路抽象為具有拓撲結構的道路網絡，如圖4所示。

圖3 電子地圖示意

圖4 拓撲結構的道路網絡示意

具有拓撲結構的道路網絡由節點、邊及相應的拓撲關系構成。其中節點是道路的交叉點、端點，邊是2個點間的一段道路。在網絡分析過程中，實際只需關心網絡邊的信息，如邊的權值、起點、終點，就可采用只存儲邊的網絡拓撲信息，不存儲實際節點的拓撲信息，減少空間分析時所要檢索的數據量。

另外對節點和弧段等數據采取動態管理的策略，也會減少算法占用的存儲空間。所謂動態管理，是指算法的開始，并不是創建整個網絡中的節點和弧段的數據結構，而是根據算法運行的需要，動態地生成、擴展以及刪除相應的節點。對數據實行動態管理的策略，能夠最大限度地發揮存儲空間的利用效率，避免無效數據占用大量的存儲空間。

2.2 直線法優化Dijkstra算法

直線法優化Dijkstra算法是指通過減小算法中的搜索范圍，以盡快達到目標節點。其核心思想： 在把研究的網絡看成平面網絡的前提下，將臨時標記節點到源點的最短路徑與該臨時標記節點到目標節點的直線距離之和，作為此臨時標記節點的一個屬性值，即選取此屬性值最小的臨時節點作為永久標記節點，這種優化算法稱為直線優化算法。此方法使得Dijkstra算法的搜索方向智能地趨向目標節點，減少了算法中遍歷的節點個數，從而提高了搜索速度。

受直線優化算法的啟發，結合WebGIS的數據組織方法可以采取一種優先搜索的方法。 從幾何的知識可知2個點之間直線距離最短，在錯綜復雜的道路網上，任選2個點，其最短路徑可設為1條從起點到終點的直線，該直線作為1條道路存在的可能性很小，但該線代表著1條路線的趨勢，順著這個方向的某條路徑是起點到終點的最短路徑的可能性極大。

如圖5所示，求A點到E點的最短路徑，可以在AE間虛擬一條連接2個點的直線，然后比較A點到鄰接點間的路段與此虛擬直線的夾角，找出夾角最小的1條AB優先處理；接下來以B點代替A，以B為起點，以同樣的方法找出與BE夾角最小的路段BF優先處理；接著以F點代替B點，以F點為起點，以同樣的方法找出與FE夾角最小的路段FI優先處理。以此類推，最終找出1條最短路徑。

由上可知，改進后的算法是在起點和終點間建立樹狀網絡拓撲的過程，同時也是路徑搜索的過程，只是在搜索過程中采用了一定的技巧，將未搜索的路徑以有方向、有目的的形式進行，從而降低原算法中搜索那些與終點背道而馳的路徑而導致算法效率低下的問題，大幅提高了計算機的運行速度。

圖5 直線優化算法路徑示意

3 改進后的Dijkstra算法在油田應急搶險系統中的應用

油田應急搶險系統是集GIS、數據庫、多媒體、語音技術及現代通信技術為一體的多功能輔助決策系統，是WebGIS空間分析的一個重要方向[13-15]。系統主要功能： 利用該系統的空間查詢技術確定事故發生地點，快速顯示采油廠的電子地圖和地理信息，在電子地圖上顯示各主要功能單位(如119，110，120和物資儲備庫)到事故發生地點的最佳行駛路線。

該系統利用ArcGIS Server 9.3 組件，在Visual C#下實現最佳路徑的查詢功能，針對油田道路網絡的具體情況，完成了改進后的Dijkstra算法在油田應急搶險系統中的應用，實現了單目標點—多源點最佳路徑查詢工作。該道路網中共有258個節點，221段弧，在主頻為3.40 GHz、內存2G的計算機中，計算5條總長度為15 667 m路徑，耗時約1.375 s。

用不同的道路數據，在同一臺電腦上，筆者又多次模擬求解同樣起點到終點的距離，表1顯示了該算法和Dijkstra算法的運行時間結果對照。

表1 同樣起點到終點運行時間對比

從表1可以看出，當網絡節點數較少時，兩種算法的運算時間相差不多，效率差異不明顯；但隨著網絡中節點數目的增多，Dijkstra算法需要遍歷圖中所有的節點，效率會降低，而該算法按照一定的搜索方向，減少了搜索節點的個數，提高了搜索速度，完全滿足了油田應急搶險系統所要求的最佳時間(1～2 s)。

4 結束語

文中詳細地介紹了Dijkstra算法的基本原理，并且結合WebGIS的實際情況，對原有的算法提出了優化方法。既節省了存儲空間，又提高了運行效率，使得Dijkstra算法真正地應用到油田應急搶險系統中。然而，目前道路網越來越復雜，也越來越龐大，在應用過程中必須要考慮眾多因素，如道路擁擠程度、道路等級、交叉口的延誤時間、交通管制信息等，因而尋找考慮多種因素的最優應急搶險路徑，將是需要進一步研究的問題。

參考文獻：

[1]PALLOTLINO S. Shortest Path Methods： Complexity， Interrelation and New Propositions. Networks[J]. 1984， 14(02)： 257-267.

[2]王一軍，羅大庸，張航.城市應急最優路徑算法[J].系統工程，2008，26(07)： 86-91.

[3]唐文武，施曉東，朱大奎.GIS中使用改進的Dijkstra算法實現最短路徑的計算[J].中國圖象圖形學報，2000，5(12)： 1019-1023.

[4]魏唯，歐陽丹彤，呂帥，等.一種多目標增量啟發式搜索算法[J].吉林大學學報，2009，47(04)： 752-758.

[5]趙慧娟，湯兵勇，張云.基于動態規劃法的物流配送路徑的隨機選擇[J].計算機應用及軟件，2013，4(30)： 110-112.

[6]紀其進.一種基于脈沖耦合神經網絡的最短路徑算法[J].小型微型計算機系統，2005，26(05)： 826-829.

[7]ZHAN F B. Three Fastest Shortest Path Algorithms on Real Road Networks[J]. Journal of Geographic Information and Decision Analysis， 1997，1(01)： 69-82.

[8]熊碧霞，楊春蘭.基于Dijkstra算法的最短時延路由算法的實現[J].中國水運，2009，9(02)： 98-99.

[9]陳靈敏.最短路徑算法在高速公路聯網收費中的研究及應用[M].貴州大學學報(自然科學版)，2009，26(01)： 47-50.

[10]GILLES B， PAUL B. Fundamentals of Algorithmics(算法基礎)[M].邱仲潘，柯渝，徐峰，等，譯.北京： 清華大學出版社，2005： 154-157.

[11]胡洪林.求最短路徑的Dijkstra算法原理分析[J].計算機科學，2008，34(07)： 60-74.

[12]王陵，段江濤，王保保.GIS中最短路徑的算法研究與仿真[J].計算機仿真，2005，22(01)： 117-120.

[13]姜鳳輝，李樹軍，姜鳳嬌.基于GIS的Dijkstra改進算法及其在交通導航系統中的應用[J].測繪與空間地理信息，2011，34(04)： 129-131.

[14]高曉榮，徐英卓.油田事故應急救援可視化決策支持系統[J].計算機工程，2010，36(15)： 236-239.

[15]羌龍華.基于GIS的油田應急指揮系統的設計與實現[J].自動化技術與應用，2011，30(07)： 38-41.

[16]SCHULZ F，WAGNER D，WEIHE K. Dijkstra’s Algorithm Online： An Empirical Case Study From Public Railroad Transport[J].Journal of Experimental Algorithmics，2000(05)： 110-123.

[17]宋士祥，張強，吳明，等.基于GIS和SOA的長輸管道管理系統的設計與實現[J].化工自動化及儀表，2012，39(08)： 998-1000，1033.