樊 瑋，別好杰

（中國民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300）

基于NSGA-II的多目標(biāo)航班機(jī)型分配問題研究

樊 瑋，別好杰

（中國民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300）

機(jī)型分配是航空公司運(yùn)營管理中資源優(yōu)化的重要難題之一，在很大程度上影響著航空公司的利潤率及競爭力。針對現(xiàn)有機(jī)型分配方法中求解目標(biāo)的單一性，在基本機(jī)型分配模型的基礎(chǔ)上建立了多目標(biāo)機(jī)型分配模型，即同時(shí)將最大化航空公司利潤和使用最少的飛機(jī)架數(shù)覆蓋全部航班作為目標(biāo)。對于多目標(biāo)數(shù)學(xué)模型求解的復(fù)雜性，采用了NSGA-II算法，以避免求解時(shí)的目標(biāo)偏好性。通過算例對此模型求解，驗(yàn)證了模型的有效性，對比單目標(biāo)機(jī)型分配模型，結(jié)果表明多目標(biāo)機(jī)型分配模型在目標(biāo)空間上分布更均勻，能夠?yàn)楹娇展竞桨鄼C(jī)型分配提供決策支持。

航空運(yùn)輸；機(jī)型分配；NSGA-II算法；多目標(biāo)優(yōu)化；航班

機(jī)型分配問題是指根據(jù)不同機(jī)型的不同座位數(shù)、運(yùn)營成本和潛在收益，分配不同的機(jī)型給各定期航班。近年來，隨著航空運(yùn)輸業(yè)的高速發(fā)展，航空公司的競爭逐步加劇，航線網(wǎng)絡(luò)與資源優(yōu)化已成為航空公司提高競爭力的有效手段，而機(jī)型分配是航線網(wǎng)絡(luò)與資源優(yōu)化的關(guān)鍵方法之一。

目前，有關(guān)機(jī)型分配的國內(nèi)外研究主要包括：Abara[1]在連接網(wǎng)絡(luò)法的基礎(chǔ)上建立了機(jī)型分配模型，該模型以最大化航空公司利潤為目標(biāo)；Brown[2]主要側(cè)重于對樞紐輪輻式航空公司機(jī)隊(duì)規(guī)劃的研究，通過構(gòu)建基于面板數(shù)據(jù)的模型分析了航空管制因素對其機(jī)隊(duì)構(gòu)成的影響，只考慮了放松航空管制后各機(jī)型飛機(jī)架數(shù)在航線上的限制；Hane等[3]構(gòu)建了一種基于時(shí)間拓展網(wǎng)絡(luò)的多商品流模型，用于解決機(jī)型分配的大規(guī)模整數(shù)規(guī)劃問題，在模型求解中用到了內(nèi)點(diǎn)算法，并通過數(shù)據(jù)驗(yàn)證了該模型和算法在解決大規(guī)模整數(shù)規(guī)劃問題上的優(yōu)越性，但此算法的時(shí)間復(fù)雜度較高；Listes等[4]通過情境聚合算法求解基于時(shí)空網(wǎng)絡(luò)的機(jī)型分配模型，模型考慮到了乘客的動態(tài)需求，最后通過實(shí)際數(shù)據(jù)驗(yàn)證了模型和算法的可行性和優(yōu)越性；Barnhart等[5]在基本機(jī)型分配模型（FAM）和基于行程的機(jī)型分配模型（IFAM）的基礎(chǔ)上，提出了一種通用機(jī)型分配模型（GFAM，generic fleet assignment model），該模型以航空公司利潤最大化為目標(biāo)；Shao等[6]綜合考慮了機(jī)型分配與航班計(jì)劃中飛機(jī)排班和機(jī)組排班，并以這3個(gè)階段建立一個(gè)數(shù)學(xué)模型，通過Benders分解法求解；徐進(jìn)[7]構(gòu)建了一種混合整數(shù)規(guī)劃的機(jī)型指派模型，并對時(shí)間窗口的機(jī)型指派問題做了初步分析研究；樂美龍等[8]提出了一種基于時(shí)空網(wǎng)絡(luò)的航班機(jī)型分配模型，該模型以最小化航班機(jī)型分配總成本為目標(biāo)函數(shù)；Liu等[9]在考慮延遲傳播的情況下，結(jié)合機(jī)型分配和飛機(jī)路徑建立了單目標(biāo)數(shù)學(xué)模型。

