楊文索　姚金凱　王　耀

摘要：軍事運(yùn)輸路徑優(yōu)化研究，是軍事物流系統(tǒng)優(yōu)化的重要內(nèi)容，特別是在運(yùn)輸網(wǎng)絡(luò)密度程度比較高的戰(zhàn)場(chǎng)，合理選擇運(yùn)輸路徑，可以提高軍事運(yùn)輸?shù)陌踩浴r(shí)效性和經(jīng)濟(jì)性，從而能夠極大地增強(qiáng)軍事運(yùn)輸?shù)谋Ｕ闲逝c效益。文章立足戰(zhàn)場(chǎng)實(shí)際，分析了戰(zhàn)時(shí)交通網(wǎng)絡(luò)的特征，在綜合權(quán)值基礎(chǔ)上運(yùn)用經(jīng)典的Di jkstra算法，探尋最優(yōu)路徑。

關(guān)鍵詞：戰(zhàn)時(shí)；軍事物流；路徑優(yōu)化

中圖分類號(hào)：U116.2文獻(xiàn)標(biāo)識(shí)碼：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引言

軍事物流的組織實(shí)施過(guò)程，既是一個(gè)創(chuàng)造軍事效益的過(guò)程，也是一個(gè)創(chuàng)造經(jīng)濟(jì)效益的過(guò)程。為使軍事物流能夠提供最佳的價(jià)值效能，必須保證在實(shí)施軍事物流的各階段、各環(huán)節(jié)的實(shí)施過(guò)程都達(dá)到最優(yōu)，從而保證軍事物流的過(guò)程通暢迅速，適應(yīng)軍事物流組織優(yōu)化的要求。所以，要運(yùn)用科學(xué)的方法，選擇合理的運(yùn)輸方式，確定最佳的運(yùn)輸路線，制定最優(yōu)的運(yùn)輸計(jì)劃，力求以最低的運(yùn)輸成本、最快的運(yùn)輸速度、最少的運(yùn)輸時(shí)間、最短的運(yùn)輸距離，達(dá)到最佳效果、最高效率和最大能力，使軍事運(yùn)輸各個(gè)過(guò)程、各個(gè)階段和各個(gè)環(huán)節(jié)都達(dá)到合理優(yōu)化。其中，運(yùn)輸路徑優(yōu)化是制定運(yùn)輸計(jì)劃的基礎(chǔ)，也是當(dāng)前軍事物流領(lǐng)域研究的熱點(diǎn)問(wèn)題。目前，邊權(quán)值為常量的靜態(tài)交通網(wǎng)絡(luò)最短路問(wèn)題研究已非常成熟，這些研究多少與戰(zhàn)時(shí)的多權(quán)值的動(dòng)態(tài)交通運(yùn)輸網(wǎng)絡(luò)有些不符。本文就是從戰(zhàn)場(chǎng)的實(shí)際情況出發(fā)，運(yùn)用經(jīng)典的Di jkstra算法，求解多目標(biāo)、多約束的交通運(yùn)輸網(wǎng)絡(luò)的路徑優(yōu)化問(wèn)題。

1戰(zhàn)時(shí)交通網(wǎng)絡(luò)的路徑優(yōu)化模型

戰(zhàn)時(shí)條件下交通網(wǎng)絡(luò)路徑優(yōu)化有其自身的特殊性：一是運(yùn)輸路徑的優(yōu)化，在達(dá)到軍事目標(biāo)的同時(shí)，相應(yīng)的也要注意經(jīng)濟(jì)效益的提高，不但要求運(yùn)行時(shí)間最短，運(yùn)行速度最快，而且還要求運(yùn)費(fèi)最省，追求的目標(biāo)體現(xiàn)在綜合性上。二是影響路徑選擇的因素和約束條件大大增多，具有多邊權(quán)、多因素、多要求的特征；三是由于戰(zhàn)時(shí)交通環(huán)境條件的惡劣性，導(dǎo)致交通網(wǎng)絡(luò)的結(jié)構(gòu)特征、功能不斷發(fā)生變化，路網(wǎng)動(dòng)態(tài)特征更為明顯。

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

2戰(zhàn)時(shí)交通網(wǎng)絡(luò)路徑優(yōu)化算法分析

2.1Di jkstra算法簡(jiǎn)介

