基于多模式時間最短的公鐵聯(lián)合軍事運(yùn)輸路徑優(yōu)化

吳 洋，張艷萍，李遂汝

(軍事交通學(xué)院國防交通系，天津300161)

新時期，在我軍質(zhì)量效能型建設(shè)思想的指導(dǎo)下，軍事運(yùn)輸路徑研究已經(jīng)受到作戰(zhàn)部門的廣泛重視，新提出的聯(lián)合作戰(zhàn)構(gòu)想的關(guān)鍵環(huán)節(jié)就是聯(lián)合投送能力。目前，對成建制部隊(duì)“人裝一體”聯(lián)合軍事運(yùn)輸研究較少，使得現(xiàn)有的軍事運(yùn)輸路徑優(yōu)化模型與實(shí)際軍事運(yùn)輸任務(wù)需求存有明顯差距［1－4］，所以亟待建立貼近成建制部隊(duì)“人裝一體”公鐵聯(lián)合軍事運(yùn)輸?shù)穆窂絻?yōu)化模型。由于時間是部隊(duì)輸送的重要約束條件，而部隊(duì)能否在規(guī)定的時限范圍內(nèi)到達(dá)指定地域又是影響作戰(zhàn)進(jìn)程并事關(guān)戰(zhàn)爭結(jié)局的重要因素。基于此，本文在已構(gòu)建的多模式交通網(wǎng)絡(luò)圖基礎(chǔ)上［5］，結(jié)合軍事運(yùn)輸實(shí)際，建立以時間最短為目標(biāo)的公鐵聯(lián)合軍事運(yùn)輸路徑優(yōu)化模型，并采用遺傳算法進(jìn)行求解。

1 問題描述與條件假設(shè)

1.1 問題描述

西部某戰(zhàn)區(qū)由于地域沖突加劇，為防止沖突升級、事態(tài)擴(kuò)大、領(lǐng)土安全受到威脅，某部接到敵情通報和上級下達(dá)的部隊(duì)輸送命令，于輸送時限t限時間內(nèi)，從駐地O輸送至目的區(qū)域D，擔(dān)負(fù)自衛(wèi)反擊作戰(zhàn)任務(wù)。根據(jù)當(dāng)?shù)亟煌ú季值膶?shí)際情況，只能選取鐵路和公路兩種運(yùn)輸保障方式，實(shí)施“人裝一體”運(yùn)輸。鑒于此次部隊(duì)輸送任務(wù)緊急且立足于國土范圍之內(nèi)，故暫不考慮運(yùn)輸費(fèi)用和運(yùn)輸警戒問題。

1.2 條件假設(shè)

由于實(shí)際軍事運(yùn)輸涉及面較廣、內(nèi)容較多、要求較嚴(yán)格，為了便于探討建模方法，故將實(shí)際情況進(jìn)行一定的合理化假設(shè)，假設(shè)條件如下。

(1)設(shè)定轉(zhuǎn)換次數(shù)。若首選公路運(yùn)輸，則公鐵轉(zhuǎn)換不多于兩次。若首選鐵路運(yùn)輸，則公鐵轉(zhuǎn)換不多于一次。

(2)抽象轉(zhuǎn)換點(diǎn)。鐵路網(wǎng)中車站作為轉(zhuǎn)換點(diǎn)也代表該車站所在城市，公路網(wǎng)中城市作為轉(zhuǎn)換點(diǎn)也代表城市內(nèi)的鐵路車站。

(3)區(qū)域化起始點(diǎn)。起始點(diǎn)根據(jù)輸送要求，既可以代表城鎮(zhèn)也表示該城鎮(zhèn)所在區(qū)域。

(4)城市內(nèi)到鐵路車站的公路運(yùn)輸區(qū)段忽略不計(jì)。

(5)高速公路等收費(fèi)站通道建筑限界滿足重裝備通行需求。

2 建立數(shù)學(xué)模型

2.1 多模式交通網(wǎng)絡(luò)［5］