以上研究雖然考慮的影響因素和優(yōu)化方法有所差異，但其基本約束條件（航班覆蓋、飛機(jī)平衡、機(jī)隊(duì)規(guī)模）基本相同，且目標(biāo)函數(shù)都集中在利潤最大化或最小化運(yùn)營成本其中一個(gè)單一目標(biāo)上，考慮到航空公司實(shí)際需求，本文同時(shí)將最大化航空公司利潤和使用最少的飛機(jī)架數(shù)覆蓋全部航班作為目標(biāo)，在基本機(jī)型分配模型[10-12]的基礎(chǔ)上建立了多目標(biāo)機(jī)型分配模型，即將機(jī)隊(duì)規(guī)模加入了目標(biāo)函數(shù)中，考慮的重點(diǎn)約束條件包括航班覆蓋、飛機(jī)平衡、飛機(jī)利用率等。Pareto最優(yōu)解是多目標(biāo)優(yōu)化求解的主要方法[13]，很難用傳統(tǒng)方法求解，為此，本文引入了計(jì)算方便、設(shè)計(jì)性強(qiáng)的帶精英策略的快速非支配排序遺傳算法NSGA-II[14-15]。對航空公司而言，通過求解此模型得到的機(jī)型分配方案，對提高各機(jī)型飛機(jī)使用效率、降低經(jīng)營成本、獲得更高的收益有著十分重要的意義。

1 多目標(biāo)航班機(jī)型分配模型

1.1 時(shí)空網(wǎng)絡(luò)法

用數(shù)學(xué)模型表示機(jī)型分配問題的一個(gè)主要難點(diǎn)在于如何跟蹤不同機(jī)場、不同時(shí)間機(jī)隊(duì)的情況，時(shí)空網(wǎng)絡(luò)圖可以很容易解決這個(gè)問題。圖1包含3個(gè)機(jī)場、2種機(jī)型，8個(gè)航班（1~8）、14個(gè)節(jié)點(diǎn)（A~O）時(shí)空網(wǎng)絡(luò)。

在時(shí)空網(wǎng)絡(luò)圖中，縱軸代表時(shí)間，橫軸代表機(jī)場。圖1中，連線（箭頭）表示航班段，節(jié)點(diǎn)表示某個(gè)機(jī)場在一天中某個(gè)特定時(shí)間航班的進(jìn)出港情況；折線（帶箭頭）表示地面連接線，用于將機(jī)場的最后一個(gè)到達(dá)節(jié)點(diǎn)與第一個(gè)始發(fā)節(jié)點(diǎn)連接起來，這種線表示飛機(jī)在該機(jī)場過夜，它將某一天的最后一個(gè)進(jìn)港航班與第二天的出港航班銜接起來。所以，時(shí)空網(wǎng)絡(luò)圖可以很好地解釋機(jī)型分配模型中約束條件飛機(jī)平衡這一概念，即某節(jié)點(diǎn)停在地面上的某個(gè)機(jī)型的飛機(jī)架數(shù)=該節(jié)點(diǎn)之前地面上同機(jī)型飛機(jī)的架數(shù)+到達(dá)該節(jié)點(diǎn)同機(jī)型飛機(jī)的架數(shù)-飛離該節(jié)點(diǎn)同機(jī)型飛機(jī)的架數(shù)。如在機(jī)場1，節(jié)點(diǎn)B處機(jī)型738的飛機(jī)架數(shù)=節(jié)點(diǎn)B處機(jī)型738 的飛機(jī)架數(shù)+1（航班 2）-1（航班 3）。

圖1 時(shí)空網(wǎng)絡(luò)圖Fig.1 Time-space network diagram

1.2 多目標(biāo)機(jī)型分配的數(shù)學(xué)模型

