軍事空運路徑與裝載聯合優化問題研究

顏 瑞，馬曉娟，梁廷政，王 雷

(1.北京信息科技大學，北京 100192； 2.北京科技大學，北京 100083；3.北京市可持續發展科技促進中心，北京 100035； 4.中國刑事警察學院，沈陽 110035)

軍事空運路徑與裝載聯合優化問題研究

顏 瑞1，馬曉娟2，梁廷政3，王 雷4

(1.北京信息科技大學，北京 100192； 2.北京科技大學，北京 100083；3.北京市可持續發展科技促進中心，北京 100035； 4.中國刑事警察學院，沈陽 110035)

為了有效、快速制定軍事空運路徑和裝載方案，在計算出最優運輸路徑的同時獲取可行裝載方案，針對軍事空運路徑和裝載的聯合優化問題進行研究。建立軍事空運路徑和裝載聯合優化模型，提出一種結合量子粒子群算法和引導式局部搜索算法的混合算法進行求解，通過數值試驗檢驗模型的可行性和算法的有效性。試驗結果表明，聯合優化模型能夠有效實現軍事空運路徑和裝載聯合優化問題的建模過程，且混合算法能夠有效獲取聯合優化模型的近似最優解。

軍事空運；路徑方案；裝載方案；聯合優化；量子粒子群算法

0 引 言

第二次世界大戰后，航空軍事運輸發展十分迅速，空運的作用越來越大。軍事空運在軍事作戰和訓練、支援國家建設、搶險救災中，都發揮著重要作用。組織軍事空運，須根據接收地域的場地條件和部隊需要，采取著陸空運(機降)或非著陸空運(空投)的方法，并注意物資的包裝、捆綁和裝載，以提高運輸效能[1]。裝載方案和路徑方案是軍事空運的兩個重要決策內容。實現軍事空運裝載方案和路徑方案的快速、優化生成，保證裝備物資安全、可靠、快速到達目的地，是戰時空運保障和應急救援保障的首要任務。

目前，針對軍事空運裝載方案和路徑方案優化的研究是獨立進行的，且分別產生了許多研究成果[2-5]。但是，獨立優化裝載方案和路徑方案往往會產生一些不合理方案。比如，在優化路徑方案通常需要考慮物資重量和體積，但由于物資打包規格不一致、機艙承載裝載空間不規則等原因，容易造成物資無法全部裝入機艙內或者浪費大量裝載空間的情況。為了避免產生不合理方案、提高軍事空運效率，有必要將裝載方案和路徑方案聯合起來進行優化，建立聯合優化模型并設計求解算法。

1 模型建立

1.1 問題描述及模型假設

軍事空運裝載方案與路徑方案聯合優化問題的建模和求解可以參考帶裝箱約束的車輛路徑問題，但需要考慮更多的裝載要求和運輸要求。軍事空運裝載方案與路徑方案聯合優化問題可以描述為：集中倉庫儲存著足夠量的各類軍事物資，機場有一定數量的運輸機可供調度，在一定區域內分布著多個物資需求點，每個需求點需求不同數量、不同類型的物資，倉庫與需求點之間、每兩個需求點之間均有固定航線，決策目標是得到一個使用運輸機數量最少、消耗總時間最短的運輸機調度和飛行路徑方案，并且同時獲取每架飛機的可行裝載方案。

軍事空運裝載方案與路徑方案聯合優化模型的假設：

(1)假設物資倉庫與機場各有一個且位置相同，即不考慮物資從倉庫搬運至運輸機的過程；

(2)任意兩個節點之間均有固定航線，運輸機可以執行所有航線上的任務，所有運輸機為同一型號；

(3)確定不超過運輸機數量的回路作為運輸機飛行路線，每條回路總長度不超過運輸機最大航程，所有回路均從機場出發并返回機場；

(4)每個需求點只能在一條回路上，每條回路上的需求點僅由一架運輸機服務(即為非滿載運輸問題)；