運(yùn)用多模式網(wǎng)絡(luò)建模和圖論的相關(guān)理論與方法，建立公鐵聯(lián)合軍事運(yùn)輸網(wǎng)絡(luò)圖G(V，T，E，M)，包含鐵路子網(wǎng)圖Gu(Tn，Eu，Mn)和公路子網(wǎng)圖Gg(V，T’n，Eg，M’n)，即 G={Gu，Gg}。某戰(zhàn)區(qū)公鐵聯(lián)合軍事運(yùn)輸網(wǎng)絡(luò)示意如圖1所示。

圖1 某戰(zhàn)區(qū)公鐵聯(lián)合軍事運(yùn)輸網(wǎng)絡(luò)示意

2.2 鐵路目標(biāo)函數(shù)

鐵路軍事運(yùn)輸時間消耗主要包括列車運(yùn)行時間、中轉(zhuǎn)換乘時間和等待發(fā)車時間。設(shè)列車運(yùn)行時間為t運(yùn)，也是部隊(duì)在鐵路上的機(jī)動時間;中轉(zhuǎn)換乘時間為t中，僅指鐵路轉(zhuǎn)換到公路的裝卸載時間(包括部隊(duì)裝備裝卸載和人員乘降時間)，表示為;等待發(fā)車時間為t待，即指聯(lián)合檢查和人員乘載完畢后直到列車開車時止所消耗的時間(其中包括多梯隊(duì)連續(xù)裝載的間隔時間和梯隊(duì)序列發(fā)車的等待時間)，表示為tTi。

設(shè) t鐵為鐵路時間目標(biāo)函數(shù):t鐵=t運(yùn)+t中+t待，即

2.3 公路目標(biāo)函數(shù)

公路軍事運(yùn)輸時間消耗主要包括公路輸送時間和中轉(zhuǎn)換乘時間。設(shè)為部隊(duì)公路機(jī)動的時間即公路運(yùn)輸?shù)倪\(yùn)行時間，由于公路網(wǎng)節(jié)點(diǎn)的特殊性，它包括錨泊點(diǎn)V和公路網(wǎng)轉(zhuǎn)換點(diǎn)，故而產(chǎn)生了4種輸送時間表示方式:第1種是從錨泊點(diǎn)Vi到錨泊點(diǎn)Vj的運(yùn)行時間;第2種是從錨泊點(diǎn)Vi到轉(zhuǎn)換點(diǎn)的運(yùn)行時間第3種是從轉(zhuǎn)換點(diǎn)到錨泊點(diǎn)Vi的運(yùn)行時間第4種是從轉(zhuǎn)換點(diǎn)到轉(zhuǎn)換點(diǎn)的運(yùn)行時間為公路轉(zhuǎn)換到鐵路裝卸載所消耗的中轉(zhuǎn)換乘時間

設(shè) t公為公路時間目標(biāo)函數(shù):t公=t＇運(yùn)+t＇中，即

2.4 公鐵聯(lián)合模型

根據(jù)路網(wǎng)的構(gòu)成方式為分層式網(wǎng)絡(luò)，故公鐵聯(lián)合模型是將鐵路時間目標(biāo)函數(shù)與公路時間目標(biāo)函數(shù)相結(jié)合，從而構(gòu)建復(fù)合網(wǎng)絡(luò)的時間目標(biāo)函數(shù)。

設(shè)t為公鐵聯(lián)合模型的時間目標(biāo)函數(shù):

即為

約束條件:

式中:t≤t限，為總時間約束，代表所有消耗時間不能超過輸送時限。∈{0，1}，為在鐵路子網(wǎng)內(nèi)兩個轉(zhuǎn)換點(diǎn)之間的路徑，當(dāng)約束為0時，表示此路徑不被選取，當(dāng)約束為1時，為通過此路徑。{0，1}，為在公路子網(wǎng)內(nèi)兩個錨泊點(diǎn)之間的路徑，當(dāng)約束為0時，表示此路徑不被選取，當(dāng)約束為1時，為通過此路徑。∈{0，1}為在公路子網(wǎng)內(nèi)錨泊點(diǎn)到轉(zhuǎn)換點(diǎn)的路徑，當(dāng)約束為0時，表示此路徑不被選取，當(dāng)約束為1時，為通過此路徑。∈{0，1}，為在公路子網(wǎng)內(nèi)轉(zhuǎn)換點(diǎn)到錨泊點(diǎn)的路徑，當(dāng)約束為0時，表示此路徑不被選取，當(dāng)約束為1時，為通過此路徑。∈{0，1}為在公路子網(wǎng)內(nèi)兩個轉(zhuǎn)換點(diǎn)之間的路徑，當(dāng)約束為0時，表示此路徑不被選取，當(dāng)約束為1時，為通過此路徑。∈{0，1}和∈{0，1}，為中轉(zhuǎn)換乘狀態(tài)，當(dāng)時表示在鐵路子網(wǎng)內(nèi)發(fā)生方式轉(zhuǎn)換;當(dāng)時表示在公路子網(wǎng)內(nèi)發(fā)生方式轉(zhuǎn)換;當(dāng)且表示不發(fā)生方式轉(zhuǎn)換。或，為保證內(nèi)部運(yùn)輸方式一致性的判斷條件，若且，則，否則，表示在轉(zhuǎn)換點(diǎn)Tj從鐵路子網(wǎng)轉(zhuǎn)換到公路子網(wǎng);同理，另一不等式表示在轉(zhuǎn)換點(diǎn)Ti從公路子網(wǎng)轉(zhuǎn)換到鐵路子網(wǎng)，保證各子網(wǎng)內(nèi)運(yùn)輸方式的一致性。當(dāng)，表示在公鐵聯(lián)合軍事運(yùn)輸網(wǎng)絡(luò)中，只發(fā)生一次方式轉(zhuǎn)換。

3 算法設(shè)計(jì)

3.1 染色體編碼

本文采用符號編碼方法。染色體的基因由轉(zhuǎn)換點(diǎn)集T和錨泊點(diǎn)集V的混合符號組成，其排列順序代表從出發(fā)點(diǎn)到目的點(diǎn)的路徑。

設(shè)路網(wǎng)的轉(zhuǎn)換點(diǎn)集合T中節(jié)點(diǎn)個數(shù)為n，錨泊點(diǎn)集合V中節(jié)點(diǎn)個數(shù)為m。染色體的基本位數(shù)為n+m，其基因構(gòu)成為:第1位設(shè)為出發(fā)點(diǎn)的符號“O”;緊接著是轉(zhuǎn)換點(diǎn)集T和錨泊點(diǎn)集V的混合符號節(jié)點(diǎn)，然后是目的點(diǎn)符號“D”。設(shè)染色體中從“O”到“D”的基因個數(shù)為(n+m+2)個，記為有效基因數(shù)。若除“O”和“D”兩個符號外，其余符號個數(shù)不足(n+m)個，則在符號“D”后補(bǔ)“0”，使基因總數(shù)保持為(n+m+2)個。確定染色體中的基因第1位必是符號“O”，最末端不為“0”的基因一定是目的點(diǎn)符號“D”，其他基因構(gòu)成只含有轉(zhuǎn)換點(diǎn)集T和錨泊點(diǎn)集V的混合符號。若基因中含有“0”基因，則表示有部分轉(zhuǎn)換點(diǎn)和錨泊點(diǎn)沒有出現(xiàn)在該染色體構(gòu)成的可行路徑范圍內(nèi)。

3.2 初始群體生成

根據(jù)染色體的編碼規(guī)則，已經(jīng)確定每個染色體基因中一定包含出發(fā)點(diǎn)符號“O”和目的點(diǎn)符號“D”的基因，每個染色體基因總數(shù)為(n+m+2)。若隨機(jī)改變?nèi)旧w個體內(nèi)除符號“O”和“D”外的其他有效基因序列，則將產(chǎn)生新的初始群體。首先通過檢驗(yàn)初始染色體個體，若出現(xiàn)讓染色體中兩個相鄰的基因生成的有效路徑數(shù)不足該路徑總數(shù)一半的情況，則剔除該染色體，繼續(xù)尋找符合條件的染色體個體;其次是將初始生成量的規(guī)模成倍增大，挑出在路徑上比較合理的個體添加到初始群體內(nèi)。

3.3 適應(yīng)度函數(shù)建立

適應(yīng)度函數(shù)由時間目標(biāo)函數(shù)的倒數(shù)構(gòu)成，即