以最大化航空公司利潤和使用最少的飛機(jī)架數(shù)覆蓋全部航班作為目標(biāo)，在已知航班時(shí)刻表（包括航班號、起飛時(shí)間、到達(dá)時(shí)間、始發(fā)機(jī)場、到達(dá)機(jī)場、飛行時(shí)間、航程、平均票價(jià)）、乘客需求、機(jī)隊(duì)結(jié)構(gòu)的基礎(chǔ)上，首先通過時(shí)空網(wǎng)絡(luò)法構(gòu)建航班網(wǎng)絡(luò)，然后在航班網(wǎng)絡(luò)的基礎(chǔ)上建立了同時(shí)優(yōu)化航空公司利潤和覆蓋全部航班飛機(jī)架數(shù)的多目標(biāo)機(jī)型分配模型。

1）集合

模型所包含的集合有：F表示航班集合；H表示經(jīng)停航班集合，H?F；J表示機(jī)型集合；O表示機(jī)場集合；M表示時(shí)空網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合；E表示時(shí)空網(wǎng)絡(luò)中終止節(jié)點(diǎn)集合，E?M。

2）下標(biāo)變量

模型所含的下標(biāo)變量有：i表示航班，i∈F；j表示機(jī)型，j∈J；o表示機(jī)場，o∈O；m表示時(shí)空網(wǎng)絡(luò)中的節(jié)點(diǎn)，m∈M；e表示時(shí)空網(wǎng)絡(luò)中的終止節(jié)點(diǎn)，e∈E；h表示一個(gè)經(jīng)停航班，h∈H，針對實(shí)際情況只考慮一次經(jīng)停，每個(gè)經(jīng)停航班h將整個(gè)航程分成h1和h2兩個(gè)航段。

3）參數(shù)

模型所涉及的參數(shù)有：ti表示航班i的飛行時(shí)間；Lj表示機(jī)型j最大日利用率；spill表示乘客的溢出率；Nj表示機(jī)型j數(shù)量；i.pax表示航班i的乘客需求；Sj表示機(jī)型j的座位數(shù)；Gm，j表示在節(jié)點(diǎn)m處機(jī)型j的架數(shù)。

4）決策變量

模型涉及的決策變量有：am，i=1，表示在節(jié)點(diǎn)m處航班i為進(jìn)港航班；am，i=-1，表示在節(jié)點(diǎn)m處為出港航班；Xi，j表示決策變量，當(dāng)機(jī)型j分配給航班i時(shí)取值1，否則為0。

5）模型

其中：f1為每個(gè)航班分配一種機(jī)型后航空公司總的利潤（取反）；f2為每個(gè)航班分配一種機(jī)型后使用總的飛機(jī)架數(shù)；Pi，j表示機(jī)型 j執(zhí)行航班 i的收益；Ci，j表示機(jī)型j執(zhí)飛航班i時(shí)的總成本；Ge，j表示在時(shí)空網(wǎng)絡(luò)中終止節(jié)點(diǎn)e處機(jī)型j的飛機(jī)架數(shù)。計(jì)算如下

約束條件：式（2）為航班覆蓋，確保每一個(gè)航班分配一種機(jī)型；式（3）~式（4）為飛機(jī)平衡或設(shè)備的連續(xù)性，保證了在需要的地方及需要的時(shí)間里會從正確的機(jī)型中提供1架飛機(jī)；式（5）為飛機(jī)利用率約束；式（6）為飛機(jī)座位數(shù)約束，即如果航班i的乘客量i.pax=100，最大旅客溢出量spill=0.1，則要求分配給航班i的機(jī)型座位數(shù)Sj≥90；式（7）表示經(jīng)停航班約束，即要求一次經(jīng)停航班的兩個(gè)航段分配相同的機(jī)型；式（8）表示Xi，j為 0-1 決策變量。

2 模型求解

2.1 NSGA-II算法基本原理

