鄧 濤，熊自明，王青山

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

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

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

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

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

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

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

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

1 機場區(qū)域最優(yōu)路徑模型

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

1.1 Dijkstra算法

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

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

圖1 路網(wǎng)示意圖

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

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

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

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

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

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

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

圖2 最短路網(wǎng)示意圖

1.2 限制區(qū)域的Dijkstra改進算法

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

圖3 限制矩形區(qū)域的Dijkstra搜索

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

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

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

限制區(qū)域的Dijkstra改進具體算法如下：

輸入：研究區(qū)域D內(nèi)的道路網(wǎng)拓撲數(shù)據(jù)，預置物資倉庫P0坐標和空軍后方倉庫、場站或者機場B坐標。

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

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

2)根據(jù)道路網(wǎng)的密度選擇合適的閾值K1，K2構(gòu)造限制區(qū)域的矩形。

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

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

2 “單對單”模式

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

(1)

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

圖4 “單對單”模式?jīng)Q策流程

3 “多對單”模式

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

3.1 模型建立

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

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

(2)

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

(3)

3.2 模型實現(xiàn)

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

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

圖5 “多對單”模式?jīng)Q策流程

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

4 “多對多”模式

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

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)。

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

(4)

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

(5)

4.2 模型實現(xiàn)

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

1)各待搶修機場的搶修任務有優(yōu)先級區(qū)分的情況。該情況下，依據(jù)待搶修機場的優(yōu)先級依次進行物資調(diào)撥運輸優(yōu)化，即將“多對多”模式轉(zhuǎn)化為“多對單”模式進行。

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

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

圖6 “多對多”模式?jīng)Q策流程

5 結(jié)束語

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

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

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

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

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

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

[6]陳濤.車輛導航系統(tǒng)中大區(qū)域路徑規(guī)劃算法的設計與實現(xiàn)[D].鄭州：信息工程大學，2005.

[7]王海梅.基于GIS的最優(yōu)路徑算法研究與實現(xiàn)[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]付夢印，李杰，鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學學報，2004,24(10):881-884.

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

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

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

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

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

[16]王華.利用組合技術(shù)的迪杰斯特拉算法改進探討[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