3.4 染色體選擇

在此選用改進(jìn)的盤賭選擇法。面對新個體的選擇時，首先利用多選一的原則確保選擇出的下一代是在當(dāng)前代中的最佳個體，然后經(jīng)過盤賭方式選出其他適應(yīng)度較大的個體。假設(shè)初始群體的個體數(shù)為K，各染色體的適應(yīng)值為f1，f2，…，fK，則染色體所被選擇的概率為

3.5 染色體交叉

交叉運(yùn)算直接關(guān)系到下一代染色體的組成，對進(jìn)一步優(yōu)化操作具有關(guān)鍵性作用。由于本文路網(wǎng)存在兩個節(jié)點(diǎn)集且染色體采用符號表碼方式，染色體交叉可能出現(xiàn)新生成的染色體不在同一層路網(wǎng)中且互不連通。因此，為保證新染色體的良好連通性，本文采用路徑交叉法，此方法是由文獻(xiàn)［6］中提出的最佳費(fèi)用的路徑雜交算子基礎(chǔ)上改進(jìn)而來。該方法具體描述如下:

染色體A:{O V1T1T3T4V4V6D 0 0 0 0}可以分為運(yùn)輸段和轉(zhuǎn)換弧

染色體B:{O V1V2T2T1T3V5V6D 0 0 0}可以分為運(yùn)輸段和轉(zhuǎn)換弧

以選擇轉(zhuǎn)換弧M為原則，將染色體A和染色體B進(jìn)行交叉操作。此處選擇染色體A中的轉(zhuǎn)換弧M4對應(yīng)路徑是T4－V4，染色體B中的轉(zhuǎn)換弧M3對應(yīng)路徑是T3－V5參與交叉。如果交叉操作后，新染色體的基因節(jié)點(diǎn)與交叉路徑節(jié)點(diǎn)重合，則將重復(fù)節(jié)點(diǎn)合并為一個節(jié)點(diǎn)，若基因節(jié)點(diǎn)數(shù)不足，則在“D”后以“0”補(bǔ)足;如果交叉操作后，新染色體內(nèi)的基因節(jié)點(diǎn)與交叉路徑節(jié)點(diǎn)之間不連通，則需插入一個使其相互連通的節(jié)點(diǎn)，若基因節(jié)點(diǎn)數(shù)大于總基因數(shù)，則刪除“D”后的“0”;如果交叉操作后，新染色體內(nèi)的基因節(jié)點(diǎn)與交叉路徑節(jié)點(diǎn)間多出一個多余節(jié)點(diǎn)，即多余節(jié)點(diǎn)刪除后不影響其左右節(jié)點(diǎn)的相連，則刪除多余節(jié)點(diǎn)，并在“D”后增減“0”，以確保路徑連通且存在于路網(wǎng)內(nèi)。

3.6 染色體變異

在產(chǎn)生新染色體時，為了避免陷入局部尋優(yōu)的不利情況，引入染色體變異機(jī)制，已便于跳出局部尋優(yōu)達(dá)到全局尋優(yōu)的目的。為保持良好的連通性，本文采用基本位變異的方法。在染色體符合“O”和“D”之間的有效長度中找出最后一個轉(zhuǎn)換點(diǎn)Ti，將其變換為與Ti上一節(jié)點(diǎn)相連的其他節(jié)點(diǎn)，若變異后的染色體有效長度發(fā)生變化，則自動增減“D”后的“0”個數(shù)。

通過上述算法設(shè)計(jì)，給出運(yùn)用該算法解決基于時間最短的公鐵聯(lián)合軍事運(yùn)輸路徑優(yōu)化模型的求解流程(如圖2所示)。

4 應(yīng)用算例

以西部某戰(zhàn)區(qū)某一輸送梯度執(zhí)行應(yīng)急任務(wù)為例。該輸送梯隊(duì)根據(jù)上級指示安排，從駐地出發(fā)，可依靠鐵路和公路兩種運(yùn)輸方式，機(jī)動到指定目的地域，要求于24 h之內(nèi)完成輸送任務(wù)。該輸送梯度包括若干人員和裝備，其中重型裝備為某式主戰(zhàn)坦克［5］。

