趙向領(lǐng)， 李云飛*， 李鵬飛

(1.中國(guó)民航大學(xué)空中交通管理學(xué)院， 天津 300300； 2.空軍某部隊(duì)， 武漢 430000)

近年來(lái)，隨著航空運(yùn)輸業(yè)的快速發(fā)展，這種快速、高效、經(jīng)濟(jì)的運(yùn)輸方式深受客戶青睞，作為地面保障工作之一的配載平衡工作仍存在著優(yōu)化空間。為保證飛機(jī)在投入運(yùn)行后能夠?qū)崿F(xiàn)安全且經(jīng)濟(jì)的運(yùn)行，同時(shí)便于飛行員輕松操縱，載重平衡工作成為亟待進(jìn)一步研究?jī)?yōu)化解決的一個(gè)問(wèn)題。為解決上述問(wèn)題，現(xiàn)通過(guò)建立整數(shù)規(guī)劃模型，使用改進(jìn)的遺傳算法進(jìn)行求解，以期望使得上述目標(biāo)能夠較好地滿足航司要求。

1 問(wèn)題描述

某些最初設(shè)計(jì)為客機(jī)的飛機(jī)可以在必要時(shí)改裝成多用途飛機(jī)來(lái)運(yùn)載貨物。特別是近期暴發(fā)的疫情更是加快了客機(jī)改裝進(jìn)程。飛機(jī)所裝載的貨物類型可以是同類型的也可以是不同類型的。對(duì)于航空公司而言，飛機(jī)的配載問(wèn)題是在考慮貨物體積和重量約束以及飛機(jī)結(jié)構(gòu)約束的情況下，找到飛機(jī)上貨物的最優(yōu)裝載分布，以實(shí)現(xiàn)飛機(jī)在運(yùn)行過(guò)程中的平衡，確保飛機(jī)安全起飛和降落。

目前航空公司所存在的飛機(jī)載重平衡問(wèn)題的本質(zhì)是考慮如何合理地分配貨物到飛機(jī)的艙位，實(shí)現(xiàn)飛機(jī)重心位置最優(yōu)和業(yè)載量最大。由于問(wèn)題的復(fù)雜度較大，2015年Feng 等[1]在總結(jié)當(dāng)前航空貨物運(yùn)行的文獻(xiàn)時(shí)指出，飛機(jī)的配載問(wèn)題是航空運(yùn)輸中最基本的多項(xiàng)式非確定性問(wèn)題(non-deterministic polynomial，NP)-難題組合優(yōu)化問(wèn)題之一。近年來(lái)在載重平衡問(wèn)題的求解方法多集中在啟發(fā)式智能算法和快速發(fā)展的商用求解器上。

