戰區內戰時軍事運輸路徑優化研究

楊文索　姚金凱　王　耀

摘要：軍事運輸路徑優化研究，是軍事物流系統優化的重要內容，特別是在運輸網絡密度程度比較高的戰場，合理選擇運輸路徑，可以提高軍事運輸的安全性、時效性和經濟性，從而能夠極大地增強軍事運輸的保障效率與效益。文章立足戰場實際，分析了戰時交通網絡的特征，在綜合權值基礎上運用經典的Di jkstra算法，探尋最優路徑。

關鍵詞：戰時；軍事物流；路徑優化

中圖分類號：U116.2文獻標識碼：A

Abstract: The research of military transportation route optimization is an vital part of military logistics optimization. Especially in war field which has dense transportation network, choosing transportion route reasonably can improve military transportation's timeliness, safety and economy, for which strengthening supportability rate and benefit. The thesis is based upon practice of war field, analyzing the characteristics of transportation network in war, using classical Dijkstra arithmetic on the basis of integrate parameter poporation, exploring the optimal route.

Key words: wartime；military logistics；optimal path

0引言

軍事物流的組織實施過程，既是一個創造軍事效益的過程，也是一個創造經濟效益的過程。為使軍事物流能夠提供最佳的價值效能，必須保證在實施軍事物流的各階段、各環節的實施過程都達到最優，從而保證軍事物流的過程通暢迅速，適應軍事物流組織優化的要求。所以，要運用科學的方法，選擇合理的運輸方式，確定最佳的運輸路線，制定最優的運輸計劃，力求以最低的運輸成本、最快的運輸速度、最少的運輸時間、最短的運輸距離，達到最佳效果、最高效率和最大能力，使軍事運輸各個過程、各個階段和各個環節都達到合理優化。其中，運輸路徑優化是制定運輸計劃的基礎，也是當前軍事物流領域研究的熱點問題。目前，邊權值為常量的靜態交通網絡最短路問題研究已非常成熟，這些研究多少與戰時的多權值的動態交通運輸網絡有些不符。本文就是從戰場的實際情況出發，運用經典的Di jkstra算法，求解多目標、多約束的交通運輸網絡的路徑優化問題。

1戰時交通網絡的路徑優化模型

戰時條件下交通網絡路徑優化有其自身的特殊性：一是運輸路徑的優化，在達到軍事目標的同時，相應的也要注意經濟效益的提高，不但要求運行時間最短，運行速度最快，而且還要求運費最省，追求的目標體現在綜合性上。二是影響路徑選擇的因素和約束條件大大增多，具有多邊權、多因素、多要求的特征；三是由于戰時交通環境條件的惡劣性，導致交通網絡的結構特征、功能不斷發生變化，路網動態特征更為明顯。

戰時條件下的軍事運輸路徑優化僅考慮路網中的單邊權是不夠的，路徑的優化應該受到多邊權的影響。路邊權應該是和運輸時間、交通條件（如交通流量、運輸距離）、道路條件（如道路類型、道路等級、道路通行能力等）、運輸風險（氣候條件、受敵威脅程度和隱蔽程度）、運輸經濟性（運費、燃料消耗、后勤保障消耗）等多方面的限制因素有關，與之同時，還要貫徹落實上級首長或運輸指揮決策者的主觀意圖，在綜合各種影響因素的基礎上才能做出路徑優化決策。因此，需要綜合考慮上述各方面因素對路徑優化的影響，并采用某種科學方法將這些因素加以集成，進而再確定出最優運輸路徑。為此，我們提出了運輸線路綜合權的概念，既綜合考慮了戰時影響路徑優化的各種因素，又適合運用經典的Di jkstra算法進行求解。

2戰時交通網絡路徑優化算法分析

2.1Di jkstra算法簡介

Di jkstra算法將路網節點分為未標記點、臨時標記點和永久標記點三種。算法過程就將路網所有節點初始化為未標記點，搜索過程中把與起點相連通的節點標記為臨時標記點，每次循環都是從臨時標記點中搜索出距起點權值最小的節點作為永久標記點，直至找到終點成為永久標記點來結束算法。其算法的基本思想，就是設置永久標記點集合并不斷做貪心選擇來擴充這個集合，將節點V插入L中當且僅當從起點Vs到v的最短路徑長度已知。執行過程中，每一節點Vi都對應一個兩元組di，pi，其中di是從起點Vs到Vi的最短路的長度，pi則是從Vs到Vi的最短路徑中Vi的前一點。

用Di jkstra算法求解從起點Vs到終點Vn的最短路徑的具體步驟：

