遺傳算法在機(jī)型配置中的應(yīng)用

陳蓉

摘 ?要：航班機(jī)型配置關(guān)系到航空公司的行業(yè)競爭力，是航空公司長期關(guān)注的問題。針對航空運(yùn)力過剩及機(jī)型比例失調(diào)等問題，考慮航班規(guī)模增加及機(jī)型配置需求增多對航空公司的影響，引入多重約束，建立基于航空收益最大化的航班機(jī)型配置優(yōu)化模型。采用遺傳算法求解該模型，并設(shè)置算法中的選擇、交叉、變異等算子，獲得一段時(shí)間內(nèi)機(jī)型配置連線最優(yōu)方案。研究表明，提出的多重約束優(yōu)化模型和遺傳算法，能夠提高航空公司機(jī)型配置時(shí)效性與科學(xué)性。

關(guān)鍵詞：機(jī)型配置;多重約束;航空收益;遺傳算法

中圖分類號(hào)：TP399 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： Fleet assignment， a long-term concern of airlines， has much to do with the competitiveness of airlines. Considering the impact of increased flight scale and increased fleet assignment demand on airlines， this paper introduces multiple constraints and establishes a fleet assignment optimization model based on maximizing aviation revenue， aiming at the problems of overcapacity and imbalance of aircraft types. The genetic algorithm is used to solve the model， and the selection， crossover， mutation and other operators in the algorithm are set to obtain the optimal solution for fleet assignment connection scheme within a period of time. Research shows that the proposed multi-constraint optimization model and genetic algorithm timely and scientifically improve fleet assignment model.

Keywords： fleet assignment; multiple constraints; aviation revenue; genetic algorithm

1 ? 引言（Introduction）

國內(nèi)外航空市場競爭日益激烈，各航空公司為了提升競爭力，對增加航班規(guī)模、優(yōu)化航班資源配置、精細(xì)化管理提出越來越多的要求。其中，機(jī)型配置是航空運(yùn)輸中不可缺少的一部分，也是提升航空市場競爭力的一個(gè)有效方法。機(jī)型配置是航空公司在航班時(shí)刻表的基礎(chǔ)上進(jìn)行現(xiàn)有機(jī)型的分配，它根據(jù)不同的機(jī)型具有的不同座位數(shù)、客運(yùn)需求、最大空缺率、運(yùn)行成本、最大耗油量等，配置不同的機(jī)型給設(shè)定好的航班，從而使航空公司獲得最大收益。此外，飛機(jī)座位是“易腐的”，在航班離港前沒有出售就會(huì)造成浪費(fèi)，因此最理想的決策就是將“合適的座位數(shù)”以“合適的價(jià)格”提供給“合適的乘客”。本文主要從“合適的座位數(shù)”出發(fā)，優(yōu)化航班的機(jī)型配置。

機(jī)型配置是一項(xiàng)長期研究的問題，過去的研究大多集中于機(jī)組任務(wù)問題上，定義一個(gè)便利且高效的目標(biāo)函數(shù)[1]，開發(fā)高效算法來解決復(fù)雜的資源配置問題[2]，或者研究問題的動(dòng)態(tài)性質(zhì)[3]，也有研究問題的隨機(jī)性[4]、魯棒性[5]的。常見的機(jī)型配置問題可通過整數(shù)規(guī)劃建立數(shù)學(xué)模型或建立時(shí)空網(wǎng)絡(luò)圖[6]來解決，包括引入乘客需求、運(yùn)營成本、票價(jià)、時(shí)間窗、航班頻率等因素[7-9]。

機(jī)型配置規(guī)劃中不同的機(jī)型及限制條件不同，模型算法有所不同。胡明華等提出改進(jìn)的啟發(fā)式算法用于解決多元受限航班優(yōu)化模型[10];李福娟等采用緊急搜索法對航空公司航線計(jì)劃優(yōu)化模型進(jìn)行求解，使利潤達(dá)到最大[11];WEI等采用一種原始的集成優(yōu)化方法對機(jī)隊(duì)分配進(jìn)行求解[8]。但當(dāng)問題規(guī)模較大時(shí)，上述模型求解比較困難，因此，遺傳算法等智能搜索算法也被用于問題求解。