有關(guān)使用啟發(fā)式智能算法求解載重平衡問(wèn)題的相關(guān)文獻(xiàn)有Dahmani 等[2-3]提出的多目標(biāo)粒子群優(yōu)化方法，將一組貨物分配到最小數(shù)量的集裝器中，然后將其放置到飛機(jī)特定的貨艙內(nèi)，模型考慮了優(yōu)化業(yè)載總重量和優(yōu)先級(jí)；謝春生[4]運(yùn)用遺傳算法建立了民航客機(jī)的裝載配平模型，并以B747客機(jī)為例開發(fā)了可視化軟件，解決了客機(jī)配載員工作強(qiáng)度大、效率低的問(wèn)題；張洪[5]運(yùn)用改進(jìn)的蟻群算法開發(fā)了面向C919的配載優(yōu)化系統(tǒng)；趙向領(lǐng)等[6]建立了民航客改貨飛機(jī)的載重配平模型，用于解決航空器配載問(wèn)題，模型以運(yùn)輸業(yè)載量最大和重心位置最優(yōu)為目標(biāo)，并運(yùn)用遺傳算法進(jìn)行的求解。谷潤(rùn)平等[7]以貨機(jī)裝載重心最優(yōu)為目標(biāo)函數(shù)，建立了以重心、重量、結(jié)構(gòu)等約束的混合整數(shù)規(guī)劃模型，依然使用遺傳算法求解；史永勝等[8]以貨機(jī)主貨艙為研究對(duì)象，建立了重心偏移量最小的目標(biāo)函數(shù)以重心位置、貨艙結(jié)構(gòu)、彎矩等為約束條件的整數(shù)規(guī)劃模型，運(yùn)用遺傳算法進(jìn)行求解；鄭琰等[9]研究了貨機(jī)群裝載非標(biāo)準(zhǔn)貨物的優(yōu)化問(wèn)題，建立了以重心率和空間利用率的目標(biāo)函數(shù)模型，運(yùn)用啟發(fā)式算法進(jìn)行求解；陳璇等[10]采用自適應(yīng)煙花算法對(duì)大型航空運(yùn)輸機(jī)裝載優(yōu)化模型求解，裝載模型考慮重量、重心、容積、系留等約束條件；孟超[11]針對(duì)民航寬體客機(jī)腹艙以綜合載重利用率和容積利用率最大為目標(biāo)，運(yùn)用啟發(fā)式算法和混和遺傳粒子群算法進(jìn)行求解；白楊[12]分析了客機(jī)腹艙和全貨機(jī)載貨兩種情況的裝載特點(diǎn)，并建立混合整數(shù)規(guī)劃模型，使用基于有效空間的啟發(fā)式算法求解；朱賀[13]針對(duì)貨物需要送達(dá)同一目的地和貨物送到不同目的地，部分貨物在中途卸載或者空投的情況，采用了混合整數(shù)規(guī)劃模型分別對(duì)這兩種問(wèn)題進(jìn)行了建模，分別采用了精確求解和元啟發(fā)求解，并建立相應(yīng)的軟件系統(tǒng)原型。

在使用商業(yè)求解載重平衡問(wèn)題方面的文獻(xiàn)有Limbourg等[14]建立的以貨物力矩、飛機(jī)結(jié)構(gòu)應(yīng)力和燃油成本最小的混合整數(shù)線性規(guī)劃模型，可以將一組選定的貨物分配到飛機(jī)的預(yù)定位置，并以B747為研究對(duì)象使用商業(yè)求解器CPLEX驗(yàn)證了模型的有效性；Verstichel等[15]及Vancroonenburg等[16]建立以裝載貨物價(jià)值最大和重心偏移量最小的雙目標(biāo)規(guī)劃模型，用于解決B747貨艙中貨物裝載平衡的問(wèn)題，使用Gurobi求解對(duì)比了人工配載專家的配載結(jié)果，驗(yàn)證了模型的可行性和Gurobi的強(qiáng)大；Lurkin等[17]建立以燃油成本和操作成本最小的混合整數(shù)線性模型，考慮了飛機(jī)重心約束，用于解決在中間機(jī)場(chǎng)取貨和交付的飛機(jī)裝載問(wèn)題，以B777為研究對(duì)象并使用IBM公司的CPLEX進(jìn)行仿真驗(yàn)證模型；Zhao等[18]把非線性重心包線描述為多段線性約束模型，并設(shè)計(jì)了線性化策略，在考慮位置、重量、平衡等約束條件下，建立了總業(yè)載最大、重心偏差最小的混合整數(shù)規(guī)劃模型。模型使用商業(yè)求解器CPLEX可在幾秒鐘內(nèi)得到最優(yōu)解，并且在所有測(cè)試實(shí)例中保持重心在指定的重心包線范圍內(nèi)；李云飛等[19]使用Lingo求解器驗(yàn)證了客改貨飛機(jī)的上下艙聯(lián)合載重平衡模型。

