侯小平，胡堅明，陳興德

(1.駐成都鐵路局軍代處，成都 610082； 2.清華大學(xué)，北京 100084)

?

部隊陸空聯(lián)合投送路徑優(yōu)化

侯小平1，胡堅明2，陳興德1

(1.駐成都鐵路局軍代處，成都 610082； 2.清華大學(xué)，北京 100084)

在成建制部隊陸空聯(lián)合投送中，為選取最優(yōu)投送路徑，采用圖論的方式構(gòu)建虛擬聯(lián)合投送網(wǎng)絡(luò)圖，分析網(wǎng)絡(luò)邊(弧)權(quán)值，對“人裝一體”投送條件下航空裝運卸時間以及各種投送方式之間換裝時間，建立以時間最短為目標的陸空聯(lián)合投送路徑優(yōu)化數(shù)學(xué)模型，并使用遺傳算法求解模型。模擬驗證表明，該模型能夠求得時間最短的優(yōu)化路徑。

陸空聯(lián)合投送；路徑優(yōu)化；遺傳算法

隨著軍隊職能使命的不斷拓展和交通運輸?shù)目焖侔l(fā)展，部隊投送只采用單一投送方式已不能滿足部隊快速機動的要求，聯(lián)合投送是大勢所趨，特別是充分利用航空這種快速投送方式[1]，采取陸空聯(lián)合投送迅速將成建制輕裝部隊“人裝一體”地投送到指定地域。但從當(dāng)前研究現(xiàn)狀看[2-4]，公鐵聯(lián)運研究多、陸空聯(lián)合投送研究少，聯(lián)合投送路徑定性分析多、定量研究少，“人裝分離”的立體投送研究多、成建制部隊“人裝一體”聯(lián)合投送研究少。因此，研究“人裝一體”條件下成建制部隊陸空聯(lián)合投送路徑優(yōu)化問題，具有十分重要的意義。

1 模型建立

1.1 問題描述

西部戰(zhàn)區(qū)某輕裝部隊接到上級命令，要求其在最短的時間內(nèi)從駐地O投送至目的地域D，途經(jīng)若干節(jié)點且相鄰兩點間有多種投送方式可以選擇。根據(jù)西部交通實際，只考慮鐵路、公路、航空3種投送方式組合，暫不考慮水路投送方式。在這種情況下，需要選擇一條合理的投送線路和最佳投送方式組合，使部隊聯(lián)合投送時間最短。

1.2 構(gòu)建虛擬網(wǎng)絡(luò)圖

聯(lián)合投送網(wǎng)絡(luò)不僅空間跨度大，而且十分龐雜，包含眾多交通信息，如果不對其進行適當(dāng)?shù)某橄蠛喕?，最?yōu)路徑的搜索將會比較繁瑣。因此，本文將每一個實際節(jié)點按照所需運輸方式數(shù)量的不同，擴展出與之相對應(yīng)的虛擬節(jié)點，每個虛擬節(jié)點表示從實際節(jié)點出發(fā)的一種運輸方式[5-6]。

圖1 虛擬聯(lián)合投送網(wǎng)絡(luò)

結(jié)合聯(lián)合投送的實際情況，該虛擬網(wǎng)絡(luò)圖的特點如下：

(1)該虛擬網(wǎng)絡(luò)圖用平面圖的方式表達了一個4個水平面和n個垂直面的立體空間圖，其中每一個水平面對應(yīng)一種投送方式，每一個垂直面表示不同投送方式之間轉(zhuǎn)換；

(2)N1和Nn分別為投送的起始點和終到點，O、D為虛擬源點和終點，為了方面最短路求解，O到N1、Nn到D的權(quán)值均為0；

(3)對于同一水平面的不相鄰節(jié)點，如果存在弧線連接，說明這兩點之間存在不經(jīng)過第三方的直達投送線路，這與聯(lián)合投送的復(fù)雜網(wǎng)絡(luò)特性是相一致的；

(4)聯(lián)合投送的實際網(wǎng)絡(luò)中，不可能每個節(jié)點都能提供4種不同的投送方式，對此，在同一層面，如果兩個相鄰節(jié)點之間不提供某種投送方式，則該相鄰節(jié)點無連接弧或為無窮大。

1.3 建立陸空聯(lián)合投送路徑優(yōu)化模型

1.3.1 情況假設(shè)

(1)各種投送方式的轉(zhuǎn)換只能在節(jié)點處發(fā)生，且每一節(jié)點只能實施一次換裝；