NSGA-II算法是一種基于進(jìn)化算法（EA）的多目標(biāo)優(yōu)化（MOO）方法之一，由Srinivas和Deb于2000年提出的。在遺傳算法（GA）的基礎(chǔ)上，NSGA-II算法提出了3種關(guān)鍵技術(shù)（快速非支配排序、擁擠度和擁擠度比較與精英策略）：①非支配排序算法保留了最優(yōu)秀的解決方案，其作用是指引搜索向Pareto最優(yōu)解集方向進(jìn)行；②采用擁擠度與擁擠度算子以保持解決方案的多樣性；③精英策略為了保留父代中的優(yōu)良個(gè)體直接進(jìn)入子代，以防止獲得的Pareto最優(yōu)解丟失，個(gè)體的優(yōu)良由目標(biāo)函數(shù)決定。而NSGA-II算法中的選擇、交叉與變異算子和遺傳算法中這3個(gè)算子的原理相同。NSGA-II算法能夠找到使各目標(biāo)函數(shù)能盡量達(dá)到比較大（或比較?。┑腜areto最優(yōu)解集，為各目標(biāo)函數(shù)之間權(quán)衡提供了有效的工具。算法的基本原理如圖2所示。

圖2NSGA-II原理圖Fig.2 Principle of NSGA-II diagram

其中：Pt表示在t代產(chǎn)生的種群，種群大小為N；Qt表示在父代種群Pt上通過遺傳操作產(chǎn)生的子代種群；Rt表示Pt與Qt合并組成的種群，種群大小為2N；Z1，Z2，Z3…表示在種群Rt上通過非支配排序算子產(chǎn)生的非支配集；Rt+1表示在Rt的基礎(chǔ)上，通過上述3種技術(shù)產(chǎn)生的第t+1代種群，種群大小為N，種群Pt的產(chǎn)生過程與此一樣，種群Qt+1的產(chǎn)生過程與Qt一樣。

2.2 模型求解的步驟

本文將NSGA-II算法應(yīng)用于式（1）所示模型求解，具體算法實(shí)現(xiàn)如下：

1）輸入輸出

輸入：機(jī)型集合J，航班集合F；

輸出：最優(yōu)的航班機(jī)型對。

2）程序流程

初始化種群：

For pop：隨機(jī)生成1組染色體

While染色體不滿足約束條件

重新生成；

End while

End for

計(jì)算染色體適應(yīng)度，即目標(biāo)函數(shù)值；

初始化種群排序；

For Gen：

錦標(biāo)賽選擇；

交叉和變異操作：

While染色體不滿足約束條件

重新進(jìn)行交叉或變異操作；

End while

計(jì)算染色體適應(yīng)度，即目標(biāo)函數(shù)值；

非支配排序和擁擠度排序；

替代種群，即生成子代；

End for

3 算例

該算例涉及40個(gè)航班，80個(gè)結(jié)點(diǎn)，19個(gè)機(jī)場，航班時(shí)刻表，如表1所示。其中，各航班段最大旅客溢出量均取0.1，航班段旅客量由歷史數(shù)據(jù)預(yù)估得出，機(jī)票價(jià)格由航線市場年總收入除以實(shí)際運(yùn)輸旅客量，計(jì)算得到平均票價(jià)。

假設(shè)航空公司40個(gè)航班可使用的機(jī)型有737和738兩種，每種機(jī)型的座位數(shù)、日最大利用率、座公里成本費(fèi)用，如表2所示。

表1 航班時(shí)刻表Tab.1 Flight timetable

表2 各機(jī)型數(shù)據(jù)表Tab.2 Data of aircraft type

3.1 模型的求解過程

本文實(shí)驗(yàn)的目的是為該航空公司的40個(gè)航班分配機(jī)型，使得航空公司的40個(gè)航班獲得的總利潤最大和覆蓋這40個(gè)航班所用的飛機(jī)架數(shù)最少，從而驗(yàn)證模型的可行性和有效性。

1）計(jì)算每種機(jī)型下航班的利潤

其中：i.price表示航班i的平均票價(jià)；i.pax≤Sj表示航班i的乘客量小于等于機(jī)型j的座位數(shù)，沒有乘客溢出；i.pax>Sj表示航班i的乘客量大于等于機(jī)型j的座位數(shù)，有乘客溢出。

航班分配成本計(jì)算，包括兩部分：運(yùn)營成本OCi，j和溢出成本 SCi，j，即