綜上所述，國(guó)內(nèi)外對(duì)于載重平衡問(wèn)題通常建立整數(shù)規(guī)劃模型，使用啟發(fā)式智能算法和商業(yè)求解器進(jìn)行求解。但國(guó)內(nèi)單獨(dú)對(duì)于載重平衡的研究較少，多數(shù)是將載重平衡問(wèn)題作為研究航空貨運(yùn)三維裝箱問(wèn)題一個(gè)階段，考慮的約束不全面，致使模型不完整。另外對(duì)于客改貨這種新的運(yùn)輸模式的載重平衡的研究還比較少。因此現(xiàn)運(yùn)用改進(jìn)的遺傳算法研究客改貨窄體機(jī)的載重平衡問(wèn)題。

2 載重平衡模型構(gòu)建

2.1 模型概述

根據(jù)目前的主流窄體機(jī)選定波音757-200為研究對(duì)象，為滿足貨艙業(yè)載量最大和重心偏移量最小的目標(biāo)，需要建立貨艙的配載優(yōu)化模型。

圖1是B757-200的貨艙側(cè)視圖，可以看出共有15個(gè)主貨艙、4個(gè)下貨艙。貨機(jī)的貨艙主要用來(lái)裝載集裝器，下貨艙裝載散貨，此次主要研究主貨艙的載重平衡問(wèn)題。

圖1 B757-200貨機(jī)側(cè)視圖Fig.1 Side view of B757-200 cargo plane

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

在模型建立之前首先設(shè)決策變量xij為

(1)

式(1)中：i為第i個(gè)待裝載集裝器；j為第j個(gè)飛機(jī)貨艙艙位；NULD為待裝載集裝器總數(shù)；NPOS為飛機(jī)主貨艙可分配位置的總量。

為保證航空公司運(yùn)輸利潤(rùn)最大化和飛機(jī)運(yùn)行安全，建立了以裝載量最大和重心偏移量最小的雙目標(biāo)模型為

(2)

式(2)中：Wi為第i個(gè)待裝載集裝器的重量；CGOPT和CGTOW分別為飛機(jī)起飛最優(yōu)重心和飛機(jī)在起飛重量(takeoff weight,TOW)時(shí)的重心，其中CGTOW的計(jì)算公式為

(3)

式(3)中：LEMAC為基準(zhǔn)到平均空氣動(dòng)力弦前緣的長(zhǎng)度；MAC(mean aerodynamic chord)為平均空氣動(dòng)力弦長(zhǎng)；BATOW(balance arm)為起飛重量下的力臂值，計(jì)算公式為

(4)

式(4)中：OEW(operation empty weight)為飛機(jī)的空機(jī)重；BAOEW為飛機(jī)的空機(jī)重對(duì)應(yīng)的力臂值；TFW(fuel weight)為飛機(jī)的起飛燃油重量；BATFW為燃油重量對(duì)應(yīng)的力臂值；BAj為飛機(jī)第j個(gè)艙位的力臂值。

根據(jù)一線配載實(shí)際工作情況，現(xiàn)需要將雙目標(biāo)函數(shù)冠以不同的權(quán)重ω1和ω2，且ω1+ω2=1，與此同時(shí)將目標(biāo)函數(shù)做歸一化處理，將其轉(zhuǎn)化為單目標(biāo)函數(shù)，即

(5)

式(5)中：MPL(max pay load)為飛機(jī)的最大業(yè)載；12.5為重心包線前后限的一半，以%MAC表示。

2.3 約束條件

在對(duì)飛機(jī)貨艙集裝器裝載方案進(jìn)行布局優(yōu)化時(shí)，需要結(jié)合實(shí)際情況考慮約束，約束條件如下。

(1)保證每個(gè)集裝器最多放置在一個(gè)艙位內(nèi)。

(6)

(2)每個(gè)艙位必須保證有一個(gè)集裝器。

(7)

(3)集裝器重量應(yīng)不超過(guò)集裝器所在艙位的最大重量。

(8)

式(8)中：MWj為飛機(jī)第j個(gè)艙位的最大載荷。

(4)為保證集裝器可以完全裝載到貨艙內(nèi)和飛機(jī)內(nèi)壁不受損，貨艙內(nèi)通常會(huì)有集裝器高度限制，所裝載的集裝器不能超過(guò)所在艙位能容納的最大高度。