(2)兩相鄰節(jié)點之間只能選擇一種投送方式，若不存在投送方式，則兩者不相連或為無窮大；

(3)相同投送方式之間或途中不發(fā)生中轉(zhuǎn)和倒裝；

(4)不考慮擁堵、晚點等因素對投送時間的影響；

(5)部隊在裝載或換乘時，鐵路車輛和飛機均已集結(jié)完畢，則不需考慮等待時間。

1.3.2 目標決策分析

從聯(lián)合投送的過程看，投送的總時間T=tz+ty+th+tx,其中：tz為部隊在集結(jié)地域出發(fā)裝載的時間；ty為部隊在各節(jié)點之間的運行時間；th為部隊投送中所有的換裝時間；tx為部隊在目的地的卸載時間。

實際中，各種投送方式的裝運卸時間都可以根據(jù)投送任務(wù)實際和交通設(shè)施設(shè)備保障能力加以求解。但在“人裝一體”條件下，進行陸空聯(lián)合投送需要考慮公路或鐵路投送與航空投送之間的銜接、換乘問題，對于運力比較大的鐵路和公路投送來說，可以一次性投送大批量的人員和裝備，但航空投送受運輸機的單機裝載能力和保有數(shù)量的制約，對成建制部隊航空投送時，需采取飛機“循環(huán)套用”的運輸組織形式，即按照空運順序，循環(huán)使用飛機分批次運送部隊，直至空運完畢。針對這一特殊情況，著重對航空投送時間進行分析研究。

(1)根據(jù)部隊人員數(shù)量和裝備物資尺寸、重量，預(yù)測所需客、貨機架次數(shù)。部隊成建制進行航空投送時，通常使用客機運送人員、貨機運輸裝備物資，客機通常按部隊總?cè)藬?shù)除以客機航次載客量的90%來估算，貨機通常用裝備物資總重量和總長度兩個指標來估算，并需綜合考慮裝卸載機場保障能力。

(2)根據(jù)可供選擇的貨機機型、架數(shù)以及架次數(shù)，計算單機往返次數(shù)。這是由于我國貨機短缺，適合輪式裝備裝載的大中型運輸機更是極其有限，通常需采取飛機“循環(huán)套用”的運輸組織形式，即按照空運順序，循環(huán)使用飛機分批次運送部隊，直至空運完畢。比如，選擇了5架飛機，需飛行15個架次，則需飛行3個梯隊，每個梯隊包含5個架次。

(3)戰(zhàn)時特殊情況下，部隊實施空中投送可采取在機場半關(guān)閉或全關(guān)閉的狀態(tài)下裝卸載，并盡可能開展多架次、多機種平行裝卸載作業(yè)。

因此，可以求出航空投送實際裝載時間為

實際運行時間為

實際卸載時間為

1.3.3 建立模型

根據(jù)上述分析，建立以時間為最短的陸空聯(lián)合投送路徑優(yōu)化數(shù)學(xué)模型：

minT=tz+ty+tx+th=

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

目標函數(shù)式(1)表示求陸空聯(lián)合投送時間最短。約束條件式(2)保證從任一節(jié)點出發(fā)只能選擇一種投送方式，式(3)保證任一節(jié)點至多發(fā)生一次換裝，式(4)保證投送方式的連續(xù)性，式(5)和式(6)表明決策變量只能取整數(shù)0或1。

2 算法設(shè)計

部隊陸空聯(lián)合投送路徑優(yōu)化問題不是一個線性規(guī)劃問題，而是一個典型的NP問題，用精確算法有一定的困難，而遺傳算法[7-9]的染色體編碼序列與路徑節(jié)點序列存在關(guān)聯(lián)性，即一條染色體的編碼可以表示為一條路徑，以及遺傳算法所具有的并行性特點，可以較快地在全局尋找到最優(yōu)解，因此本文運用遺傳算法對部隊陸空聯(lián)合投送路徑優(yōu)化問題進行求解。

2.1 染色體編碼

采用比較簡單易懂的自然數(shù)編碼方式，這樣能與投送節(jié)點編號和投送方式代碼相對應(yīng)。染色體的基因就是投送節(jié)點編號與投送方式代碼間隔編碼，其排列順序代表著從起點到終點的路徑?；驑?gòu)成為：第一個和最后一個分別為起點編號“1”、終點編號“n”,偶數(shù)位置為投送方式代碼，奇數(shù)位置為投送節(jié)點編號。一般來說，投送節(jié)點編號一般用1,2,…,n表示，為了相互區(qū)別，投送方式代碼用0、-1、-2、-3表示，其中：0表示兩個節(jié)點間不連通；-1表示鐵路；-2表示公路；-3表示航空。

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