Di jkstra算法將路網(wǎng)節(jié)點(diǎn)分為未標(biāo)記點(diǎn)、臨時(shí)標(biāo)記點(diǎn)和永久標(biāo)記點(diǎn)三種。算法過(guò)程就將路網(wǎng)所有節(jié)點(diǎn)初始化為未標(biāo)記點(diǎn)，搜索過(guò)程中把與起點(diǎn)相連通的節(jié)點(diǎn)標(biāo)記為臨時(shí)標(biāo)記點(diǎn)，每次循環(huán)都是從臨時(shí)標(biāo)記點(diǎn)中搜索出距起點(diǎn)權(quán)值最小的節(jié)點(diǎn)作為永久標(biāo)記點(diǎn)，直至找到終點(diǎn)成為永久標(biāo)記點(diǎn)來(lái)結(jié)束算法。其算法的基本思想，就是設(shè)置永久標(biāo)記點(diǎn)集合并不斷做貪心選擇來(lái)擴(kuò)充這個(gè)集合，將節(jié)點(diǎn)V插入L中當(dāng)且僅當(dāng)從起點(diǎn)Vs到v的最短路徑長(zhǎng)度已知。執(zhí)行過(guò)程中，每一節(jié)點(diǎn)Vi都對(duì)應(yīng)一個(gè)兩元組di，pi，其中di是從起點(diǎn)Vs到Vi的最短路的長(zhǎng)度，pi則是從Vs到Vi的最短路徑中Vi的前一點(diǎn)。

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

①?gòu)钠瘘c(diǎn)開(kāi)始，令d1=0，di=∞，pi為空，L={Vs}，并令k=1。

②考察所有Vk∈L到與其直接連接的未標(biāo)記點(diǎn)vi的距離，并設(shè)置，di=min{di,dk+Wki}其中Wki是從Vk到Vi的權(quán)重。

③從所有未標(biāo)記的節(jié)點(diǎn)中選取di最小的節(jié)點(diǎn)Vi，將其設(shè)置為已標(biāo)記節(jié)點(diǎn)，即L=L+{Vi}。

④從已標(biāo)記的節(jié)點(diǎn)中找到與Vi直接連接的節(jié)點(diǎn)Vj*，作為Vi的前一點(diǎn)，即pi=Vj*。

⑤如果Vn已標(biāo)記，則算法終止；否則，令k=i，轉(zhuǎn)入②。

2.2模型轉(zhuǎn)化求解

首先確定運(yùn)輸線路上的幾個(gè)最重要的邊權(quán)，在綜合考慮多個(gè)邊權(quán)的基礎(chǔ)上，將每條運(yùn)輸線路的情況用線路矩陣D表示。假定：Tij、Cij、Qij、Dij分別代表第i點(diǎn)到j(luò)點(diǎn)之間線路的運(yùn)行時(shí)間、運(yùn)輸費(fèi)用、交通條件惡劣程度和運(yùn)輸風(fēng)險(xiǎn)。

A= TCQD T C QDi

對(duì)線路矩陣進(jìn)行標(biāo)準(zhǔn)化處理。令T＝max{Tij}，C=max{Cij}，Q＝max{Qij}，D=max{Dij}，則可得到標(biāo)準(zhǔn)化矩陣。

=i

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

將權(quán)系數(shù)矩陣與標(biāo)準(zhǔn)化矩陣相乘，便可得到各線路的綜合權(quán)B矩陣。

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

確定了運(yùn)輸線路的綜合權(quán)之后，就將多權(quán)值的交通網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題轉(zhuǎn)化為確定最小綜合權(quán)的單權(quán)運(yùn)輸線路優(yōu)化問(wèn)題。因此，可運(yùn)用經(jīng)典的Di jkstra算法探尋其最優(yōu)運(yùn)輸路徑。

2.3含特殊要求的運(yùn)輸路徑優(yōu)化算法

對(duì)于必經(jīng)點(diǎn)和禁行路段的處理問(wèn)題，算法的基本思想是以運(yùn)輸網(wǎng)絡(luò)中的必經(jīng)點(diǎn)為界，將原運(yùn)輸網(wǎng)絡(luò)分成兩個(gè)子網(wǎng)絡(luò)，必經(jīng)點(diǎn)作為前一運(yùn)輸子網(wǎng)絡(luò)的終點(diǎn)，同時(shí)作為后一運(yùn)輸子網(wǎng)絡(luò)的起點(diǎn)，分別求算兩個(gè)運(yùn)輸子網(wǎng)絡(luò)的最短路徑，兩個(gè)子網(wǎng)絡(luò)的最短路徑相連，便是經(jīng)過(guò)該必經(jīng)點(diǎn)運(yùn)輸網(wǎng)絡(luò)的最優(yōu)路徑。