(5)不考慮起飛和降落過程，在同一條航線、同方向上，所有運輸機均以相同速度勻速飛行，在不同航線或相對方向上，運輸機的速度可能不同；

(6)每條回路上需求點的物資需求總重量不能超過運輸機的最大載重，物資總體積不能超過運輸機機艙內的最大容積；

(7)每件物資均打包成長方體形狀，機艙內空間可被分割成若干個裝載區域，每個區域均為長方體；

(8)所有物資均從運輸機尾部的艙門進出，裝貨過程從運輸機內側左下角開始，假設裝貨工具可以把物資擺放到運輸機內的任意位置；

(9)每條回路上物資需求點的物資必須全部裝入運輸機內，且滿足全部給定的裝載約束；

(10)以所有運輸機的飛行時間之和最小為目標。

軍事空運裝載不僅要求承載量最大、空間利用率最高，更要滿足作戰要求，實現軍事價值最大化。因此，除了以上假設中的(6)、(7)和(8)之外，還需要考慮如下裝載約束：

(1)基本裝載約束：物資不能懸空放置、不能重合放置，單件物資的體積不能大于機艙可裝載空間；

(2)方向性約束：物資邊緣必須與相應的車廂邊緣平行，所有物資均區分頂部和底部，且物資必須頂部朝上放置，物資只能在水平面上做90°的旋轉，不能以其它角度或者在垂直面上旋轉；

(3)穩定性約束：上下堆疊的物資之間不能有空隙，且上下層兩個物資的直接接觸面積不能小于上層物資底面積的ρ(ρ為給定常量，0.5≤ρ≤1)倍，下層如有多個頂部平齊的物資可被視為一個物資；

(4)LIFO(Last-in-First-out)約束：軍事空運對時間要求非常高，決不允許在裝卸貨過程中執行不必要的操作，此外還須應對突發狀況導致無法著陸時空投物資的情況，因此，必須滿足“先進物資后出，先出物資后進”的約束，以滿足連續執行裝卸貨作業的要求；

(5)平衡性約束：如果載貨之后的運輸機重心偏移過大，則會大幅增加操控難度、降低任務執行效率，因此，必須保證運輸機前后、左右的載貨重量之差在規定范圍內；

(6)安全性約束：對于防壓、防震、防潮、防凍的儀器設備類以及危險類物資，除了在裝載前需要進行適當的包裝處理之外，裝載的時候還應確保其放置在安全位置，可假設該類物資的長寬為實際長寬加上安全間隔寬度，且假設物資的高度與機艙高度一致(即其上方不可放置其他物資)，為了簡化模型，本文將所有物資歸為如下兩種類型：普通物資，可堆疊擺放；防壓物資，其上方不可堆疊放置其他類型物資，可放置同類物資。

1.2 模型符號及符號解釋

建立聯合優化模型之前需要將機艙空間轉化為，以機艙內側左下角為坐標原點，以機艙最邊緣的長、寬和高為坐標軸，建立笛卡爾坐標系。表1給出模型中的所有符號，并解釋每個符號的意義。

表1 模型符號及符號解釋

1.3 數學模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

目標函數(1)表示最小化所有運輸機的飛行總時長；式(2)表示所有物資需求節點僅被訪問一次；式(3)和式(4)表示運輸機從物資倉庫出發，執行完任務之后返回物資倉庫；式(5)表示運輸機進入某節點，也必須從該節點離開；式(6)表示每架運輸機裝載貨物的重量之和不超過運輸機限制載重；式(7)表示每架運輸機裝載貨物的體積之和不超過運輸機限制容積；式(8)綁定了裝載優化變量和路徑優化變量；式(9)為支路消除約束，保證任何路線中只包含一個物資倉庫。

在建立裝載優化模型之前，需要先建立一個笛卡爾坐標系。坐標系的坐標軸分別對應于運輸機外切長方體的長、寬和高，如圖1所示。

圖1 運輸機外切長方體及笛卡爾坐標系示意圖