(9)

式(9)中：Hi為第i個(gè)待裝載集裝器的高度；MHj為第j個(gè)艙位的最大高度。

(5)飛機(jī)的主貨艙內(nèi)一般還存在著分艙位區(qū)域限重，主要考慮1～5艙，6～10艙，11～15艙所在區(qū)域重量限重。

{(s,t)}∈{(1,5),(6,10),(11,15)}

(10)

式(10)中：MWst為主貨艙s到t艙的重量限制。

(6)飛機(jī)在運(yùn)行中會(huì)受到最大無(wú)油重量(max zero fuel weight，MZFW)、最大起飛重量(max takeoff weight，MTOW)、最大著陸重量(max landing weight，MLW)的限制，儲(chǔ)備燃料重量(reserve fuel weight，RFW)為飛機(jī)的備用油量。

(11)

(12)

(13)

(7)飛機(jī)在運(yùn)行中還會(huì)受到最大業(yè)載的限制。

(14)

MPL的計(jì)算公式為

MPL=min{MZFW-OEW，MTOW-OEW-

TFW，MLW-OEW-RFW}

(15)

(8)為保證飛機(jī)的安全運(yùn)行，飛機(jī)的重心必須時(shí)刻處于重心前后限的范圍之間。式(16)為飛機(jī)在不同重量下的重心限制，其中minINDw和maxINDw分別為飛機(jī)在不同重量下所對(duì)應(yīng)的重心包線前后限，而INDw為在不同重量下配載結(jié)果對(duì)應(yīng)的指數(shù)，通過(guò)式(17)計(jì)算獲得，即

(16)

w∈{TOW,LW,ZFW}

(17)

式中：BI為空機(jī)重指數(shù)；FIw為飛機(jī)不同重量時(shí)對(duì)應(yīng)燃油指數(shù)；C1為縮小系數(shù)；CGDATUM為平衡基準(zhǔn)點(diǎn)站位,對(duì)于給定航班為已知數(shù)據(jù)。

3 載重平衡問(wèn)題求解

擬采用遺傳算法來(lái)求解載重平衡問(wèn)題，遺傳算法是根據(jù)自然界的進(jìn)化理論和遺傳學(xué)說(shuō)所創(chuàng)造的一種啟發(fā)式算法。使用適者生存的原則來(lái)逐步逼近一個(gè)可行的近似解，這個(gè)過(guò)程使得新個(gè)體比原個(gè)體更能適應(yīng)環(huán)境。圖2是遺傳算法流程圖。

圖2 遺傳算法流程圖Fig.2 Genetic algorithm flow chart

3.1 編碼方式

圖3 編碼方式示意圖Fig.3 Schematic diagram of coding mode

3.2 適應(yīng)度函數(shù)

由于將雙目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)之后，仍是求解模型的最大值因此將目標(biāo)函數(shù)[式(5)]作為適應(yīng)度函數(shù)。

3.3 選擇算子

對(duì)于選擇算子的設(shè)計(jì)在這里仍采用常見的輪盤賭，輪盤賭是指?jìng)€(gè)體被選中的概率與適應(yīng)度成正比，適應(yīng)度越高，個(gè)體被選中的概率越大。對(duì)于該模型而言，假設(shè)種群個(gè)體數(shù)為P,Fp為其中某個(gè)個(gè)體的適應(yīng)度值，那么個(gè)體被選擇遺傳到下一代的概率Pp為

(18)

3.4 交叉算子

交叉操作是遺傳算法最重要的操作，是產(chǎn)生新個(gè)體的重要來(lái)源，直接關(guān)系到算法的全局尋優(yōu)能力，采用部分映射交叉，即在滿足給定交叉概率下，隨機(jī)生成某條染色體上交叉位置。具體操作如下。

