軍事空運(yùn)路徑與裝載聯(lián)合優(yōu)化問題研究

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

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

軍事空運(yùn)路徑與裝載聯(lián)合優(yōu)化問題研究

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

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

為了有效、快速制定軍事空運(yùn)路徑和裝載方案，在計(jì)算出最優(yōu)運(yùn)輸路徑的同時(shí)獲取可行裝載方案，針對軍事空運(yùn)路徑和裝載的聯(lián)合優(yōu)化問題進(jìn)行研究。建立軍事空運(yùn)路徑和裝載聯(lián)合優(yōu)化模型，提出一種結(jié)合量子粒子群算法和引導(dǎo)式局部搜索算法的混合算法進(jìn)行求解，通過數(shù)值試驗(yàn)檢驗(yàn)?zāi)Ｐ偷目尚行院退惴ǖ挠行?。試?yàn)結(jié)果表明，聯(lián)合優(yōu)化模型能夠有效實(shí)現(xiàn)軍事空運(yùn)路徑和裝載聯(lián)合優(yōu)化問題的建模過程，且混合算法能夠有效獲取聯(lián)合優(yōu)化模型的近似最優(yōu)解。

軍事空運(yùn)；路徑方案；裝載方案；聯(lián)合優(yōu)化；量子粒子群算法

0 引 言

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

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

1 模型建立

1.1 問題描述及模型假設(shè)

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

軍事空運(yùn)裝載方案與路徑方案聯(lián)合優(yōu)化模型的假設(shè)：

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

(2)任意兩個(gè)節(jié)點(diǎn)之間均有固定航線，運(yùn)輸機(jī)可以執(zhí)行所有航線上的任務(wù)，所有運(yùn)輸機(jī)為同一型號；

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

(4)每個(gè)需求點(diǎn)只能在一條回路上，每條回路上的需求點(diǎn)僅由一架運(yùn)輸機(jī)服務(wù)(即為非滿載運(yùn)輸問題)；

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

(6)每條回路上需求點(diǎn)的物資需求總重量不能超過運(yùn)輸機(jī)的最大載重，物資總體積不能超過運(yùn)輸機(jī)機(jī)艙內(nèi)的最大容積；

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

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

(9)每條回路上物資需求點(diǎn)的物資必須全部裝入運(yùn)輸機(jī)內(nèi)，且滿足全部給定的裝載約束；

(10)以所有運(yùn)輸機(jī)的飛行時(shí)間之和最小為目標(biāo)。

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

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

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

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

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

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

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

1.2 模型符號及符號解釋

建立聯(lián)合優(yōu)化模型之前需要將機(jī)艙空間轉(zhuǎn)化為，以機(jī)艙內(nèi)側(cè)左下角為坐標(biāo)原點(diǎn)，以機(jī)艙最邊緣的長、寬和高為坐標(biāo)軸，建立笛卡爾坐標(biāo)系。表1給出模型中的所有符號，并解釋每個(gè)符號的意義。

表1 模型符號及符號解釋

1.3 數(shù)學(xué)模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

在建立裝載優(yōu)化模型之前，需要先建立一個(gè)笛卡爾坐標(biāo)系。坐標(biāo)系的坐標(biāo)軸分別對應(yīng)于運(yùn)輸機(jī)外切長方體的長、寬和高，如圖1所示。

圖1 運(yùn)輸機(jī)外切長方體及笛卡爾坐標(biāo)系示意圖

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

貨物i底部左前方的位置用坐標(biāo)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。

受到物資三維形狀的限制，即使單架運(yùn)輸機(jī)的物資總體積小于其裝載空間總?cè)莘e，也有可能發(fā)生無法將所有物資全部裝入機(jī)艙內(nèi)的情況?？紤]到這一點(diǎn)，本文以最大化裝入機(jī)艙內(nèi)的貨物總數(shù)為目標(biāo)建立裝載優(yōu)化模型，則可行解的目標(biāo)函數(shù)值等于物資總數(shù)。裝載優(yōu)化模型如下：

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

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

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

本文提出一種結(jié)合量子粒子群算法和引導(dǎo)式局部搜索算法的混合算法求解軍事空運(yùn)裝載與路徑聯(lián)合優(yōu)化模型。本節(jié)將詳細(xì)描述混合算法的基本原理、各部分策略和實(shí)施步驟。