在圖1中，用間距相等的網格線將運輸機外切長方體分割成若干個小立方體，當網格線足夠密集時可以保證所有物資占用立方體的個數為整數(當網格線間距小于等于物資尺寸示數的最小單位時即可)。運輸機的不同裝載區域均處于外切長方體之內，當某裝載區域的邊緣未達到長方體邊緣時，可將裝載區域與外切長方體之間的立方體全部標記為已被占用。

貨物i底部左前方的位置用坐標A(x,y,z)表示，則有：x∈X={0,1,…,L-minik(lmik)}，y∈Y={0,1,…,W-minik(wmik)}，z∈Z={0,1,…,H-minik(hmik)}，其中k=1,2,…,K，i=1,2,…,Np。

受到物資三維形狀的限制，即使單架運輸機的物資總體積小于其裝載空間總容積，也有可能發生無法將所有物資全部裝入機艙內的情況?？紤]到這一點，本文以最大化裝入機艙內的貨物總數為目標建立裝載優化模型，則可行解的目標函數值等于物資總數。裝載優化模型如下：

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

其中，(x′,y′,z)表示另一個物資底部左前方的可能位置坐標，σi表示貨物頂部任意一點所能承受的最大壓強。注意，在路徑優化模型中i表示顧客，而在裝載優化模型中i表示物資。式(10)為目標函數，最大化裝入運輸機的總貨物數；式(11)保證了所有物資都必須有支撐區域(不可懸空放置)；式(12)用以區分不同物資類型的擺放要求；式(13)和(14)分別表示運輸機在x軸和y軸上的重心約束；式(15)給出了決策變量；式(16)和式(17)計算貨物i的長和寬。模型中的變量和標識詳見文獻[6]和文獻[7]。

2 算法設計

本文提出一種結合量子粒子群算法和引導式局部搜索算法的混合算法求解軍事空運裝載與路徑聯合優化模型。本節將詳細描述混合算法的基本原理、各部分策略和實施步驟。

2.1 改進的量子粒子群算法

2.1.1 基礎量子粒子群算法

美國學者Kennedy和Eberhart受到鳥群覓食行為的啟發提出了粒子群算法(Particle Swarm Optimization，PSO)，PSO具有精度高、收斂快和容易實現等優點[8]。算法提出后不久就被用于求解VRP問題，目前已有許多運用PSO求解VRP及其變種問題的文獻[9, 10]。在標準PSO中，種群由一定數量的粒子組成，每個粒子的位置均代表一個可行解。在多維搜索空間中，每個粒子均按照某個特定速度向更好的解移動。

mbest(t)=(mbest1(t),mbest2(t),…mbestd(t))=

(18)

(19)

u=rand(0,1)

(20)

其中，M表示粒子群中粒子的數目；d為粒子維度；mbest表示在所有粒子中每個粒子搜索到的最優位置的平均值，本文采用最接近平均適應值的粒子所在的位置；Pi=(Pi1,Pi2,…,Pid)表示第i個粒子的最優位置；Pgd表示所有粒子中最佳粒子所在的位置；pid表示在Pid和Pgd之間的一個隨機點，在第i個粒子d維空間的一個位置；φ和u是在[0,1]之間均勻分布的隨機數；α是QPSO算法的參數，稱為收縮-擴張系數，一般采用線性遞減的方式取值，其公式為：

(21)

量子粒子群優化算法過程如下：

Step1.初始化種群，粒子的初始位置通過隨機方式產生；

Step2.對于每一個粒子，計算其適應值，保存每個粒子歷史最優值Pid，以及所有粒子的最優值Pgd；

Step3.根據公式(18)計算mbest，即最接近所有粒子的平均適應值的粒子所在位置；

Step4.對于粒子的每一個維，通過公式(19)得到一個隨機點；

Step5.通過公式(20)獲得一個新的位置Xid；

Step6.執行局部擾動操作；

Step7.重復Step2-Step6，直至達到最大迭代次數。

2.1.2 局部擾動

