基于改進Dijkstra算法的機場搶修決策模型研究

鄧 濤，熊自明，王青山

(1.信息工程大學 地理空間信息學院，河南 鄭州 450052；2.解放軍特種作戰學院，廣東 廣州 510500)

基于改進Dijkstra算法的機場搶修決策模型研究

鄧 濤1，熊自明2，王青山1

(1.信息工程大學 地理空間信息學院，河南 鄭州 450052；2.解放軍特種作戰學院，廣東 廣州 510500)

機場搶修決策模型是實現機場道面快速搶修的核心環節，傳統的機場搶修決策模型普遍存在模型假設脫離實際、計算結果在實際中難以應用等缺點。文中將GIS技術應用于機場搶修決策，提出基于限制區域的Dijkstra改進算法的最優路徑模型，在此基礎上，探討“單對單”、“多對單”和“多對多”3種模式下機場搶修決策模型的建立方法。

機場搶修；決策；GIS；Dijkstra算法；模型

機場搶修決策模型是實現機場道面快速搶修的核心環節，是機場搶修部門根據機場道面修復所需材料和設備情況、預置物資倉庫的儲備情況，對材料和設備的有序流動作出的科學計劃安排。機場搶修決策主要研究預置倉庫如何給機場調撥運輸所需修復材料和設備的問題。

傳統的機場搶修決策模型普遍存在模型假設脫離實際、計算結果在實際中難以應用等缺點。GIS特有的一些功能可以彌補傳統方法的不足，能使決策過程更加快捷、方便，結果更加精確、實用。

1 機場區域最優路徑模型

最優路徑模型是GIS中的重要網絡空間分析算法，應用范圍較廣。但是，在機場區域最優路徑計算與普通路徑優化算法存在一個最大的不同點就是：機場區域最優路徑的計算是在一個相對較小的區域范圍內進行。因此，本文針對小區域范圍內Dijkstra算法路徑搜索效率低的問題，結合機場搶修業務實際改進優化經典的Dijkstra算法。

1.1 Dijkstra算法

最優路徑問題最經典的算法是Dijkstra算法，其他路徑優化算法大都是基于此算法的改進，如A*算法。Dijkstra算法實際上是一種圖上標記作業法，每次計算完成一個搜索節點就產生一個標記，直至所有路網節點被標記。為了便于理解，本文結合一個具體實例解釋Dijkstra算法的基本原理和步驟。

假設某區域有5個后方倉庫或場站，其位置分別是A1～A5，另外還預置物資倉庫，其所在位置P0，如圖1所示?，F需5個倉庫或場站給預置物資倉庫補充物資，求出從預置物資倉庫到5個倉庫或場站各自的最短路徑及其路程。圖1中的數字是各資源點或預置物資倉庫之間的距離。

圖1 路網示意圖

根據Dijkstra算法的原理，除去預置物資倉庫P0作為搜索起點外，還須進行5輪搜索，每次搜索標記1個倉庫或場站，具體搜索過程如下：

1)初始化P0并作標記，搜索與P0的鄰近相通的節點有A1和A2，尋找到與P0距離最短的鄰近相通節點A2并作標記，則最短路徑為P0→A2，最短距離為1；

2)在已標記的節點P0，A2中尋找未作標記的鄰近相通節點，找到節點A1、A3和A4，3個節點中距離最短的為節點P0到A1，給A1作標記，最短路徑為P0→A1，最短距離為2；

3)在已標記的節點P0，A1，A2中尋找未作標記的鄰近相通節點，找到節點A3和A4，兩個節點中距離最短的為節點A4，給A4作標記，最短路徑為P0→A1→A4，最短距離為5；

4)在已標記的節點P0，A1，A4，A2中尋找未作標記的鄰近相通節點，找到節點A3和A5,兩個節點中距離最短的為節點A3，給A3作標記，最短路徑為P0→A2→A3，最短距離為6；

