部隊陸空聯合投送路徑優化

侯小平，胡堅明，陳興德

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

?

部隊陸空聯合投送路徑優化

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

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

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

陸空聯合投送；路徑優化；遺傳算法

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

1 模型建立

1.1 問題描述

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

1.2 構建虛擬網絡圖

聯合投送網絡不僅空間跨度大，而且十分龐雜，包含眾多交通信息，如果不對其進行適當的抽象簡化，最優路徑的搜索將會比較繁瑣。因此，本文將每一個實際節點按照所需運輸方式數量的不同，擴展出與之相對應的虛擬節點，每個虛擬節點表示從實際節點出發的一種運輸方式[5-6]。

圖1 虛擬聯合投送網絡

結合聯合投送的實際情況，該虛擬網絡圖的特點如下：

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

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

(3)對于同一水平面的不相鄰節點，如果存在弧線連接，說明這兩點之間存在不經過第三方的直達投送線路，這與聯合投送的復雜網絡特性是相一致的；

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

1.3 建立陸空聯合投送路徑優化模型

1.3.1 情況假設

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

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

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

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

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

1.3.2 目標決策分析

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

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

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

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

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

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

實際運行時間為

實際卸載時間為

1.3.3 建立模型

根據上述分析，建立以時間為最短的陸空聯合投送路徑優化數學模型：

minT=tz+ty+tx+th=

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

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

2 算法設計

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

2.1 染色體編碼

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

2.2 建立適應度函數

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

2.3 染色體選擇

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

2.4 染色體交叉

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

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

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

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

2.5 染色體變異

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

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

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

3 算例驗證

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

圖2 聯合投送網絡

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

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

表1 運輸機、客機技術參數

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

表2 各節點之間的運輸投送時間 h

表3 各節點裝卸載、換乘時間 h

根據網絡節點數可知，有效染色體的基因個數小于48個。設遺傳算法的群體大小規模為300,交叉概率0.85,變異概率0.05,最大迭代次數為300次。

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

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

4 結 語

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

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

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

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

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

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

[6] 董潔霜.港口集疏運系統優化模型[J].上海理工大學學報,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] 崔珊珊.遺傳算法的一些改進及其應用[D].合肥：中國科學技術大學,2010.

[10] 程文明,何孟良,唐準,等.關于我軍航空戰略投送裝備建設的思考[J].軍事交通學院學報,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．

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

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

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

E234

A

1674-2192(2017)05- 0005- 05

● 戰略投送 Strategic Projection