研究表明，機(jī)型配置規(guī)劃對航空運(yùn)輸具有非常重要的意義，目前研究大多集中于某個(gè)因素或多個(gè)因素約束構(gòu)成的綜合模型，或者對重大規(guī)?，F(xiàn)有模型進(jìn)行算法優(yōu)化。本文在已有的理論上進(jìn)行深入探究和發(fā)展，首先基于飛機(jī)座位數(shù)、尺寸、效率、成本、耗油量等因素建立以收益最大化為目標(biāo)的多重約束機(jī)型配置模型;然后采用遺傳算法對其進(jìn)行優(yōu)化求解，使機(jī)型配置模型求得適應(yīng)度最優(yōu)的解;最后結(jié)合具體情況，驗(yàn)證機(jī)型配置模型的可行性和有效性，以及遺傳算法用于解決機(jī)型資源配置的高效性。

2 ? 機(jī)型配置模型（Fleet assignment model）

2.1 ? 問題描述

機(jī)型配置是航班計(jì)劃的重要研究內(nèi)容。我國現(xiàn)有航空公司中，每個(gè)航空公司不止一種機(jī)型，每種機(jī)型的飛機(jī)架數(shù)、座位容量、油耗、成本（維修成本及乘客溢出成本）等都是不同的，且在不同的航線上，不同的機(jī)型產(chǎn)生的運(yùn)營成本也是不同的，故機(jī)型配置是為了確定每一條航線上使用的機(jī)型，并使得整體利益最大化。

要解決的問題及基本假設(shè)：

（1）機(jī)型配置要確定每一條航線應(yīng)該使用哪一種飛機(jī)或機(jī)隊(duì)，使收入減運(yùn)營成本最大化。

（2）航班時(shí)刻表是已知的，是一組具有指定起飛和到達(dá)時(shí)間的航班段。

（3）收入是細(xì)分市場需求，運(yùn)營成本取決于飛機(jī)的尺寸和效率，以及航段的距離。

（4）機(jī)場必須有飛機(jī)可以飛行，且每個(gè)機(jī)場必須在一周開始和結(jié)束時(shí)分配相同的飛機(jī)。

（5）滿足覆蓋約束：確保每個(gè)單航程只分配一種機(jī)型;滿足計(jì)數(shù)約束：每個(gè)機(jī)型指定的飛機(jī)架數(shù)必須等于該機(jī)型在所有時(shí)間內(nèi)可用的飛機(jī)總數(shù);容量限制約束：分配到單一航程的所有乘客數(shù)量不能超過分配到該航程機(jī)型的容量;平衡約束：中轉(zhuǎn)服務(wù)飛行必須將兩個(gè)航段分配給相同的飛機(jī);行程約束：機(jī)型分配航程時(shí)要注意機(jī)型路程類型，短途機(jī)不能分配給中長航段，中途機(jī)不可以分配給長航段。

2.2 ? 模型構(gòu)建

2.2.1 ? 模型參數(shù)

機(jī)型配置模型所需參數(shù)及變量定義如表1所示。

其中，目標(biāo)函數(shù)（5）是機(jī)型配置下運(yùn)輸成本與收入的絕對值最大化，即使得收益達(dá)到最大。約束條件（6）確保每一次“真正”的飛行都有一架指定的飛機(jī)，即每一個(gè)航段都有一個(gè)機(jī)型來覆蓋。約束條件（7）確保每個(gè)機(jī)型的每架飛機(jī)只能從偽出發(fā)航班集及偽到達(dá)航班集起飛一次。約束條件（8）確保飛機(jī)必須在同一個(gè)地方開始和結(jié)束。約束條件（9）確保滿足最大座位空缺率，如果MS=0.1，航班的需求為100，則可溢出的乘客最多不超過10人，即必須使用座位容量大于90的機(jī)型。約束條件（10）強(qiáng)制在中轉(zhuǎn)飛行中，航段要使用相同的設(shè)備機(jī)型。約束條件（11）和（12）確保飛機(jī)必須在機(jī)場才能被分配給航段且機(jī)型相同，其中，對于將要

從某機(jī)場出發(fā)的航班，是在該機(jī)場航班可以銜接的到達(dá)航班集合，且滿足航班銜接的時(shí)間要求;，即在航班

前從該機(jī)場出發(fā)的航班集合。約束條件（13）和（14）確保機(jī)型與航班之間類型的兼容性，其中，即長途機(jī)型可以進(jìn)行長、中、短途飛行;，即中途機(jī)型可以進(jìn)行中、短途飛行，短途機(jī)型只能飛短途。