5)在已標記的節點P0，A1，A2，A4，A3中尋找未作標記的鄰近相通節點，只有節點A5且為最后一個節點,直接給A5作標記，最短路徑為P0→A1→A4→A5，最短距離為8。

至此，預置物資倉庫P0到各倉庫或場站的最短距離均已算出，從預置物資倉庫P0到各倉庫或場站的最短路徑均可以反推前一個節點得出。根據優化結果繪出最短路網示意圖如圖2所示，圖中矩形框內所示為對應節點到P0的最短距離。

圖2 最短路網示意圖

1.2 限制區域的Dijkstra改進算法

由于機場區域最優路徑的計算是在一個相對較小的區域范圍內進行，并不需要搜索所有的道路網節點。因此針對此問題，本文提出一種限制區域的Dijkstra改進算法，其基本思路如圖3所示。

圖3 限制矩形區域的Dijkstra搜索

圖3中，Dijkstra算法搜索最短路徑時幾乎是以源點為圓心的圓向外擴展，直到找到目的地為止，所以Dijkstra算法搜索的范圍幾乎相當于以源點和目的地為半徑的整個圓的范圍。限制矩形區域的Dijkstra改進算法的基本要點是：將算法搜索的范圍限制在以源點和目的地連線為基礎構造的一個外擴矩形范圍內，由此可以大大減少算法的搜索范圍。該矩形區域建立的方法是：

1)以源點和目標點的連線為X軸，以其垂直的方向為Y軸，以源點為原點建立直角坐標系。

2)矩形的長度LR為源點和目標點的連線長度LPB外擴合適的閾值K1確定，矩形的寬WR由閾值K2確定，即LR=LPB+2K1，WR=K2。通常閾值K1，K2可根據LPB來確定，即Ki=λi*LPB(i=1,2)，其中λi為比例因子，可根據區域內道路的密集程度來確定，如果區域內道路較密可取值較小，如0.2，如果區域內道路較稀少可取值較大，如0.8，其他情況可介于兩者之間。

限制區域的Dijkstra改進具體算法如下：

輸入：研究區域D內的道路網拓撲數據，預置物資倉庫P0坐標和空軍后方倉庫、場站或者機場B坐標。

輸出：P0和B間的一條最短路徑和最短路徑的長度。

1)以源點P0和目標點B的連線為X軸，以其垂直的方向為Y軸，以P0為原點建立直角坐標系。

2)根據道路網的密度選擇合適的閾值K1，K2構造限制區域的矩形。

3)在Dijkstra算法運算過程中，判斷已標記的節點鄰近相通節點是否在限制區域的矩形范圍內，如果不在則置該節點的權重為最大值表示不相連通；如果在則按照Dijkstra算法繼續運行。

4)輸出P0和B間的最短路徑和最短路徑的長度。

2 “單對單”模式

“單對單”模式，是最簡單的機場搶修保障模式，只有一個預置物資倉庫和一個待搶修機場，是屬于典型的兩個固定地點之間尋求最優路徑的問題。假設預置物資倉庫為P0，需要搶修的機場為B，P0到B經過N個節點的路網，則其目標函數為

(1)

“單對單”模式的最優路徑直接利用1.2中給出的模型求解即可。具體的搶修決策流程為：首先根據機場道面破壞狀況評定模型確定機場道面修復所需材料和設備的種類、數量；然后在GIS中查詢預置物資倉庫中存儲的材料和設備情況是否滿足需求，如果滿足需求則啟動“單對單”搶修運輸模式；最后利用機場區域最優路徑模型計算最優運輸路徑，并給出經過的主要地名、路徑長度等信息。具體流程如圖4所示。

圖4 “單對單”模式決策流程

3 “多對單”模式

“多對單”模式，是一種較復雜的機場搶修保障模式，有多個預置物資倉庫和一個待搶修機場。在搶修機場確定的情況下，需要對當前參與保障的預置物資倉庫的保障能力、空間分布及道路交通等信息進行分析，從多個預置物資倉庫中選出最優的保障對象、保障品種和數量，明確其輸送路線。