對(duì)于含有必經(jīng)路段的運(yùn)輸路徑優(yōu)化問(wèn)題，算法的基本思想是將必經(jīng)路段看作一個(gè)點(diǎn)，這樣就簡(jiǎn)化為必經(jīng)點(diǎn)問(wèn)題。以必經(jīng)路段為界，將原運(yùn)輸網(wǎng)絡(luò)分成兩個(gè)子網(wǎng)絡(luò)，必經(jīng)路段的起點(diǎn)作為前一運(yùn)輸子網(wǎng)絡(luò)的終點(diǎn)，必經(jīng)路段的終點(diǎn)作為后一運(yùn)輸子網(wǎng)絡(luò)的起點(diǎn)，分別求算兩個(gè)運(yùn)輸子網(wǎng)絡(luò)的最短路徑，兩個(gè)子網(wǎng)絡(luò)的最短路徑相連，便是經(jīng)過(guò)該必經(jīng)路段運(yùn)輸網(wǎng)絡(luò)的最優(yōu)路徑。

對(duì)于含有禁行點(diǎn)或禁行路段運(yùn)輸網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題，算法的基本思想是將禁行點(diǎn)或路段從原運(yùn)輸網(wǎng)絡(luò)中去掉，再探尋原運(yùn)輸網(wǎng)絡(luò)的最優(yōu)路徑。

另外，戰(zhàn)區(qū)運(yùn)輸路徑優(yōu)化還會(huì)遇到為部隊(duì)提供多條最優(yōu)運(yùn)輸路徑問(wèn)題，對(duì)于這一問(wèn)題，算法的基本思想是首先運(yùn)用經(jīng)典最短路算法，求出一條最優(yōu)路徑，然后通過(guò)消除替換最優(yōu)路徑中的部分路段以尋求備選路徑。選擇的消除路段可以考慮戰(zhàn)時(shí)易遭到敵人破壞的路段，或交通不便的路段等。這一算法的突出優(yōu)點(diǎn)是它的簡(jiǎn)便性——備選路徑可以像最優(yōu)路徑一樣很容易被確定出來(lái)。

3實(shí)例分析

以戰(zhàn)時(shí)條件下東南沿海某一公路網(wǎng)段為例：

有一批保障物資要從戰(zhàn)役后方基地V1（起點(diǎn)）經(jīng)過(guò)此公路運(yùn)輸網(wǎng)絡(luò)運(yùn)輸?shù)角把匦枨簏c(diǎn)V7（終點(diǎn)）。在此公路網(wǎng)絡(luò)中，V2～V5公路段中唯一可通行的橋梁已被敵方破壞，短時(shí)間內(nèi)已經(jīng)無(wú)法通車。V6是此網(wǎng)絡(luò)運(yùn)輸點(diǎn)的重要的指揮保障點(diǎn)，所有的運(yùn)輸物資都要在此通過(guò)，然后運(yùn)往V7。因此，V2～V5路段已成禁行路段，在運(yùn)輸網(wǎng)絡(luò)優(yōu)化中可以去除。而V6是必須要經(jīng)過(guò)的節(jié)點(diǎn)（如圖1所示）。

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

A=

（2）對(duì)線路矩陣進(jìn)行標(biāo)準(zhǔn)化處理。可知T＝max{Tij}=13，C=max{Cij}=12，Q＝max{Qij}=14, D=max{Dij}=14, 則可得到標(biāo)準(zhǔn)化矩陣;

=

對(duì)于運(yùn)行時(shí)間、運(yùn)輸費(fèi)用、交通條件惡劣程度和運(yùn)輸風(fēng)險(xiǎn)影響運(yùn)輸線路決策的重要程度，根據(jù)運(yùn)輸決策指揮人員的主觀意圖并結(jié)合專家評(píng)分，得出權(quán)系數(shù)矩陣為M＝｛MT,MC,MQ,WD｝={0.2,0.1,0.3,0.4}。