隨機(jī)產(chǎn)生兩個(gè)[1,10]的隨機(jī)數(shù)r1和r2，代表選擇交叉的位置，比如r1=2、r2=4,如圖4中灰色的位置，將第一個(gè)個(gè)體r1到r2之間的基因(即集裝器序號(hào))與第二個(gè)個(gè)體r1到r2之間的基因交換，交換之后如圖5所示。

圖4 交叉前示意圖Fig.4 Schematic diagram of crossover

圖5 交叉后示意圖Fig.5 Schematic diagram after crossing

灰色部分表示交叉過(guò)來(lái)的基因，然而仔細(xì)觀察后發(fā)現(xiàn)交叉過(guò)來(lái)的基因與原來(lái)其他位置上的基因可能會(huì)有重復(fù)，第一個(gè)裝載方式重復(fù)基因的數(shù)目與第二個(gè)裝載方式重復(fù)基因的數(shù)目是相同的(這里都是3個(gè))，只需要把第一個(gè)裝載方式重復(fù)的基因(用黑色標(biāo)識(shí))與第二個(gè)裝載方式重復(fù)的基因做交換，即可以消除沖突。消除沖突之后的解如圖6所示。

圖6 解除交叉沖突示意圖Fig.6 Schematic diagram for removing cross conflict

3.5 變異算子

變異算子的設(shè)計(jì)針對(duì)一個(gè)染色體(即個(gè)體)隨機(jī)選取兩個(gè)基因進(jìn)行交換。例如圖7的變異示意圖，隨機(jī)生成區(qū)間[1，10]的兩個(gè)數(shù)r1、r2分別為3和8，然后將位置3和位置8互換基因。

圖7 變異算子示意圖Fig.7 Schematic diagram of mutation operator

3.6 進(jìn)化逆轉(zhuǎn)操作算子

在標(biāo)準(zhǔn)的遺傳算法中是沒(méi)有進(jìn)化逆轉(zhuǎn)操作算子的，為了加速進(jìn)化在選擇、交叉、變異之后加入的一個(gè)操作。進(jìn)化逆轉(zhuǎn)操作是具有單向性的，若逆轉(zhuǎn)之后個(gè)體變得更優(yōu)即適應(yīng)度越大，則執(zhí)行逆轉(zhuǎn)操作，否則逆轉(zhuǎn)無(wú)效。逆轉(zhuǎn)算子在操作時(shí)仍是隨機(jī)選擇兩個(gè)位置r1和r2,然后將r1和r2之間的基因進(jìn)行反向排序。比如對(duì)于某個(gè)裝載方式隨機(jī)選擇位置r1=3，r2=5，將其之間的基因按照相反順序倒過(guò)來(lái)。具體操作如圖8所示。

圖8 進(jìn)化逆轉(zhuǎn)操作示意圖Fig.8 Schematic diagram of evolutionary reversal operation

在文獻(xiàn)[20-22]中，逆轉(zhuǎn)算子的加入使得子代繼承了更多的父代基因信息，由于只往好的方向逆轉(zhuǎn)，因此在搜索最優(yōu)解的能力比順序交叉算子更強(qiáng)。

3.7 約束條件處理

在處理約束條件時(shí)運(yùn)用文獻(xiàn)[23]中的y-check思想，具體過(guò)程為將每次的解代入各個(gè)約束條件中進(jìn)行判斷。

約束(5)和約束(6)在編碼方式上已經(jīng)處理完成無(wú)需考慮。

約束(7)和約束(8)在生成初始解就進(jìn)行判斷，直到滿足約束(7)和約束(8)初始解輸出進(jìn)行下一步工作。

計(jì)算目標(biāo)函數(shù)，滿足約束(9)～約束(17)輸出解。

4 仿真實(shí)例

4.1 算例數(shù)據(jù)

某次航班任務(wù)執(zhí)飛機(jī)型為B757-200F，飛行計(jì)劃報(bào)顯示此次飛行任務(wù)所帶起飛油量10 000 kg，航段耗油量為8 000 kg，表1給出了B757-200F的基本參數(shù)包括3類最大重量等，表2是每個(gè)艙位所能容納集裝器的最大重量和高度，表3為待裝載的集裝器基本信息。