①從起點開始，令d1=0，di=∞，pi為空，L={Vs}，并令k=1。

②考察所有Vk∈L到與其直接連接的未標記點vi的距離，并設置，di=min{di,dk+Wki}其中Wki是從Vk到Vi的權重。

③從所有未標記的節點中選取di最小的節點Vi，將其設置為已標記節點，即L=L+{Vi}。

④從已標記的節點中找到與Vi直接連接的節點Vj*，作為Vi的前一點，即pi=Vj*。

⑤如果Vn已標記，則算法終止；否則，令k=i，轉入②。

2.2模型轉化求解

首先確定運輸線路上的幾個最重要的邊權，在綜合考慮多個邊權的基礎上，將每條運輸線路的情況用線路矩陣D表示。假定：Tij、Cij、Qij、Dij分別代表第i點到j點之間線路的運行時間、運輸費用、交通條件惡劣程度和運輸風險。

A= TCQD T C QDi

對線路矩陣進行標準化處理。令T＝max{Tij}，C=max{Cij}，Q＝max{Qij}，D=max{Dij}，則可得到標準化矩陣。

=i

根據運輸決策指揮人員的主觀意圖，確定權系數矩陣為M＝｛MT,MC,MQ,MD｝，其中MT+MC＋MQ+MD＝1，分別代表運輸決策指揮人員認為運行時間、運輸費用、通行能力與安全系數影響運輸線路決策的重要程度。

將權系數矩陣與標準化矩陣相乘，便可得到各線路的綜合權B矩陣。

B=MMMM=B,B,…,B i＜j

確定了運輸線路的綜合權之后，就將多權值的交通網絡路徑優化問題轉化為確定最小綜合權的單權運輸線路優化問題。因此，可運用經典的Di jkstra算法探尋其最優運輸路徑。

2.3含特殊要求的運輸路徑優化算法

對于必經點和禁行路段的處理問題，算法的基本思想是以運輸網絡中的必經點為界，將原運輸網絡分成兩個子網絡，必經點作為前一運輸子網絡的終點，同時作為后一運輸子網絡的起點，分別求算兩個運輸子網絡的最短路徑，兩個子網絡的最短路徑相連，便是經過該必經點運輸網絡的最優路徑。

對于含有必經路段的運輸路徑優化問題，算法的基本思想是將必經路段看作一個點，這樣就簡化為必經點問題。以必經路段為界，將原運輸網絡分成兩個子網絡，必經路段的起點作為前一運輸子網絡的終點，必經路段的終點作為后一運輸子網絡的起點，分別求算兩個運輸子網絡的最短路徑，兩個子網絡的最短路徑相連，便是經過該必經路段運輸網絡的最優路徑。

對于含有禁行點或禁行路段運輸網絡路徑優化問題，算法的基本思想是將禁行點或路段從原運輸網絡中去掉，再探尋原運輸網絡的最優路徑。

另外，戰區運輸路徑優化還會遇到為部隊提供多條最優運輸路徑問題，對于這一問題，算法的基本思想是首先運用經典最短路算法，求出一條最優路徑，然后通過消除替換最優路徑中的部分路段以尋求備選路徑。選擇的消除路段可以考慮戰時易遭到敵人破壞的路段，或交通不便的路段等。這一算法的突出優點是它的簡便性——備選路徑可以像最優路徑一樣很容易被確定出來。

3實例分析

以戰時條件下東南沿海某一公路網段為例：

有一批保障物資要從戰役后方基地V1（起點）經過此公路運輸網絡運輸到前沿需求點V7（終點）。在此公路網絡中，V2～V5公路段中唯一可通行的橋梁已被敵方破壞，短時間內已經無法通車。V6是此網絡運輸點的重要的指揮保障點，所有的運輸物資都要在此通過，然后運往V7。因此，V2～V5路段已成禁行路段，在運輸網絡優化中可以去除。而V6是必須要經過的節點（如圖1所示）。

（1）如果各權值取值范圍為1～15，圖1利用加乘同余法隨機生成各段線路的權值，可以得到線路矩陣：

A=

（2）對線路矩陣進行標準化處理。可知T＝max{Tij}=13，C=max{Cij}=12，Q＝max{Qij}=14, D=max{Dij}=14, 則可得到標準化矩陣;

=

對于運行時間、運輸費用、交通條件惡劣程度和運輸風險影響運輸線路決策的重要程度，根據運輸決策指揮人員的主觀意圖并結合專家評分，得出權系數矩陣為M＝｛MT,MC,MQ,WD｝={0.2,0.1,0.3,0.4}。