其中：CASMj為機(jī)型j的座公里成本[6]；di為航班i的航程；溢出成本 SCi，j可表示為

2）采用NSGA-II算法為航班分配機(jī)型，算法設(shè)計(jì)如2.2節(jié)。其中交叉概率Pc和變異概率Pm根據(jù)生成的隨機(jī)數(shù)取值，若生成的隨機(jī)數(shù)小于0.9，則進(jìn)行交叉操作，否則進(jìn)行變異操作。設(shè)置參數(shù)種群規(guī)模pop及最大進(jìn)化代數(shù)Gen并進(jìn)行實(shí)驗(yàn)。

3.2 實(shí)驗(yàn)結(jié)果及分析

通過以上方法，求得的Pareto最優(yōu)解集，即航班機(jī)型分配方案如表3所示。Pareto前沿，即與表3中方案對應(yīng)的目標(biāo)函數(shù)值如表4所示。

為了驗(yàn)證所提模型的有效性，在同樣的條件下，建立僅以航班總利潤最大為優(yōu)化目標(biāo)，不考慮使用最少的飛機(jī)架數(shù)覆蓋全部航班的單目標(biāo)機(jī)型分配模型，對這40個(gè)航班分配機(jī)型，得到的結(jié)果與方案2相同。對比兩個(gè)方案的目標(biāo)函數(shù)，可知方案1和方案2在兩個(gè)目標(biāo)函數(shù)上具有互不支配的特點(diǎn)，同屬Pareto最優(yōu)解。方案1在使用的飛機(jī)架數(shù)上占優(yōu)，方案2在航班總利潤上占優(yōu)，而方案1的飛機(jī)利用率明顯占優(yōu)。對比單目標(biāo)機(jī)型分配模型，說明了基于NSGA-II算法的多目標(biāo)機(jī)型分配獲得的解集在各目標(biāo)空間上分布更為均勻，更具多樣性，能夠?yàn)楹娇展竞桨鄼C(jī)型分配提供更多選擇空間。

表3 航班機(jī)型分配方案Tab.3 Airline fleet assignment scheme

表4 機(jī)型分配方案Tab.4 Fleet assignment scheme

表5給出了這4個(gè)機(jī)場各機(jī)型需要的過夜飛機(jī)架數(shù)，其余15個(gè)機(jī)場過夜飛機(jī)架數(shù)都為0。

表5 各機(jī)場各機(jī)型飛機(jī)分布Tab.5 Aircraft distribution of airports

通過計(jì)算得出各機(jī)型的日平均利用率如表4所示，而通常情況下737機(jī)型和738機(jī)型的日平均利用率分別約為8.28 h和7.2 h。此時(shí)，航空公司需求的總飛機(jī)數(shù)量為13或14架，為了獲得更好的機(jī)隊(duì)配置組合，可以通過調(diào)整機(jī)隊(duì)的機(jī)型配置獲得總利潤和日利用率較高的配置方案。表6為部分配置方案，從表中可以看出，方案4的總利潤不是最高的，但是737機(jī)型的利用率最高。此外，該表可以為航空公司的機(jī)隊(duì)管理提供決策支持，各方案的航班機(jī)型配置表不再一一列出。

表6 機(jī)隊(duì)配置方案的利潤和日利用率Tab.6 Profit and daily utilization rate of fleet assignment scheme

4 結(jié)語

為了增強(qiáng)航空公司在市場中的競爭力，本文通過優(yōu)化機(jī)型分配的方式來提高航空公司的管理水平，建立了多目標(biāo)航班機(jī)型分配模型，構(gòu)建了基于精英策略快速非支配排序遺傳算法（NSGA-II）的多目標(biāo)機(jī)型分配優(yōu)化算法。通過將模型應(yīng)用于國內(nèi)某航空公司航線網(wǎng)絡(luò)中，為周期為日的定期航班分配機(jī)型，對比單目標(biāo)機(jī)型分配模型的機(jī)型分配方案，結(jié)果表明該算法在目標(biāo)空間上分布更均勻，驗(yàn)證了模型的有效性。NSGA-II算法能為航班機(jī)型分配提供更多選擇空間，為多目標(biāo)航班機(jī)型分配的全局優(yōu)化提供了一種新的思路和手段。

