基于Dijkstra 算法的多約束軍事運(yùn)輸最優(yōu)路徑研究

王 軍，賈 斌，董立峰，吉 帥，石鈺磊

(1.軍事交通學(xué)院 研究生管理大隊，天津300161;2.軍事交通學(xué)院 國家應(yīng)急交通運(yùn)輸裝備工程技術(shù)中心，天津300161)

軍事運(yùn)輸具有很強(qiáng)的約束性，在制訂運(yùn)輸方案中，如何選擇最優(yōu)路徑，以最快速度將人員、物資、裝備運(yùn)送到目的地是軍事運(yùn)輸決策部門需要解決的重要問題。由于運(yùn)輸?shù)能娛卵b備多數(shù)情況下超限(超長、超寬、超高)，對道路限重標(biāo)準(zhǔn)、縱坡、曲半徑和車輛行駛速度等具有很高的要求，因此，在選擇運(yùn)輸路徑時不僅需要考慮路線距離，還要考慮各項道路技術(shù)條件以及道路的交通狀況，只有這樣，才能制定出具有實際價值的最優(yōu)路徑。對最優(yōu)路徑的求解，可以按照求解最短路徑的方法進(jìn)行拓展。最短路徑算法種類很多，包括Dijkstra 算法、A*算法、D*算法等［1］，其中，Dijkstra 算法是目前采用最多的傳統(tǒng)方法。但是，作為一種基于單一權(quán)值的算法，未能考慮路徑的多種約束條件。本文針對傳統(tǒng)Dijkstra 算法，結(jié)合制訂軍事運(yùn)輸方案需求，對該算法進(jìn)行拓展，可有效解決多約束條件的路徑選擇問題，并通過限制搜索區(qū)域方法、降低路網(wǎng)規(guī)模提高算法搜索效率。

1 路徑選擇模型建立

1.1 Dijkstra 算法描述

Dijkstra 算法使用廣度優(yōu)先搜索解決非負(fù)權(quán)有向圖的單源點(diǎn)最短路徑問題，算法以源點(diǎn)為中心向外層層擴(kuò)展遍歷，直到目標(biāo)點(diǎn)為止，按路徑長度遞增次序產(chǎn)生最短路徑。

假設(shè)G=(V，E)是一個帶權(quán)的有向圖，其中V為所有節(jié)點(diǎn)的集合，E為邊的集合。設(shè):M為已確定最短路徑的標(biāo)定節(jié)點(diǎn)集合;T為未確定最短路徑的未標(biāo)定節(jié)點(diǎn)集合。有向圖中任意一個節(jié)點(diǎn)i都有一對標(biāo)號(di，pi)，其中:di為從源點(diǎn)s到點(diǎn)i的最短路徑的長度;pi為從s到i的最短路徑中i點(diǎn)的前一點(diǎn)。dij表示節(jié)點(diǎn)i和j之間的距離(i與j直接相連，否則dij=∞)。算法求解過程如下:

(1)初始化。M= {s}，T=V-M，ds=0，ps為空;其他節(jié)點(diǎn)dij=∞，pi為空。

(2)從T中選取節(jié)點(diǎn)k，使得dk最小，并將k加入集合M中，即M={s，k}，T=V-{k}，pk=s。

(3)以標(biāo)記節(jié)點(diǎn)k為中間點(diǎn)，檢驗k到其直接相連的未標(biāo)記節(jié)點(diǎn)i的距離，并設(shè)置

若di改變，則pi=k。

(4)從所有未標(biāo)記節(jié)點(diǎn)集T中，選取di中最小的一個點(diǎn)j，dj= mindi，i∈T，點(diǎn)j即被選為最短路徑中一個節(jié)點(diǎn)，M={s，k，j}，T=V-{k，j}。

(5)如果所有節(jié)點(diǎn)都已標(biāo)記，包含于M，則算法結(jié)束;否則，記k=j，轉(zhuǎn)到步驟(3)再重復(fù)進(jìn)行。

1.2 多約束條件定義

Djikstra 算法基于單一指標(biāo)(路徑距離)，不能直接用于多約束條件路徑選擇，需要對算法進(jìn)行擴(kuò)展。在最優(yōu)路徑選擇中，涉及因素不僅包括傳統(tǒng)的時間、里程指標(biāo)，還包括道路等級、必經(jīng)路段、禁止路段、通行能力、安全通過概率等，在數(shù)學(xué)模型中表現(xiàn)為圖中邊的權(quán)值并不是唯一的，因此，有必要建立一種能夠把邊上多約束條件映射成單一權(quán)值的數(shù)學(xué)模型［2］。在所有涉及因素中，根據(jù)約束條件對最優(yōu)路徑選擇影響的不同，分為加法約束、乘法約束和凹性約束3 種類型。