圖2 遺傳算法求解基本流程

建立該戰(zhàn)區(qū)公鐵聯(lián)合軍事運(yùn)輸網(wǎng)絡(luò)圖(如圖1所示)［5］。由于軍事運(yùn)輸與民用客貨運(yùn)存在較大差異，故不能按民用運(yùn)輸?shù)臅r間來推算軍事運(yùn)輸時間。在此假設(shè)該輸送梯隊(duì)通過鐵路子網(wǎng)各運(yùn)輸段的時間見表1，發(fā)生中轉(zhuǎn)換乘及等待時間見表2，通過公路子網(wǎng)各運(yùn)輸段的時間見表3。

表1 鐵路子網(wǎng)各運(yùn)輸段通行時間

設(shè)出發(fā)地為O點(diǎn)，其路網(wǎng)內(nèi)對應(yīng)節(jié)點(diǎn)為V12;目的地為D點(diǎn)，其路網(wǎng)內(nèi)對應(yīng)節(jié)點(diǎn)為V37。根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)可知，染色體的基因總數(shù)為17+48+2=67個。設(shè)遺傳算法的群體大小設(shè)定值等于400，路徑交叉概率設(shè)定值等于0.85，轉(zhuǎn)換點(diǎn)變異概率設(shè)定值等于0.05，最高疊代300次。模擬迭代次數(shù)為600次。

表2 中轉(zhuǎn)換乘及等待時間

表3 公路子網(wǎng)各運(yùn)輸段通行時間

對求出的此條最優(yōu)路徑進(jìn)行評估。按軍事運(yùn)輸?shù)南嚓P(guān)規(guī)定，配有履帶式重裝備的成建制部隊(duì)機(jī)動時首選鐵路運(yùn)輸方式，但在某戰(zhàn)區(qū)內(nèi)未跨越戰(zhàn)區(qū)范圍，且該輸送梯隊(duì)規(guī)模不大，配屬某式坦克數(shù)量不多，可以裝載到公路大型平板拖車上運(yùn)輸，因此，只采取公路運(yùn)輸方式符合軍事運(yùn)輸規(guī)定，所求最優(yōu)路徑切實(shí)可行。

5 結(jié)語

為深入貫徹落實(shí)習(xí)主席“能打仗、打勝仗”的強(qiáng)軍目標(biāo)，充分發(fā)揮各種運(yùn)輸方式的優(yōu)勢，聯(lián)合軍事運(yùn)輸將成為我軍機(jī)動的重要手段。除時間外，保障能力、通過能力等因素在實(shí)際情況中也制約著軍事運(yùn)輸組織保障工作，下一步將在時間最短的基礎(chǔ)上研究多目標(biāo)聯(lián)合軍事運(yùn)輸路徑優(yōu)化問題，為提升我軍戰(zhàn)略投送能力提供技術(shù)與理論支持。

［1］ 李巖，戴明強(qiáng)，溫林.基于運(yùn)輸風(fēng)險的戰(zhàn)時運(yùn)輸網(wǎng)絡(luò)交通流分配模型［J］.兵工自動化，2009(2):22-24.

［2］ 楊文索，姚金凱，王耀.戰(zhàn)區(qū)內(nèi)戰(zhàn)時軍事運(yùn)輸路徑優(yōu)化研究［J］.物流科技，2009(4):88-90.

［3］ 常剛，劉寶新，宋凱.應(yīng)用灰色評價理論選擇最優(yōu)軍事運(yùn)輸方式研究［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識，2007(3):57-63.

［4］ 許國銀，熊孝和，林濤.基于GASA算法的成品燃油戰(zhàn)時公路配送路徑優(yōu)化［J］.解放軍理工大學(xué)學(xué)報:自然科學(xué)版，2007(2):180-185.

［5］ 吳洋，李瑞敏，王曉安.基于多模式的公鐵聯(lián)合軍事運(yùn)輸網(wǎng)絡(luò)圖模型研究［J］.公路工程，2013(6):54-59.

［6］ 劉敏.多目標(biāo)遺傳算法在車輛路徑優(yōu)化中的應(yīng)用研究［D］.湘潭:湘潭大學(xué)，2006.