2.1 改進(jìn)的量子粒子群算法

2.1.1 基礎(chǔ)量子粒子群算法

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

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

(18)

(19)

u=rand(0,1)

(20)

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

(21)

量子粒子群優(yōu)化算法過程如下：

Step1.初始化種群，粒子的初始位置通過隨機(jī)方式產(chǎn)生；

Step2.對于每一個(gè)粒子，計(jì)算其適應(yīng)值，保存每個(gè)粒子歷史最優(yōu)值Pid，以及所有粒子的最優(yōu)值Pgd；

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

Step4.對于粒子的每一個(gè)維，通過公式(19)得到一個(gè)隨機(jī)點(diǎn)；

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

Step6.執(zhí)行局部擾動(dòng)操作；

Step7.重復(fù)Step2-Step6，直至達(dá)到最大迭代次數(shù)。

2.1.2 局部擾動(dòng)

為了提高QPSO的尋優(yōu)效率，本文采用2-opt和線路內(nèi)部搜索兩個(gè)方法進(jìn)行局部擾動(dòng)，這兩種方法類似于遺傳算法中的變異算子。2-opt作用于兩條線路上，具體操作方法是：隨機(jī)選擇兩條線路，并隨機(jī)選擇兩個(gè)位置，將兩條線路上的對應(yīng)節(jié)點(diǎn)進(jìn)行互換。線路內(nèi)部搜索作用于單條線路上，具體操作方法是：隨機(jī)選擇一條線路，并隨機(jī)選擇兩個(gè)位置，將兩個(gè)位置對應(yīng)的節(jié)點(diǎn)進(jìn)行互換。

2.2 引導(dǎo)式局部搜索算法

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

2.2.1 確定待裝貨物順序

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

2.2.2 確定可行裝貨位置

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

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

在所有的可行裝貨位置中，我們下一步要做的事情就是根據(jù)當(dāng)前貨物的形狀，選擇一個(gè)最理想的位置作為當(dāng)前裝貨位置。在確定最理想裝貨位置的時(shí)候，我們應(yīng)當(dāng)遵循一個(gè)最基本的原則，就是充分節(jié)省空間?；谶@樣的原則，我們給出如下規(guī)則對可行裝貨點(diǎn)進(jìn)行排序，得到每個(gè)可行裝貨點(diǎn)的優(yōu)先級。本文采用引導(dǎo)式排序方法給出可行裝貨位置順序，引導(dǎo)式排序方法包括“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]，實(shí)際操作中依次選擇六種方法中的一個(gè)，直至找到可行裝載方案。具體實(shí)施方法見文獻(xiàn)[11]。

2.3 混合算法

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

3 數(shù)值試驗(yàn)

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

數(shù)值試驗(yàn)采用Matlab 7.1軟件實(shí)現(xiàn)，計(jì)算機(jī)CPU為英特爾酷睿Ⅱ、2.67GHz，4GB內(nèi)存，64位windows 8操作系統(tǒng)。

圖2 機(jī)場及物資需求點(diǎn)坐標(biāo)示意圖

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

表3 物資規(guī)格參數(shù)

表4 各需求點(diǎn)的物資需求量

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

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

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

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

4 結(jié) 語

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

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

[2] 孟沖，宋華文，陳柏松. 基于0-1整數(shù)線性規(guī)劃的軍事空運(yùn)裝載優(yōu)化算法[J]. 西南交通大學(xué)學(xué)報(bào)，2011，46(3): 500-505.

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

[4] 孟沖. 航空兵應(yīng)急轉(zhuǎn)場空運(yùn)裝載方案優(yōu)化研究[D]. 西安：空軍工程大學(xué)，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—)，江蘇人，講師，博士，主要研究方向?yàn)槲锪鲀?yōu)化、智能算法；

馬曉娟(1994—)，寧夏人，碩士研究生，主要研究方向?yàn)轫?xiàng)目管理；

梁廷政(1981—),山西人，助理研究員，主要研究方向?yàn)轫?xiàng)目管理；

王 雷(1980—)，遼寧人，講師，博士，主要研究方向?yàn)閼?yīng)急管理、公共安全管理。

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

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

U8

A

1673-5692(2017)01-007-07