3 遺傳算法的應(yīng)用（Application of genetic algorithm）

由于航空運(yùn)輸規(guī)模的擴(kuò)大，且機(jī)型配置模型是大規(guī)模數(shù)學(xué)組合模型，為了在短時(shí)間內(nèi)得到最優(yōu)解，本文采用遺傳算法對機(jī)組配置模型求解，采用適合的編碼方式及約束條件的處理方式，選取適應(yīng)度函數(shù)和選擇、交叉以及變異方法，最后以某航空公司的數(shù)據(jù)為例，代入機(jī)組配置模型進(jìn)行研究，計(jì)算使得機(jī)組航班資源最優(yōu)的配置方案。

3.1 ? 編碼

采用遺傳算法對機(jī)組配置問題進(jìn)行求解，需要編碼確定研究問題所表達(dá)的含義。本文采用直接編碼法對其進(jìn)行編碼，其中機(jī)型編號(hào)為1—，航段為染色體上的基因位數(shù)，即為染色體長度。假設(shè)機(jī)型有3種，航段數(shù)為6，在進(jìn)行編碼時(shí)3種機(jī)型的編號(hào)為1、2和3，規(guī)劃方式為36種選擇，假設(shè)一條染色體上基因的排列為（1，3，2，3，1，1），則解為：

3.2 ? 初始化數(shù)據(jù)

求解模型中所需的數(shù)據(jù)格式，確定交叉概率和變異概率，選擇一個(gè)機(jī)型配置結(jié)果作為初始群體，即為模型求解結(jié)果的假設(shè)集合，模型的最優(yōu)解將通過這些初始解進(jìn)化而求出。選擇初始解，可以采用隨機(jī)選取或優(yōu)化算法選取，本文采用的是隨機(jī)選取。

選取初始群體后確定每個(gè)個(gè)體的適應(yīng)度，適應(yīng)度函數(shù)是根據(jù)目標(biāo)函數(shù)來區(qū)分的。對每個(gè)航班所選擇的機(jī)型的編碼串進(jìn)行解碼處理后得到個(gè)體的表現(xiàn)型，通過個(gè)體表現(xiàn)型可計(jì)算機(jī)出對應(yīng)個(gè)體的目標(biāo)函數(shù)值，根據(jù)機(jī)型配置模型的目標(biāo)函數(shù)轉(zhuǎn)換出個(gè)體的適應(yīng)度。

3.3 ? 選擇、交叉與變異

遺傳算法是一個(gè)優(yōu)勝劣汰的尋優(yōu)算法，選擇操作的目的是為了將不夠優(yōu)的個(gè)體從群體中挑出，也就是在將機(jī)型分配給航段的個(gè)體中選擇適應(yīng)度較高的個(gè)體進(jìn)行演化。本文采用最佳保留選擇算法，按輪盤賭選擇方法執(zhí)行遺傳算法的選擇操作，然后將當(dāng)前群體中適應(yīng)度最高的個(gè)體結(jié)構(gòu)完整地復(fù)制到下一代群體中。

對于選中的用于演化的個(gè)體，隨機(jī)選擇兩個(gè)個(gè)體相同的位置進(jìn)行交叉操作得到新的個(gè)體，然后根據(jù)變異算子的概率對某些個(gè)體的某些位置執(zhí)行變異操作，增加全局優(yōu)化特性，確保得到全局最優(yōu)解。

4 ? 算列分析（Example analysis）

每條飛機(jī)連線上的航班視為一個(gè)航班塊，每一個(gè)航班塊包括序號(hào)、出發(fā)地和出發(fā)時(shí)間、目的地和到達(dá)時(shí)間、乘客需求及票價(jià)。決策變量為0—1的整數(shù)，即每一個(gè)決策變量只能取0或1。以表2和表3數(shù)據(jù)為例，涉及230個(gè)航班的3個(gè)機(jī)型，其中表2為航班塊集合（由于篇幅限制，僅展示部分信息），表3為機(jī)組信息集合。