表1 B757-200F基本參數(shù)Table 1 Basic parameters of B757-200F

表2 貨艙艙位約束Table 2 Constraints in main cargo compartment

表3 集裝器重量、高度Table 3 Weight and height of ULD

4.2 算例計(jì)算

此次算法程序在Visual Studio 2019 下運(yùn)行，設(shè)ω1=0.8，ω2=0.2，在遺傳算法中設(shè)置種群規(guī)模PS為200，遺傳進(jìn)化代數(shù)Gen為200，交叉率PC為0.9，變異率PM為0.1，表4為計(jì)算結(jié)果，可知遺傳算法業(yè)載量平均為21 281 kg，重心偏移量平均為2.309%MAC，人工配載業(yè)載量為20 565.6 kg，重心偏移量平均為4.846%MAC。加入進(jìn)化逆轉(zhuǎn)算子后只加快了收斂速度，所計(jì)算的結(jié)果與普通遺傳算法保持一致。

表4 計(jì)算結(jié)果Table 4 Calculation results

圖9是引入進(jìn)化逆轉(zhuǎn)算子的遺傳算法和普通遺傳算法的適應(yīng)度變化曲線，可以看出改進(jìn)的遺傳算法可以較快得到目標(biāo)值。

圖9 遺傳算法適應(yīng)度變化曲線Fig.9 Fitness curve of genetic algorithm

圖10和圖11分別是在ω1=0.8下的重量箱線圖和重心偏移箱線圖，可以得出遺傳算法都要優(yōu)于人工計(jì)算，這是因?yàn)檫\(yùn)用遺傳算法時(shí)，可以快速排除質(zhì)量較差的解，保留高質(zhì)量的解，而人工配載一般根據(jù)經(jīng)驗(yàn)，不具有高效性。

圖10 重量箱線圖Fig.10 Weight box diagram

圖11 重心偏移箱線圖Fig.11 Boxplot of center of gravity deviation

4.3 多目標(biāo)權(quán)重分析

為驗(yàn)證算法的有效性，擬多次調(diào)整多目標(biāo)權(quán)重的取值。表5為在不同ω1下所計(jì)算得到的業(yè)載及重心，為保證數(shù)據(jù)的有效性，同一ω1下計(jì)算10組取均值得到。

表5 不同ω1下的業(yè)載及重心偏差Table 5 Payload and center of gravity deviation under different ω1

在每個(gè)權(quán)重下計(jì)算多次得到圖12的業(yè)載量和重心偏移量變化曲線，隨著權(quán)重ω1的減小，業(yè)載量呈降低的趨勢(shì)；在ω1從0.9減小到0.67過(guò)程中，重心偏移量呈接近目標(biāo)重心的趨勢(shì)。因此在實(shí)際情況下，各航司可以根據(jù)需要來(lái)選取不同的權(quán)重ω1滿足需求。

圖12 不同ω1下的業(yè)載及重心偏差Fig.12 Payload and CG deviation under different ω1

5 結(jié)論

載重平衡工作在地面保障工作中發(fā)揮了重大作用。針對(duì)航空公司目前所存在的問(wèn)題，如何獲得一個(gè)可行的裝載優(yōu)化方案，建立了民航飛機(jī)貨艙載重平衡模型，并運(yùn)用改進(jìn)的遺傳算法進(jìn)行求解。對(duì)B757-200F進(jìn)行實(shí)例計(jì)算結(jié)果顯示，平均業(yè)載可達(dá)21 281 kg，平均偏移量為2.31%MAC。由于所選機(jī)型為窄體機(jī)，在今后的研究工作中可以考慮寬體機(jī)的載重平衡問(wèn)題，同時(shí)在重心優(yōu)化上可以考慮將重心包線作為目標(biāo)函數(shù)，來(lái)避免使用重心偏移量作為目標(biāo)函數(shù)使得飛機(jī)重心偶然超出重心范圍。