考慮到遺傳算法中一般是適應(yīng)值越大越好，以時間最短為目標的路徑優(yōu)化模型適應(yīng)度函數(shù)可以取F=1/T。

2.3 染色體選擇

本文采用輪盤賭選擇法。假設(shè)初始群體的個體數(shù)量為M，各染色體的適應(yīng)值為F1,F2,…,Fn，則染色體被選擇的概率為

2.4 染色體交叉

采取單點交叉，且交叉的點為除1、n外所有投送節(jié)點編號。由于投送節(jié)點位于染色體中的奇數(shù)位置，設(shè)染色體基因串長度為m，那么交叉點就是從3,5,…，m-2中隨機選取。

(1)從上一代選擇染色體A和B的基因中隨機確定各自交叉點，交叉點必須位于1和n之間。

(2)進行交叉操作。主要分兩種情況：如果兩個交叉點對應(yīng)的節(jié)點編號相同，則將個體A交叉點的左半部分與個體B的右半部分通過相同的交叉點連接在一起，得到新的個體A1；同理，將個體A交叉點的右半部分與個體B的左半部分通過相同的交叉點連接在一起，得到新的個體B1。如果兩個交叉點對應(yīng)的節(jié)點編號不同，則將個體A交叉點的左半部分與個體B的右半部分進行組合，并隨機生成一條路徑銜接兩個交叉點，最終得到新的個體A1，同理可以得到新的個體B1。

(3)消除染色體中重復(fù)節(jié)點。對交叉后的染色體進行檢查，若有完全相同的基因，則將相同基因間的路段刪除，最終得到新個體。

2.5 染色體變異

根據(jù)編碼方式，主要采取兩種變異方法。

(1)變異位為染色體中奇數(shù)位的投送節(jié)點，則將該節(jié)點變更為其他節(jié)點，并重新確定變異節(jié)點與相鄰節(jié)點的投送方式，以確保變異后的染色體有效。同時檢查變異后的染色體是否存在重復(fù)地點，若有則刪除。

(2)變異位為染色體中偶數(shù)位的投送方式，然后查看該投送方式連接的左右兩個節(jié)點，并將該投送方式變更為這兩個節(jié)點之間其他可連通的投送方式。如果這兩節(jié)點之間只有這種投送方式，則不做更改。

3 算例驗證

假設(shè)，某部隊奉命從駐地出發(fā)，采取“人裝一體”方式，運用鐵路、公路、航空3種投送方式，機動至指定地域。其投送網(wǎng)絡(luò)如圖2所示。

圖2 聯(lián)合投送網(wǎng)絡(luò)

該輸送梯隊包含200名官兵和30輛裝備，其中裝備為某式輪式裝甲突擊車，可摩托化機動并裝運少數(shù)兵力(9人)。

鑒于當(dāng)前我國航空投送裝備數(shù)量嚴重不足的實際[10]，應(yīng)急情況下能用于部隊成建制航空投送的大中型運輸機非常有限。本文假設(shè)一次性能調(diào)動參與部隊航空投送的運輸機為5架、客機1架，其技術(shù)參數(shù)見表1。

表1 運輸機、客機技術(shù)參數(shù)

從部隊裝備實力和飛機裝運能力、實際數(shù)量情況看，要完成該部航空投送，需要12架次飛機，即單機需往返1次，則可以根據(jù)航空運輸裝運卸時間的計算式進行求解實際裝載、運行、卸載時間。假設(shè)該輸送梯隊以鐵路、公路、航空投送方式在各線路的投送時間見表2，各節(jié)點鐵路、航空投送裝卸載時間見表3(航空投送時間已綜合考慮了航空運力和單機往返次數(shù)等因素)。

表2 各節(jié)點之間的運輸投送時間 h

表3 各節(jié)點裝卸載、換乘時間 h

根據(jù)網(wǎng)絡(luò)節(jié)點數(shù)可知，有效染色體的基因個數(shù)小于48個。設(shè)遺傳算法的群體大小規(guī)模為300,交叉概率0.85,變異概率0.05,最大迭代次數(shù)為300次。