根據(jù)表4、表5可以得出：（1）引進(jìn)遺傳算法得到的最優(yōu)解成本劣于混合整數(shù)線性規(guī)劃得到的最優(yōu)解成本，但是隨著迭代次數(shù)的增大，GB也隨著減小，這證明了遺傳算法引入的有效性，且所提出的算法不受問題空間的限制，因此遺傳算法能在可接受時(shí)間內(nèi)產(chǎn)生較優(yōu)航空資源配置。（2）遺傳算法的引進(jìn)增加了算法運(yùn)行時(shí)間，但這個(gè)運(yùn)行時(shí)間在成本取得較優(yōu)的情況下可以忽略不考慮，且時(shí)間的增加在可接受范圍內(nèi)。

5 ? 結(jié)論（Conclusion）

考慮到航空公司規(guī)模的不斷擴(kuò)大，機(jī)型配置問題也愈發(fā)復(fù)雜，遺傳算法的引進(jìn)解決了航班資源配置問題。首先，考慮乘客需求、運(yùn)行成本、飛行距離、票價(jià)、耗油量等因素的影響，根據(jù)航班集合信息及機(jī)隊(duì)信息，建立收益最大化的機(jī)組配置優(yōu)化模型;其次，考慮大規(guī)模問題，引進(jìn)自適應(yīng)遺傳算法，為調(diào)度、機(jī)組分配問題創(chuàng)建可行的初始解，設(shè)計(jì)制定遺傳算子，改進(jìn)初始解，得到全局較優(yōu)解;最后，以航空公司數(shù)據(jù)為例，將采用遺傳算法后的資源配置結(jié)果和最初的資源配置結(jié)果進(jìn)行對比。結(jié)果表明，引進(jìn)遺傳算法的優(yōu)化模型可以得到全局最優(yōu)解，實(shí)現(xiàn)了飛機(jī)停機(jī)調(diào)度約束的統(tǒng)一，通過對不同個(gè)體的適應(yīng)度分析，得到全局效益最優(yōu)解，且該優(yōu)化模型靈活可變，方便后續(xù)相關(guān)約束的加入，能夠通過建立線性約束條件，較為方便地加入、修改、取消相關(guān)約束，進(jìn)而實(shí)現(xiàn)約束的動(dòng)態(tài)優(yōu)化。

參考文獻(xiàn)（References）

[1] DUMAS J， AITHNARD F， SOUMIS F. Improving the objective function of the fleet assignment problem[J]. Transportation Research Part B： Methodological， 2009， 43（04）：466-475.

[2] YAN S Y， TANG C H， FU T C. An airline scheduling model and solution algorithms under stochastic demands[J]. European Journal of Operational Research， 2007， 190（01）：22-39.

[3] JIANG H， BARNHART C. Dynamic airline scheduling[J]. Transportation Science， 2009， 43（03）：336-354.

[4] CADARSO L， CELIS R D. Integrated airline planning： Robust update of scheduling and fleet balancing under demand uncertainty[J]. Transportation Research Part C： Emerging Technologies， 2017， 81（02）：227-245.

[5] JIANG H， BARNHART C. Robust airline schedule design in a dynamic scheduling environment[J]. Computers & Operations Research， 2013， 40（03）：831-840.

[6] HANE C A， BARNHART C， JOHNSON E L， et al. The fleet assignment problem： Solving a large-scale integer program[J]. Mathematical Programming， 1995， 70（02）：? ? ? 211-232.

[7] YAN S， TSENG C H. A passenger demand model for airline flight scheduling and fleet routing[J]. Computers and Operations Research， 2002， 29（11）：1559-1581.

[8] WEI K J， VAZE V， JACQUILLAT A. Airline timetable development and fleet assignment incorporating passenger choice[J]. Transportation Science， 2020， 54（01）：139-163.

[9] SERRANO-HERNANDEZ A， CADARSO L， FAULIN J.?? ? A strategic multistage tactical two-stage stochastic optimization model for the airline fleet management problem[J]. Transportation Research Procedia， 2020， 47（04）：473-480.

[10] 胡明華，朱晶波，田勇.多元受限的航班時(shí)刻優(yōu)化模型與方法研究[J].南京航空航天大學(xué)學(xué)報(bào)，2003，35（03）：326-332.

[11] 李福娟，王魯平，劉仲英.航班計(jì)劃優(yōu)化模型及其應(yīng)用研究[J].計(jì)算機(jī)工程，2007，33（11）：279-281.

作者簡介：

陳 ? 蓉（1970-），女，碩士，經(jīng)濟(jì)師.研究領(lǐng)域：航空公司數(shù)字化轉(zhuǎn)型及智能系統(tǒng)建設(shè).