基于Dijkstra 算法的多約束軍事運輸最優路徑研究

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

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

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

1 路徑選擇模型建立

1.1 Dijkstra 算法描述

Dijkstra 算法使用廣度優先搜索解決非負權有向圖的單源點最短路徑問題，算法以源點為中心向外層層擴展遍歷，直到目標點為止，按路徑長度遞增次序產生最短路徑。

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

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

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

(3)以標記節點k為中間點，檢驗k到其直接相連的未標記節點i的距離，并設置

若di改變，則pi=k。

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

(5)如果所有節點都已標記，包含于M，則算法結束;否則，記k=j，轉到步驟(3)再重復進行。

1.2 多約束條件定義

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

記d(x，y)表示路段(x，y)的約束權值，則對于路徑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)為凹性約束，例如道路限重標準。

通常可將不同約束類型轉化為加法約束，以實現計算的簡單化。對于凹性約束，在進行最優路徑選擇之前，將不滿足最小權值要求的路段刪除，例如公路運輸中，某一路段對車輛進行限重，并且限制重量低于裝載貨物重量，那么在選擇路徑時不必考慮該路段;對于乘法約束，將各路段約束權值取對數變換，變為加法約束，使得在進行路徑選擇時，一般只考慮加法約束。

1.3 路徑選擇多約束模型

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

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

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

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

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

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

即一條路徑的限重標準為組成該路徑的所有路段限重標準的最小值。

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

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

由于pk≤1，等式兩邊均為負數。兩邊同乘-1，得

根據對數函數的性質可知，P取最大值等價于P*取最小值，符合Dijkstra 算法搜索最小權值的原理和邊權值為非負數的要求。

1.4 多約束條件向單一權值的轉換

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

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

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

2 拓展Dijkstra 算法的實現

2.1 傳統求解Dijkstra 算法的不足

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

本文從2 個層面對算法的實現過程進行優化:①使用合適的路網表示方法，降低路網規模，節約計算時間;②使用新的矩形區域限定模型，減少算法搜索的節點和路段，提高最優路徑選擇效率。

2.2 運輸路徑網絡構建

運輸路徑網絡是最優路徑選擇的基礎和對象，要實現算法搜索，首先要把路徑網絡抽象為圖論理論中的拓撲圖，然后將其轉化為計算機能夠識別的信息，以合理的結構存儲起來。

路網通常用賦權有向圖來表示，針對道路交通網絡的實際情況，本文采用二次讀入邊數據方法來建立路網［5］。

2.2.1 支點到支點的網絡

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

圖1 運輸路徑網絡

2.2.2 中間點起止的網絡

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

2.3 應用矩形搜索區域處理搜索范圍

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

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

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

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

建立路網之后，經過路徑網絡預處理，選擇合理的數據存儲結構，限制搜索區域來約束節點搜索范圍，并恰當地制定搜索策略，利用Dijkstra 算法對最優路徑進行搜索。整個算法的流程如圖3所示。

圖3 算法流程

3 模擬仿真分析

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

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

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

圖4 部分公路線路

圖5 鄭州—周口路網結構

4 結 論

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

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

［2］ 廖建軍.基于道路交通網絡的多約束最優路徑算法的研究［D］.南京:南京理工大學，2009.

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

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

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

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

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