對于以時間最小為目標的路徑優(yōu)化問題，經(jīng)遺傳算法求解后得到染色體為1-3、10-1、13-1、15-2、16，其運輸路徑為1→航空→10→鐵路→13→鐵路→15→公路→16,時間為42.300 0 h。

算例表明，利用本文給出的模型研究部隊陸空聯(lián)合投送路徑優(yōu)化問題，符合鐵路、公路、航空投送的特點和實際需要，而采用遺傳算法是求解該問題的一種有效方法，能夠求解得到時間最短的優(yōu)化路徑。

4 結(jié) 語

陸空聯(lián)合投送是部隊快速投送發(fā)展的重要方向，通過本文提供的模型和算法，能夠較好地解決“人裝一體”條件下成建制部隊陸空聯(lián)合投送路徑優(yōu)化問題，可為指揮決策者確定部隊陸空聯(lián)合投送路徑優(yōu)化提供有效的決策支撐。但是由于陸空聯(lián)合投送路徑優(yōu)化問題涉及的內(nèi)容以及各種不確定性因素較多，還需要進一步考慮鐵路車輛和運輸機的集結(jié)準備時間問題以及運輸網(wǎng)絡(luò)的動態(tài)性，并且必經(jīng)點和禁行點問題也是聯(lián)合投送中的一個重要問題，這些都需要下一步研究解決。

[1] 吳曉東,楊永偉.戰(zhàn)略投送兵棋推演初探[J].軍事運籌與系統(tǒng)工程,2011,25(3):15-19.

[2] 寇世強.兵力運輸投送及其相關(guān)概念[J].國防交通,2005(3):29-30.

[3] 管井標,周赤非,許瑞明,等.戰(zhàn)略運輸投送能力評估方法研究[J].軍事運籌與系統(tǒng)工程, 2011(2):76-80.

[4] 海軍.部隊戰(zhàn)略運輸投送模式問題探析[J].國防交通工程與技術(shù),2013(5):8-10.

[5] 王清斌,韓增霞,計明軍,等.基于節(jié)點作業(yè)隨機特征的集裝箱多式聯(lián)運路徑優(yōu)化[J]．交通運輸系統(tǒng)工程與信息,2010(6):137-144.

[6] 董潔霜.港口集疏運系統(tǒng)優(yōu)化模型[J].上海理工大學(xué)學(xué)報,2007,29(5):453-456.

[7] RYAN J L, BAILEY T G,MOORE J T, et al. Reactive Tabu search in unmanned aerial reconnaissance simulations[C]//Proceedings of the 30th Conference on Winter Simulation，Washington DC,USA:IEEE Computer Society Press,1998:873-879.

[8] KOH S P, ARIS I B, HO C K, et al. Design and performance optimization of a multi-TSP (traveling salesman problem) algorithm[J]. AIML Journal, 2006, 6(3):29-33.

[9] 崔珊珊.遺傳算法的一些改進及其應(yīng)用[D].合肥：中國科學(xué)技術(shù)大學(xué),2010.

[10] 程文明,何孟良,唐準,等.關(guān)于我軍航空戰(zhàn)略投送裝備建設(shè)的思考[J].軍事交通學(xué)院學(xué)報,2014,16(7):5-8.

(編輯：張峰)

Route Optimization of Military Air-ground Joint Projection

HOU Xiaoping1, HU Jianming2, CHEN Xingde1

(1.Military Representative Office in Chengdu Railway Bureau, Chengdu 610082, China; 2.Tsinghua University, Beijing 100084, China)

To select optimized projection route in military air-ground joint projection, the paper firstly establishes virtual joint projection network diagram with graph theory. Then, it analyzes weights of network sides (arcs) and studies aviation load-haul-dump time under the projection condition of personnel-equipment integration and converting time among different projection modes, and establishes a route optimization mathematical model of air-ground joint projection which taking shortest time as the objective. Finally, it solves the problem with genetic algorithm. The simulation verifies it can obtain optimized route with shortest time by this model.

air-ground joint projection; route optimization; genetic algorithm

2016-12-22；

2016-12-29．

國家重點研發(fā)項目(2016YFB0100906)；國家自然科學(xué)基金項目(61673232)．

侯小平(1983—)，男，碩士．

10．16807/j.cnki.12-1372/e.2017.05.002

E234

A

1674-2192(2017)05- 0005- 05

● 戰(zhàn)略投送 Strategic Projection