基于改進(jìn)Dijkstra算法的機(jī)場(chǎng)搶修決策模型研究

鄧 濤，熊自明，王青山

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

基于改進(jìn)Dijkstra算法的機(jī)場(chǎng)搶修決策模型研究

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

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

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

機(jī)場(chǎng)搶修；決策；GIS；Dijkstra算法；模型

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

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

1 機(jī)場(chǎng)區(qū)域最優(yōu)路徑模型

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

1.1 Dijkstra算法

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

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

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

根據(jù)Dijkstra算法的原理，除去預(yù)置物資倉(cāng)庫(kù)P0作為搜索起點(diǎn)外，還須進(jìn)行5輪搜索，每次搜索標(biāo)記1個(gè)倉(cāng)庫(kù)或場(chǎng)站，具體搜索過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

1)以源點(diǎn)和目標(biāo)點(diǎn)的連線為X軸，以其垂直的方向?yàn)閅軸，以源點(diǎn)為原點(diǎn)建立直角坐標(biāo)系。

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

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

輸入：研究區(qū)域D內(nèi)的道路網(wǎng)拓?fù)鋽?shù)據(jù)，預(yù)置物資倉(cāng)庫(kù)P0坐標(biāo)和空軍后方倉(cāng)庫(kù)、場(chǎng)站或者機(jī)場(chǎng)B坐標(biāo)。

輸出：P0和B間的一條最短路徑和最短路徑的長(zhǎng)度。

1)以源點(diǎn)P0和目標(biāo)點(diǎn)B的連線為X軸，以其垂直的方向?yàn)閅軸，以P0為原點(diǎn)建立直角坐標(biāo)系。

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

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

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

2 “單對(duì)單”模式

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

(1)

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

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

3 “多對(duì)單”模式

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

3.1 模型建立

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

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

(2)

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

(3)

3.2 模型實(shí)現(xiàn)

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

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

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

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

4 “多對(duì)多”模式

“多對(duì)多”模式，是最復(fù)雜的機(jī)場(chǎng)搶修保障模式，有多個(gè)預(yù)置物資倉(cāng)庫(kù)和多個(gè)待搶修機(jī)場(chǎng)，需要解決多個(gè)預(yù)置物資倉(cāng)庫(kù)和多個(gè)待搶修機(jī)場(chǎng)之間的優(yōu)化保障問(wèn)題。

4.1 模型建立

假設(shè)某方向上，有n個(gè)待搶修機(jī)場(chǎng)Bi(i=1，2，…，n)，對(duì)物資的需求量分別為Yik(k=1，2，…，s)，s為物資種類，選定m個(gè)預(yù)置物資倉(cāng)庫(kù)承擔(dān)其物資供應(yīng)任務(wù)，分別是Pj(j=1，2，…，m)，物資存儲(chǔ)量分別為Rjk(j=1，2，…，m；k=1，2，…，s)。

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

(4)

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

(5)

4.2 模型實(shí)現(xiàn)

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

[2]萬(wàn)莉.基于GIS和最短路徑算法的物流重心選址的研究[D].長(zhǎng)沙：中南大學(xué)，2007.

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

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

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

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

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

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

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

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

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

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

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

[責(zé)任編輯：張德福]

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(41201390)

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

P208

：A

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