[1] ABARA J.Applying integer linear programming to the fleet assignment problem[J].INTERFACES,1989,19(4)：20-28.

[2] BROWN J.Airline fleet composition and deregulation[J].Review of Industrial Organization,1992,8(4)：435-449.

[3]HANE C A,BARNHART C,JOHNOSON E L,et al.The fleet assignment problem：Solving a large-scale integerprogram[J].Mathematical Programming,1995,70(2)：211-232.

[4] LISTES O,DEKKERR.A scenario aggregation-based approach for determining a robust airline fleet composition for dynamic capacityallocation[J].Transportation Science,2005,39(3)：367-382.

[5]BARNHART C,FARAHAT A,LOHATEPANONT M.Airline fleet assignment with enhanced revenue modeling[J].Operations Research,2009,57(1)：231-244.

[6] SHAO Shengzhi,HANIF D,SHERALI.A novel model and decomposition approach for the integrated airline fleet assignment，aircraft routing,and crew pairing probiem[J].Transportation Science,2015,51(1)：1-17.

[7] 徐 進(jìn).航空公司航班計(jì)劃的優(yōu)化方法研究[D].南京：南京航空航空大學(xué),2007.

[8] 樂美龍,黃文秀.基于時(shí)空網(wǎng)絡(luò)的航班機(jī)型分配問題研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2014,14(1)：81-87.

[9] LIU Wanming,ZHU Xinghui,QI Yanlong.Integrated fleet assignment and aircraft routing based on delay propagation[J].Indian Academy of Sciences,2016,41(7)：713-719.

[10]朱金福.航空運(yùn)輸規(guī)劃[M].西安：西北工業(yè)大學(xué)出版社,2008.

[11]馬蘇德·巴扎爾干,邵 龍.航空公司運(yùn)營與規(guī)劃管理[M].北京：中國民航出版社,2006.

[12]JOHN H MOTT,DANIEL HENAO,MITCHELL S HODGEN,et al.Increasing collegiate flight training fleet utilization through the use of an aircraft assignment algorithm[J].International Journal of Aviation,Aeronautics,and Aerospace,2016,3(3)：1-19.

[13]王洪濤,劉玉田.基于NSGA-II的多目標(biāo)輸電網(wǎng)架最優(yōu)重構(gòu)[J].電力系統(tǒng)自動化,2009,33(23)：14-17.

[14]JINBA T,HARADA T,SATO H,et al.Multi Objective Optimization for Route Planning and Fleet Assignment in Regular and Non-Regular Flights[C]//Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems,Springer International Publishing,2015：561-575.

[15]KALYANMOY DEB,AMRIT PRATAP,SAMEER AGARWAL,et al.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactiond on Evolutionary Computation,2002,6(2)：182-197.

（責(zé)任編輯：孟 欣）

Multi-objective for airline fleet assignment model based on NSGA-II computer engineering and applications

FAN Wei,BIE Haojie
（College of Computer Science and Technology,CAUC,Tianjin 300300,China）

Fleet assignment is one of the most important problems in airline resource optimization and management,which affects the profitability and competitiveness greatly.In order to solve the singularity of existing fleet assignment methods,a multi-objective fleet assignment model is proposed based on traditional fleet assignment models,which means that taking profit maximization and least number of aircraft as optimizational targets.However,complicated multi-objective solving model can bring bias target solving.NSGA-II algorithm is used to solve the multiobjective problem.The instance verifies the effectiveness of this method.Compared with single-objective optimization for fleet assignment model,experiment shows that the result solved by the proposed model can reach more even distribution and provide reference for decision making of airline fleet assignment.

air transportation;fleet assignment;NSGA-II algorithm;multi-objective optimization;flights

V355；TP3

A

1674－5590（2017）03－0043－06

2016-12-06；

2017-01-09 基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目（U1333109）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)（3122016B006）

樊瑋（1968—），男，陜西乾縣人，教授，博士，研究方向?yàn)閿?shù)據(jù)挖掘、計(jì)算機(jī)軟件理論與應(yīng)用、智能信息處理.