為了提高QPSO的尋優效率，本文采用2-opt和線路內部搜索兩個方法進行局部擾動，這兩種方法類似于遺傳算法中的變異算子。2-opt作用于兩條線路上，具體操作方法是：隨機選擇兩條線路，并隨機選擇兩個位置，將兩條線路上的對應節點進行互換。線路內部搜索作用于單條線路上，具體操作方法是：隨機選擇一條線路，并隨機選擇兩個位置，將兩個位置對應的節點進行互換。

2.2 引導式局部搜索算法

由2.1中的量子粒子群算法可求解得最優路線，并可以確定每條路線上有哪些物資需求點。本節討論如何將物資裝入各自機艙內，且滿足所有裝載約束。一般的裝箱問題以裝載貨物數最大為目標，而在軍事空運裝載與路徑聯合優化模型的裝載問題中每架運輸機裝載的貨物數量和形狀是固定的，因此其解空間僅是一般裝箱問題解空間的一個子集。針對這樣的特點，我們將設計一系列引導策略搜索問題的局部最優解。聯合優化模型的裝箱過程包括確定待裝貨物順序和確定可行裝貨位置兩個子問題，下面分別給出這兩個子問題的求解策略。

2.2.1 確定待裝貨物順序

對于一條給定的運輸路線而言，該線路上的所有物資需求點及其順序是固定的。在當前需求點執行卸貨任務時不可以用挪動其他需求點的貨物，因此同一條線路上的物資應首先按照執行任務的順序逆向安排，遵循后進先出原則。因此，不同物資需求點的物資裝箱順序是固定的，但是同一個需求點的貨物裝箱順序并不唯一。本文采用Oj(j=1,2,3)規則中的一個規則對初始貨物順序進行調整，確定最終貨物裝載順序[6]。對于初始裝貨序列中相同級別的貨物(屬于相同顧客且同為非易碎品或同為易碎品的貨物)，O1、O2和O3分別表示把貨物按體積(w·l·h)、底面積(w·l)和高度h的降序進行排列，其意義在于：O1規則優先裝載體積較大的貨物，以占據較大的可行裝貨空間；O2規則優先裝載底面積較大的貨物，為后續裝載的貨物提供較大的支撐區域；O3規則優先裝載較高的貨物，因為較小的貨物更容易放在其他貨物之上。

2.2.2 確定可行裝貨位置

機艙內的可行裝貨位置指的是裝貨列表中的下一個貨物能夠放置的位置。每裝入一個貨物之后，可行裝貨位置會發生變化。通?？尚醒b貨位置并不唯一，那么我們需要對可行裝貨位置按某種規則進行排序。已發表的文獻中給出了幾種確定可行裝貨位置的方法，但是這些方法通常僅按照固定的規則逐一嘗試，容易造成后面的貨物不能全部裝入車廂，需要進行重復計算，降低了求解效率。因此，本文給出一種新的基于匹配規則的啟發式裝箱方法，充分考慮到貨物與位置之間的匹配關系，將待裝貨物放在最合適的位置上，盡可能充分節省空間，以提高一次裝箱成功率。

對于列表中的第一個貨物，我們通常將它放置在機艙內的左下角。當我們描述把貨物放在某個位置時，則表示該貨物左下角的坐標落在該位置點上。此外，由于所有貨物占據的網格數均為整數，因此某個點被貨物占據的意思就是，包含該點且處于其右上方的網格被該貨物占據。例如，點O處放置一個貨物，則(0, 0)、(0, 1)、(1, 0)和(1, 1)所組成的網格被該貨物占據。當裝入一些貨物之后可能會出現一系列新的裝貨位置。

