油氣管道應急資源調配最優路徑研究

聶宸菡

（北京建筑大學 測繪與城市空間信息學院，北京100044）

在過去較長時間內，由于我國缺乏對各類油氣管道事故管理的重視，基于我國擁有12 萬公里陸上油氣管道的現實，而其中30%以上的管道運行時間超過10 年，形成了管道事故率偏高的現狀。油氣管道事故發生后，由于管道是連續的，往往會同時或者延后出現多個事故點。并且油氣管道事故發生后會引起泄露，大量易燃、易爆、有毒有害物質的釋放，又將會導致火災、爆炸、中毒等嚴重事故的產生[1]。

基于此本文將探討研究如何選取應急資源調配的最優路徑，來滿足油氣管道自身特點以及災害后的應急需求。

1 最優路徑的常見算法

1.1 Dijkstra 算法

Dijkstra 算法，基于貪心算法。算法的中心思想是解決地圖中單個節點到其他頂點的最短路徑問題。Dijkstra 算法是一種比較典型的最短路徑算法，它用于計算一個節點到其他所有頂點的最短路徑[2]。

Dijkstra 算法的具體原理以及實現步驟如下，首先設A 為起點節點，求A 到其他所有頂點B、C、D、E 和F 的最短路徑。

圖1 Dijkstra

（1）將圖中所有頂點分為S 和V 兩個集合：首先，先將A 節點選入進S 集合中，此時S=（A）；這時的最短路徑是A=0，以A為中心點。V 是未知最短路徑頂點的集合；

（2）選入B 頂點進入S 集合，此時集合中A,B 以B 為中心點，求得起點節點到B 點的最短路徑；

（3）遍歷V 集合，尋找距離起點最近的頂點，將此頂點放置于S 集合中，求出起點到當前頂點間的最短路徑；

（4）重復（3）步，直至V 集合為空集合，算法終止，求出起點節點A 到圖中其他所有頂點（B-F）之間的最短路徑。

1.2 Best-First 算法

Best-First 算法又稱作最佳優先搜索算法，這是一種啟發式搜索算法（Heuristic Algorithm），且是基于廣度優先搜索算法[3]。不同點在于Best-First 算法依賴于估價函數對將要遍歷的節點進行估價，選擇代價小的節點進行遍歷，直到找到目標點為止。

算法實現步驟如下：

（1）從S 中選擇出權重最高的節點A，并生成子節點B。如果B 不在S 和V 集合中，通過評估函數計算出B 節點的權重，并添加進S 中，根據評估價對S 集合中的節點進行排序；

（2）反之，如果B 節點在S 中，則通過評估函數計算B 節點的權重，如果權重高于B 節點的權重，則替換原先權重，并對S中的節點排序；

（3）如果B 節點在V 中，先通過評估函數計算出B 節點的權重，如果高于V 中的權重，移除B 節點，添加到S 中，并對S中的節點排序；

（4）把A 節點從S 移除并添加到V；

（5）循環上述操作直到找到目標點，或者S 沒有節點為止。

1.3 A*算法

A*算法是比較流行的啟發式搜索算法之一，同時也是路徑搜索中最歡迎的選擇[4]。因為A*算法相當靈活，并且能用于多種多樣的情形之中。

A*算法的獨特之處是檢查最短路徑中每個可能的節點時引入了全局信息，對當前節點距終點的距離做出估計，并作為評價該節點處于最短路線上的可能性的量度。A*算法的如下式：

f（n）=g（n）+h（n）

A* 算法設置兩個列表，開啟列表（open） 和關閉列表（closed）。A*算法的具體步驟為：

圖2

2 最優路徑算法的比較分析

本文利用實驗室項目數據做了實驗，如下表。

搜索結果

從實驗結果的表格可以看出，A*算法所消耗內存、擴展節點、時間優越于另外兩種算法。A*算法和Dijkstra 算法總能找到最優路徑，但由于Best-First 基于貪心策略，僅僅考慮到達目標節點的花費，而忽略了當前已花費，導致找到的路徑有可能不是最優路徑。

3 結論

油氣管道事故發生后，為了使應急救援資源快速到達事故現場，減少災害損失，深入分析了三種經典的最優路徑算法。首先，對這三種最優路徑的核心思想與算法流程進行完整的描述；然后，對這三種最優路徑算法進行全面的比較分析，通過實驗對比，得出在求解最優路徑時，A*算法作為一種經典的啟發式搜索算法優越于另外兩種算法，能夠高效的找到兩點之間的最優路徑。A*作為一種啟發式算法，構造合適的啟發式函數，所求得的最優路徑將更符合實際情況，致力于改進和完善傳統的最優路徑搜索A*算法將會成為我們的下一步工作。