記d(x，y)表示路段(x，y)的約束權(quán)值，則對于路徑P = (h，i，j，k)，可以作出以下定義:如果d(P)=d(h，i)+d(i，j)+d(j，k)，稱d(x，y)為加法約束，例如路段長度;如果d(P)=d(h，i)×d(i，j)×d(j，k)，稱d(x，y)為乘法約束，例如路徑安全通過概率;如果d(P)=min{d(h，i)，d(i，j)，d(j，k)}，稱d(x，y)為凹性約束，例如道路限重標(biāo)準(zhǔn)。

通?？蓪⒉煌s束類型轉(zhuǎn)化為加法約束，以實現(xiàn)計算的簡單化。對于凹性約束，在進(jìn)行最優(yōu)路徑選擇之前，將不滿足最小權(quán)值要求的路段刪除，例如公路運(yùn)輸中，某一路段對車輛進(jìn)行限重，并且限制重量低于裝載貨物重量，那么在選擇路徑時不必考慮該路段;對于乘法約束，將各路段約束權(quán)值取對數(shù)變換，變?yōu)榧臃s束，使得在進(jìn)行路徑選擇時，一般只考慮加法約束。

1.3 路徑選擇多約束模型

考慮到軍事運(yùn)輸最優(yōu)路徑選擇計算的復(fù)雜性，本文選擇以路段距離、道路限重標(biāo)準(zhǔn)、道路安全通過概率3 個約束條件為例，建立出行路徑選擇模型。

設(shè)一條路徑P 由路段(e1，e2，…，ei)組成，運(yùn)輸車輛通過該路徑時行駛距離可以表示為

式中sk表示路段ek的距離。

假設(shè)車輛勻速通過鄰近節(jié)點(diǎn)各路段，此時，路程最短就等同于時間最短，可以滿足時間最短原則，行駛時間記為

式中:tk=sk/v0為車輛在路段ek的行駛時間;v0為車輛行駛速度。

路段ek的道路限重標(biāo)準(zhǔn)用hk來表示，主要對車輛荷載質(zhì)量進(jìn)行約束，那么由路段(e1，e2，…，ei)組成的路徑P 的整體限重標(biāo)準(zhǔn)屬于凹性約束，可以表示為

即一條路徑的限重標(biāo)準(zhǔn)為組成該路徑的所有路段限重標(biāo)準(zhǔn)的最小值。

路段ek的安全通過概率用pk來表示，用來描述該路段的交通狀況。設(shè)路徑P 由路段(e1，e2，…，ei)組成，根據(jù)概率論相關(guān)知識可知，該路徑的安全通過概率P屬于乘法約束:

即一條路徑的安全通過概率等于組成該路徑所有路段安全通過概率的乘積。根據(jù)1.2 中對多約束條件的定義，對等式兩邊取對數(shù)，將乘法約束表示為加法約束:

由于pk≤1，等式兩邊均為負(fù)數(shù)。兩邊同乘-1，得

根據(jù)對數(shù)函數(shù)的性質(zhì)可知，P取最大值等價于P*取最小值，符合Dijkstra 算法搜索最小權(quán)值的原理和邊權(quán)值為非負(fù)數(shù)的要求。

1.4 多約束條件向單一權(quán)值的轉(zhuǎn)換

在最優(yōu)路徑選擇過程中，可以把道路限重標(biāo)準(zhǔn)作為一個瓶頸約束條件，在搜索之前將不符合運(yùn)輸要求的路段刪除。對于道路長度和安全通過概率，將2 個約束條件融合，引入估值函數(shù):

式中:λ1和λ2分別為決策部門對道路長度和安全通過概率2 個約束條件的關(guān)注度，0 ≤λ1≤1，0≤λ2≤1，且λ1+ λ2=1;sk為路段距離;mk為安全通過概率等價轉(zhuǎn)化后的距離，且式中:ˉv為車輛行駛的平均速度;lk為路段ek本身固有的交通狀況，由實際勘測、綜合考慮發(fā)生交通事故、道路損壞等因素后評估得到;p*k=-lnpk是安全通過概率pk經(jīng)過取對數(shù)、乘以-1 得到。

如果一條路徑P 包括n個路段，則該條路徑的權(quán)值可以表示為

2 拓展Dijkstra 算法的實現(xiàn)

2.1 傳統(tǒng)求解Dijkstra 算法的不足

傳統(tǒng)Dijkstra 算法搜索路徑的效率與路網(wǎng)節(jié)點(diǎn)數(shù)量密切相關(guān)［3］。在軍事運(yùn)輸路網(wǎng)這種大規(guī)模網(wǎng)絡(luò)中，節(jié)點(diǎn)路段數(shù)量多，若直接應(yīng)用Dijkstra 算法，程序的計算時間和存儲空間將會變得非常龐大，導(dǎo)致系統(tǒng)運(yùn)行效率低下。在算法的循環(huán)迭代過程中，未標(biāo)記節(jié)點(diǎn)以無序狀態(tài)存放，每次選擇路徑必須把所有節(jié)點(diǎn)搜索一遍，并且是毫無方向性地向四周擴(kuò)散，在大數(shù)據(jù)量的情況下，將嚴(yán)重制約計算速度［4］。