在所有的可行裝貨位置中，我們下一步要做的事情就是根據當前貨物的形狀，選擇一個最理想的位置作為當前裝貨位置。在確定最理想裝貨位置的時候，我們應當遵循一個最基本的原則，就是充分節省空間?；谶@樣的原則，我們給出如下規則對可行裝貨點進行排序，得到每個可行裝貨點的優先級。本文采用引導式排序方法給出可行裝貨位置順序，引導式排序方法包括“Back-Left-Low”、“Left-Back-Low”、“Max-Touching-Area-Y”、“Max-Touching-Area-No-Walls-Y”、“Max-Touching-Area-X”及“Max-Touching-No-Walls-X”等六種[11]，實際操作中依次選擇六種方法中的一個，直至找到可行裝載方案。具體實施方法見文獻[11]。

2.3 混合算法

本文把量子粒子群算法和引導式局部搜索算法結合起來，構造求解軍事空運裝載與路徑聯合優化模型的引導式局部搜索量子粒子群算法(Guided Local Search-Quantum-behaved Particle Swarm Optimization Algorithm，GLS-QPSO)。GLS-QPSO算法的基本思路為：通過量子粒子群算法得到路徑優化模型的近似最優解集，近似最優解集中保存適應度靠前的若干粒子；把最優解集中的粒子按適應度從大到小排列，選擇第一個粒子作為當前運輸路線方案，然后調用引導式局部搜索算法；如果找到可行裝箱方案，則返回最優解，否則，依次選擇最優解集中的下一個解作為運輸路線方案；如果最優解集中所有運輸路線方案均找不到可行解，則返回量子粒子群算法重新求解路徑優化問題；重復算法直至找到可行解，或達到最大迭代次數。若達到最大迭代次數仍未找到最優解，則應考慮減少需求點或物資數量，或者增加運輸機總數，然后重新執行GLS-QPSO算法。

3 數值試驗

假設某次戰斗需要應急空運一批裝備物資，已知條件有：1個物資倉庫(機場)，8個物資需求點(P1，P2，…，P8)，坐標如圖2所示，在圖2中每單位距離表示150 km；3架某型號運輸機可供調度，參考文獻[]中的飛機參數設定，飛機允許重心范圍為20%bA～40%bA(bA為平均空氣動力弦)，具體數值見表2；共有6種物資需要運送，物資規格見表3；物資倉庫備有充足物資，各個需求點的物資需求量見表4。

數值試驗采用Matlab 7.1軟件實現，計算機CPU為英特爾酷睿Ⅱ、2.67GHz，4GB內存，64位windows 8操作系統。

圖2 機場及物資需求點坐標示意圖

型號貨艙長度貨艙寬度貨艙高度巡航速度最大有效載重最大油量航程運-818 0m3 0m3 0m550km/h20t3440km

表3 物資規格參數

表4 各需求點的物資需求量

通過優化得到3條運輸機航行線路，且飛機的可行裝載方案均全部找到。所有飛機行駛總距離為601.9 km，具體線路為：

Route1：Depot-N2-N3-Depot，物資總重量10 753 kg，飛機行駛距離219.5 km；

Route2：Depot-N1-N4-N5-Depot，物資總重量13 808 kg，飛機行駛距離211.8 km；

Route3：Depot-N6-N7-N8-Depot，物資總重量18 084 kg，飛機行駛距離170.6 km。

4 結 語

在現有關于軍事空運的研究成果中，通常分別研究空運線路優化和空運裝載優化這兩個問題，實際應用中具有很大的局限性。本文將路徑方案和裝載方案聯合起來進行優化，能夠有效避免產生不可行方案、提高軍事空運效率。數值試驗表明，本文所提出的模型和算法具有很好的應用效果，能夠有效解決軍事空運路徑和裝載聯合優化問題并進行求解。本文模型具有較強的擴展性，實際應用中可根據具體情境設置、調節模型參數，或者適當增加、刪減部分約束條件。比如，考慮起飛和降落過程中的非勻速飛行狀態，可將飛行速度設定為分段函數；考慮到油量與航程之間的關系，可將油量作為載重貨物一并計算重量，同時飛機的最大航程則要轉換為油量的非線性函數；物資需求點對物資供應時間有較高要求，可增加時間窗約束；等等。