3.1 模型建立

假設某方向上，有1個待搶修機場B，對物資(為簡化問題，將機場道面修復所需的材料和設備統稱為物資)的需求量分別為Yk(k=1，2，…，s)，s為物資種類，選定m個預置物資倉庫承擔其物資供應任務，分別是Pj(j=1，2，…，m)，物資存儲量分別為Rjk(j=1，2，…，m；k=1，2，…，s)。

利用機場區域最優路徑模型，分別求出預置物資倉庫Pj到機場B的最短路徑距離，設Pj到B為短路徑距離為dj(j=1，2，…，m)，構建距離關系矩陣

(2)

然后對距離關系矩陣d進行排序，根據就近保障原則，依次找到最小距離的預置物資倉庫進行搶修保障，使得總距離最短。

(3)

3.2 模型實現

“多對單”模式機場搶修決策模型是根據道路交通條件進行的，模型實現主要有兩種方法：

1)以待搶修機場所在地為運算起點。運用機場區域最優路徑模型，從該點出發沿著與其相連通的道路進行搜索，對在搜索過程中遇到的預置物資倉庫及其保障能力進行判斷，如果預置物資倉庫無保障能力或者不屬于保障范圍，則繼續搜索，如果預置物資倉庫具備保障能力則記錄其相關信息(如地理位置、連接道路、物資儲備情況)，如果搶修所需物資的需求量已經得到滿足則停止搜索，否則繼續搜尋。其流程如圖5所示。

圖5 “多對單”模式決策流程

2)以預置物資倉庫所在地為運算起點。運用機場區域最優路徑模型，獲取所有參與保障的預置物資倉庫與待搶修機場之間的距離關系矩陣，然后按照就近保障原則，優先選擇距離最短的預置物資倉庫，計算其物資種類、數量，如果不能滿足保障任務，則繼續選擇剩下距離最短的預置物資倉庫，直至滿足搶修物資需求為止。

4 “多對多”模式

“多對多”模式，是最復雜的機場搶修保障模式，有多個預置物資倉庫和多個待搶修機場，需要解決多個預置物資倉庫和多個待搶修機場之間的優化保障問題。

4.1 模型建立

假設某方向上，有n個待搶修機場Bi(i=1，2，…，n)，對物資的需求量分別為Yik(k=1，2，…，s)，s為物資種類，選定m個預置物資倉庫承擔其物資供應任務，分別是Pj(j=1，2，…，m)，物資存儲量分別為Rjk(j=1，2，…，m；k=1，2，…，s)。

利用機場區域最優路徑模型，分別求出預置物資倉庫Pj到機場Bi的最短路徑距離，設Pj到Bi最短路徑距離為dji(j=1，2，…，m；i=1，2，…，n)，構建距離關系矩陣

(4)

然后對距離關系矩陣d進行總排序，根據就近保障原則，依次找到最小距離的預置物資倉庫進行搶修保障，使得總距離最短。

(5)

4.2 模型實現

“多對多”模式的模型基于GIS實現主要有兩種情況。

1)各待搶修機場的搶修任務有優先級區分的情況。該情況下，依據待搶修機場的優先級依次進行物資調撥運輸優化，即將“多對多”模式轉化為“多對單”模式進行。

2)各待搶修機場的搶修任務沒有優先級區分的情況。該情況下有兩種實現方法：第一種方法是利用機場區域最優路徑模型求出預置物資倉庫與待搶修機場之間的距離關系矩陣，然后比較所有矩陣元素，按照就近保障的原則，即距離從小到大的順序依次確定參與保障的預置物資倉庫，直至需求任務完成；第二種方法是將待搶修機場所在地作為運算起點，從該點出發沿著與其相連通的道路進行搜索，對在搜索過程中遇到的預置物資倉庫進行判斷，如果不屬于保障范圍或無保障能力則繼續搜索，否則將預置物資倉庫的保障物資數量記錄下來，如果保障任務已得到滿足則停止搜索，否則繼續搜索。具體流程如圖6所示。