本文從2 個層面對算法的實現(xiàn)過程進(jìn)行優(yōu)化:①使用合適的路網(wǎng)表示方法，降低路網(wǎng)規(guī)模，節(jié)約計算時間;②使用新的矩形區(qū)域限定模型，減少算法搜索的節(jié)點(diǎn)和路段，提高最優(yōu)路徑選擇效率。

2.2 運(yùn)輸路徑網(wǎng)絡(luò)構(gòu)建

運(yùn)輸路徑網(wǎng)絡(luò)是最優(yōu)路徑選擇的基礎(chǔ)和對象，要實現(xiàn)算法搜索，首先要把路徑網(wǎng)絡(luò)抽象為圖論理論中的拓?fù)鋱D，然后將其轉(zhuǎn)化為計算機(jī)能夠識別的信息，以合理的結(jié)構(gòu)存儲起來。

路網(wǎng)通常用賦權(quán)有向圖來表示，針對道路交通網(wǎng)絡(luò)的實際情況，本文采用二次讀入邊數(shù)據(jù)方法來建立路網(wǎng)［5］。

2.2.1 支點(diǎn)到支點(diǎn)的網(wǎng)絡(luò)

按照連接邊的數(shù)量，可以將路網(wǎng)中的節(jié)點(diǎn)分為2 類:中間站點(diǎn)(連接2 條邊)和支點(diǎn)(連接3 條及3 條以上邊)。首先把中間站點(diǎn)刪除，只保留支點(diǎn)，支點(diǎn)之間的路段權(quán)值進(jìn)行相加(如圖1 所示)。

圖1 運(yùn)輸路徑網(wǎng)絡(luò)

2.2.2 中間點(diǎn)起止的網(wǎng)絡(luò)

中間節(jié)點(diǎn)作為源點(diǎn)或目標(biāo)點(diǎn)，可以從數(shù)據(jù)庫中查詢該點(diǎn)到所在邊2 個端點(diǎn)的距離，暫時刪除這條邊，然后增加1 個站點(diǎn)vk及2 條邊(vk，vi)和(vk，vj)，邊長等于該站點(diǎn)到這2 個端點(diǎn)的距離。

2.3 應(yīng)用矩形搜索區(qū)域處理搜索范圍

傳統(tǒng)Dijkstra 算法計算過程中，搜索區(qū)域基本是以起始點(diǎn)為原點(diǎn)、起始點(diǎn)與目標(biāo)點(diǎn)的歐式距離為半徑的圓，如圖2 中的圓。s、t分別為起始點(diǎn)和目標(biāo)點(diǎn)，這樣遍歷了太多不必要的節(jié)點(diǎn)和邊。

圖2 限制搜索區(qū)域路徑算法的比較示意

Nordbeck 等［6］提出了橢圓限制搜索區(qū)域算法，其基本思想是將構(gòu)成路徑的節(jié)點(diǎn)限制在1 個橢圓區(qū)域中，假設(shè)路網(wǎng)中的1 個節(jié)點(diǎn)n到起始點(diǎn)s和目標(biāo)點(diǎn)t的直線距離分別為|sn?|、|tn?|(sn、tn分別為節(jié)點(diǎn)n到起始點(diǎn)和目標(biāo)點(diǎn)的連線)，將節(jié)點(diǎn)是否在限制區(qū)域中的判斷條件寫成|sn?| + |tn?|≤MD，正好形成一個以s、t為焦點(diǎn)，以MD為長軸的橢圓，如圖2 中的橢圓。進(jìn)行路徑選擇時，橢圓外的節(jié)點(diǎn)不予考慮，這樣就大幅度縮小了搜索規(guī)模，但是計算時需要執(zhí)行大量的乘積與開方來判斷節(jié)點(diǎn)是否在橢圓內(nèi)，占用時間較多。針對橢圓限制搜索區(qū)域算法效率不高的缺點(diǎn)，陸鋒等［7］提出矩形限制搜索區(qū)域算法，在橢圓搜索的基礎(chǔ)上，求出橢圓的最小包含矩形，如圖2 中的較大矩形。判斷新擴(kuò)展出的節(jié)點(diǎn)是否落在限制搜索區(qū)域，只需將節(jié)點(diǎn)坐標(biāo)與矩形邊界進(jìn)行比較，避免了橢圓算法中大量的乘積和開方計算，效率更高。