[1] 周樹德. 基于分布估計算法的軍事物流配送中心選址決策[J]. 中國電子科學研究院學報, 2010, 05(5): 532-536.

[2] 孟沖，宋華文，陳柏松. 基于0-1整數線性規劃的軍事空運裝載優化算法[J]. 西南交通大學學報，2011，46(3): 500-505.

[3] 張軍，陳柏松，王新虎，李良峰. 軍事空運裝載問題的禁忌搜索算法實現[J]. 國防交通工程與技術，2010，8(6)：10-13.

[4] 孟沖. 航空兵應急轉場空運裝載方案優化研究[D]. 西安：空軍工程大學，2009.

[5] Marcel Mongeau, Christian Bes. Optimization of aircraft container loading[J]. IEEE Transactions on Aerospace & Electronic Systems, 2003, 39(1): 140-150.

[6] Ruan QF, Zhang ZQ, Miao LX, et al. A hybrid approach for the vehicle routing problem with three-dimensional loading constraints[J]. Computers & Operations Research, 2011, 38(11): 1-11.

[7] Junqueira L, Morabito R, Yamashita DS. Three-dimensional container loading modes with cargo stability and load bearing constraints[J]. Computers & Operations Research, 2012, 39(1): 74-85.

[8] Kennedy J, Eberhart RC. Swarm Intelligence[M]. Morgan Kaufman Publishers, San Francisco, 2001: 3-54.

[9] Ai T, Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery[J]. Computers & Operations Research, 2009, 36(5): 1693-1702.

[10]Wu Z. Optimization of distribution route selection based on particle swarm algorithm[J]. International Journal of Simulation Modelling, 2014, 13 (2): 230-242.

[11]Tarantilis CD, Zachariadis EE, Kiranoudis CT. A Hybrid Metaheuristic Algorithm for the Integrated Vehicle Routing and Three-Dimensional Container-Loading Problem

[C]. Transactions on Intelligent Transportation Systems, 10(2): 255-271.

顏 瑞(1986—)，江蘇人，講師，博士，主要研究方向為物流優化、智能算法；

馬曉娟(1994—)，寧夏人，碩士研究生，主要研究方向為項目管理；

梁廷政(1981—),山西人，助理研究員，主要研究方向為項目管理；

王 雷(1980—)，遼寧人，講師，博士，主要研究方向為應急管理、公共安全管理。

Research on Optimal Joint Problem of Routing and Loading in Military Airlift

YAN Rui1,MA Xiao-Juan2,LIAN Ting-zheng3,WANG Lei4

(1. Beijing Information Science & technology University, Beijing 100192; 2. University of Science and Technology Beijing, Beijing 100083; 3. The sustainable development of science and technology promotion center of Beijing, Beijing 100035; 4. National Police University of China, Shenyang 110035)

In order to formulate routing plan and loading plan in military airlift effectively and rapidly, as well as obtain the feasible loading plan while identifying the optimal transportation path, it is necessary to combine the routing problem and loading problem in military airlift together. This paper is an attempt to study the joint optimal model of routing and loading in military airlift. A hybrid algorithm of quantum behaved particle swarm optimization algorithm and guided local search algorithm is employed to solve this optimal joint model. The feasibility of this model and the effectiveness of the hybrid algorithm are tested by an experiment. The results of the experiment show that the optimal joint problem of routing and loading in military airlift can reflects facts more reasonably, and the hybrid algorithm can obtain the approximate optimal solution for this model.

military airlift; routing plan; loading plan; joint optimization; quantum behaved particle swarm optimization algorithm

10.3969/j.issn.1673-5692.2017.01.002

2016-10-15

2016-12-15

國家自然科學基金項目(71602008);北京市哲學社科規劃項目(16JDGLC032);北京市哲學社科規劃項目(14JDJC018);公安部公安理論與軟科學計劃項目(2016LLYJXJXY032);遼寧省社會科學規劃基金項目(L16BGL042)。

U8

A

1673-5692(2017)01-007-07