搜索完成后進行匯總，明確各待搶修機場由哪些預置物資倉庫進行保障，各預置物資倉庫的保障種類、保障數量以及這些預置物資倉庫進行保障時的最優路徑。

圖6 “多對多”模式決策流程

5 結束語

本文將GIS中的基于改進Dijkstra算法的最優路徑模型應用于機場搶修決策，給出“單對單”、“多對單”和“多對多”3種模式下機場搶修決策模型的建立方法，為機場搶修科學決策提供一個有效的方法。

[1]武軍，王治.一種機場搶修預置物資倉庫選址模型[J].基建優化，2006，28(3):91-93.

[2]萬莉.基于GIS和最短路徑算法的物流重心選址的研究[D].長沙：中南大學，2007.

[3]李慶奎，呂志平，李昌貴. 基于模糊理論的智能最優路徑算法[J].測繪工程，2011，20(4):5-8.

[4]付金輝，趙軍喜，高源. 基于灰色預測法的超市選址模型研究[J].測繪工程，2013，22(5):46-50.

[5]李元臣，劉維群.基于Dijkstra算法的網絡最短路徑分析[J].微計算機應用，2004，25(3):295-298.

[6]陳濤.車輛導航系統中大區域路徑規劃算法的設計與實現[D].鄭州：信息工程大學，2005.

[7]王海梅.基于GIS的最優路徑算法研究與實現[D].南京：南京大學，2008.

[8]AHN C W, RAMAKRISHNA R S. A genetic algorithm for shortest path routing problem and the sizing populations[J]. IEEE Transactions on Evolutionary Computation，2002,6(6):566-580.

[9]ZHAN F B, NOON C E. Short path algorithms: an evaluation using real road network [J]. Transportation Science，1998, 32(1):65-73.

[10]付夢印，李杰，鄧志紅.限制搜索區域的距離最短路徑規劃算法[J].北京理工大學學報，2004,24(10):881-884.

[11]王海濤，朱春生，安立國，等.野戰機場搶修搶建機械群調度系統的研究與實現[J].機械制造與研究，2009，41(3):73-76.

[12]張仁平，劉奇韜.物資調撥運輸優化模型及應用研究[J].物流技術，2009(3)：85-87.

[13]李愛零.戰時物資籌措與運送模型研究[D].西安：西安電子科技大學，2007.

[14]龔延成.戰時軍事物流系統決策理論與方法研究[D].西安：長安大學，2004.

[15]溫伯威，王超峰，劉瑞雪，等.基于泛在網信息的城市應急疏散決策研究[J].測繪工程，2013，22(6)：58-60.

[16]王華.利用組合技術的迪杰斯特拉算法改進探討[J].測繪科學，2014，39(2)：52-54.

[責任編輯：張德福]

Research on airport rapid repair decision-making model based on improved Dijkstra algorithm

DENG Tao1, XIONG Zi-ming2, WANG Qing-shan1

(1.School of Geographic Spatial Information，Information Engineering University, Zhengzhou 450052, China;2. Special Operations University, Guangzhou 510500, China)

The model of airport rapid repair decision-making is the key link in realizing airport rapid repair, while traditional airport rapid repair emergency decision-making has some shortcomings widespreadly, such as: the assumption is away from reality, the calculation results are difficult to apply to the practice，and so on. GIS technology is applied to the airport rapid repair decision-making, and proposed an optimal path model using restricted areas of Dijkstra algorithm. Discussion is made on the establishment method of this model under three patterns of “single to single”, “single to many” and “many to many”.

airport rapid repair; decision-making; geographic information system(GIS); dijkstra algorithm; model

2014-03-17

國家自然科學基金資助項目(41201390)

鄧 濤(1984-)，男，博士研究生.

P208

：A

：1006-7949(2014)10-0031-05