在圖2 中對給定2 節(jié)點(diǎn)進(jìn)行最短路徑搜索時，從起始點(diǎn)s到目標(biāo)點(diǎn)t的連線方向基本代表了最短路徑的走向，以此推測，最短路徑基本在2 節(jié)點(diǎn)連線的兩側(cè)。因此，可以將搜索區(qū)域進(jìn)一步縮小，限制在以st為對角線的矩形中，如圖2 中的較小矩形。如果2 節(jié)點(diǎn)附近出現(xiàn)短距離的反向路徑，即在線段st外，沿st或ts延長線方向的路徑(在現(xiàn)實情況中表現(xiàn)為車輛為駛?cè)牒线m車道所選擇的道路)，此時最短路徑顯然不會落在小矩形區(qū)域，這時以橢圓的最小包含矩形為限制搜索區(qū)域來進(jìn)行搜索。

建立路網(wǎng)之后，經(jīng)過路徑網(wǎng)絡(luò)預(yù)處理，選擇合理的數(shù)據(jù)存儲結(jié)構(gòu)，限制搜索區(qū)域來約束節(jié)點(diǎn)搜索范圍，并恰當(dāng)?shù)刂贫ㄋ阉鞑呗?，利用Dijkstra 算法對最優(yōu)路徑進(jìn)行搜索。整個算法的流程如圖3所示。

圖3 算法流程

3 模擬仿真分析

為驗證算法的實用性和有效性，以鄭州基地物資運(yùn)輸為背景，利用計算機(jī)軟件平臺進(jìn)行仿真實驗。通過實際調(diào)查與查詢資料，得到鄭州基地周邊部分公路線路簡圖和相關(guān)數(shù)據(jù)，線路圖如圖4所示。

現(xiàn)有一批物資，需要從鄭州基地運(yùn)送到周口市，從線路圖中可以看出，備選路徑共有10 條。利用本文設(shè)計算法搜索最優(yōu)路徑，限制搜索區(qū)域并構(gòu)建路網(wǎng)。分別用數(shù)字1 ～10 代表鄭州、謝莊鎮(zhèn)、開封、陳留鎮(zhèn)、禹州、通許縣、許昌、西華營鎮(zhèn)、漯河、周口，路網(wǎng)如圖5 所示。

應(yīng)動 Matlab (實驗使用版本為 Matlab7.12.0 R2011a，操作系統(tǒng)為Windows XP，32 位)，按圖3 算法進(jìn)行計算，得到鄭州到周口的最優(yōu)路徑為鄭州—謝莊鎮(zhèn)—陳留鎮(zhèn)—通許縣—西華營鎮(zhèn)—周口。

圖4 部分公路線路

圖5 鄭州—周口路網(wǎng)結(jié)構(gòu)

4 結(jié) 論

本文根據(jù)國家科技支撐計劃項目“特種運(yùn)輸規(guī)劃組織與監(jiān)控技術(shù)研究”關(guān)于公路運(yùn)輸路徑規(guī)劃方案的提出，通過對傳統(tǒng)Dijkstra 算法基于單一權(quán)值的特點(diǎn)進(jìn)行拓展，使之能夠解決軍事運(yùn)輸多約束路徑選擇問題。從實驗仿真結(jié)果可以看出，算法簡化了路網(wǎng)結(jié)構(gòu)，縮小了搜索規(guī)模，搜索時間基本能夠滿足實際需要。

［1］ 向冬梅，陳樹輝.基于動態(tài)交通的最短時間路徑規(guī)劃方法研究［J］.微計算機(jī)信息，2012，28(9):317-319.

［2］ 廖建軍.基于道路交通網(wǎng)絡(luò)的多約束最優(yōu)路徑算法的研究［D］.南京:南京理工大學(xué)，2009.

［3］ 阮潔，鐘寶榮.Dijkstra 算法在物流配送運(yùn)輸中的最短路徑優(yōu)化研究［J］. 計算機(jī)光盤軟件及應(yīng)用，2013，16(15):42-44.

［4］ 王兆南.基于Dijkstra 算法改進(jìn)的海量數(shù)據(jù)最優(yōu)路徑計算方法研究與實現(xiàn)［J］.測繪通報，2012(9):32-37.

［5］ 楊斌，魏佳. 鐵路超限貨物最短運(yùn)輸徑路查詢系統(tǒng)的研究［J］.鐵道運(yùn)營技術(shù)，2010，16(2):1-7.

［6］ Nordebck S，Rystedt B. Computer Cartography Shortest Route Programs［M］.Sweden:The Royal University of Lund，2003.

［7］ 陸鋒，盧冬梅，崔偉宏. 交通網(wǎng)絡(luò)限制搜索區(qū)域時間最短路徑算法［J］.中國圖像圖形學(xué)報，1999，4(10):849-853.