賈寶惠，杜建勛，李耀華

（中國民航大學(xué)航空工程學(xué)院，天津 300300）

基于遺傳算法的航班串優(yōu)化方法研究

賈寶惠，杜建勛，李耀華

（中國民航大學(xué)航空工程學(xué)院，天津 300300）

分析研究了航班串編制問題，考慮了飛機載客量與航班平均客流量的關(guān)系，構(gòu)造了航班旅客溢出成本指數(shù)因子，建立了改進后的基于最小成本的航班串優(yōu)化模型，并構(gòu)造了遺傳算法求解模型。利用Matlab遺傳算法工具箱進行仿真研究。應(yīng)用航空公司實際航班數(shù)據(jù)對上述模型和算法進行驗證，所得優(yōu)化結(jié)果良好，證明該航班串優(yōu)化模型及方法切實可行。

遺傳算法；航班串；生產(chǎn)計劃

隨著中國民航業(yè)的飛速發(fā)展，航空公司的航班量快速增長，傳統(tǒng)的人工或半人工排班方式由于其排班效率低下已難以滿足航空公司日常的飛機排班要求。而智能高效的航班串求解和優(yōu)化方法，不僅有助于航班的安全、正點運行，更將直接提高機隊的利用率，進而加大航空公司的經(jīng)濟收益，對航空公司提高自身競爭力具有重要意義[1]。

近年來，國內(nèi)外學(xué)者將具有更高效率的智能化啟發(fā)式算法引入飛機排班的求解和優(yōu)化中，并取得了良好效果。Tung-Kuan等[2]針對航班延誤及恢復(fù)問題，提出了一種新的多目標(biāo)優(yōu)化方法，即評價取向遺傳算法（EPGA），在面對航班調(diào)度突發(fā)狀況時能迅速得到高品質(zhì)解決方案。Torsten等[3]將貪婪啟發(fā)式算法進行改進，創(chuàng)建了RSFFB算法，并將其用于對ARP模型的求解優(yōu)化，獲得了較好效果。詹志輝等[4]針對飛機抵達機場排序和調(diào)度問題，提出了一種帶有滾動時域控制的蟻群算法，即RHC-ACS-ASS算法，該算法具有很強的全局搜索能力，對飛機排班調(diào)度問題具有高效率和較好的魯棒性。Burke[5]針對航班調(diào)度問題，提出了一種改進的文化基因算法（multi-meme memetic algorithm），該算法通過同步飛行時間和飛行路徑得到目標(biāo)的改善，形成一個更具可靠性和靈活性的航班指派計劃。

盡管國內(nèi)外已取得了較多成果，但仍存在一定的不足之處。本文從大型航空公司的飛機排班角度出發(fā)，考慮了機型載客量與航班平均客流量的關(guān)系，構(gòu)造了航班旅客溢出成本指數(shù)因子，建立了改進后的基于最小成本的航班串優(yōu)化模型，最后通過Matlab遺傳算法工具箱對初始航班串進行了優(yōu)化。

1 研究與方法

1.1 問題描述

航班串的編制是指將航空公司一天、一周或一個季度的航班信息通過合理的方法編制為若干個航班串，即將一個到港航班和一個離港航班在符合各方面約束的情況下生成可以由一架飛機去執(zhí)行的航班連接，且其起點和終點都應(yīng)在基地機場。航班串的生成算法包括航班連接網(wǎng)絡(luò)的構(gòu)造算法和航班任務(wù)串搜索算法。通常在航班數(shù)量較少的情況下，通過手工編制航班串即可達到良好的效果。近年來隨著中國航空公司的規(guī)模日益增大，手工編制航班串已難以達到要求，而借助計算機高性能的搜索算法和優(yōu)化算法完成編制航班串的工作已逐漸趨于主流。

對于初始航班串的優(yōu)化工作，需要先建立具有優(yōu)化目標(biāo)的數(shù)學(xué)模型，當(dāng)前已被提出的各種數(shù)學(xué)模型的優(yōu)化目標(biāo)主要包括：以機組規(guī)模最小為目標(biāo)，以執(zhí)勤時間最短為目標(biāo)，以飛行時間均衡為目標(biāo)，以機組利用率最大為目標(biāo)等。本文通過建立以成本最小為目標(biāo)的數(shù)學(xué)模型，并基于遺傳算法工具箱對航班串進行優(yōu)化。

航班串生成所要考慮的準則主要包括：

1）初始航班的出發(fā)時間需由航空公司確定；

2）相銜接的兩個航班在間隔時間、機型、載客量、飛行區(qū)域上都需要嚴格遵守相關(guān)規(guī)定；

3）基地機場需具有一定的維修能力。

1.2 建立模型

關(guān)于最小成本為目標(biāo)的航班串模型，國內(nèi)外學(xué)者已研究出多種優(yōu)化方案[6-7]，分別從不同角度對問題進行了描述，所涉及的約束包括航班銜接約束、航班串成本約束、飛機過站約束等。本文建立了如下以客流量差異值最小為目標(biāo)函數(shù)的航班串編制模型

其中：n為待做計劃的總航班數(shù)，i，j∈n；m為總航班串?dāng)?shù)，k為第k個航班串，k∈m；nk為第k個航班串內(nèi)包含的航班數(shù)；ck為第k個航班串的總溢出成本；為第 k個航班串內(nèi)第 i個航班的旅客溢出成本（passenger overflow cost）；Li為第i個航班到達機場代碼；Dj為第j個航班出發(fā)機場代碼；B為具有一定維修能力的機場，b∈B；xijk，xk為0-1決策變量

式（1）要求優(yōu)化后航班串成本最小；式（2）要求航班串?dāng)?shù)最少；式（3）保證第k個航班串的總溢出成本由相連航班的溢出成本組成；式（4）保證每個航班只能且必須存在在一個航班串內(nèi)；式（5）保證航班銜接要求；式（6）保證航班串k的首個航班出發(fā)機場與最后一個航班到達機場必須一致且是具有一定維修能力的機場。旅客溢出成本指數(shù)經(jīng)過大量數(shù)據(jù)仿真研究，取值如表1所示（其中T為相鄰航班機上座位差異數(shù)量）。

表1 旅客溢出成本指數(shù)表Tab.1 Travellers overflow cost index

1.3 算法設(shè)計

1.3.1 算法原理

遺傳算法（GA）是由美國密歇根大學(xué)的JH Holland教授于1975年創(chuàng)立的，該算法是通過模仿自然界生物進化機制發(fā)展起來的一種高效、全局、并行的優(yōu)化方法[8]。近年來國內(nèi)外學(xué)者通過對遺傳算法的編碼方式、控制參數(shù)的確定、遺傳算子的設(shè)計等方面的改善，對遺傳算法在航班串優(yōu)化問題的應(yīng)用進行了大量的研究工作，提出了各種改進后的遺傳算法[9-10]。

采用基于Matlab的遺傳算法工具箱GUI對航班串進行優(yōu)化，染色體基因型數(shù)據(jù)結(jié)構(gòu)如式（7）所示，整個種群存儲在的矩陣中，行代表個體，列代表個體上的基因。

依照此原理，對航班串初始群體用線性規(guī)劃方法進行優(yōu)化。如式（8）和式（9）所示，根據(jù)航班信息形成矩陣Am×n，其中縱坐標(biāo)j代表航班串，橫坐標(biāo)i代表航班，即Am×n表示m個航班，n個航班串。通過Am×n·X= B求出1組X=（x1，x2，…，xn）使其覆蓋Am×n。

1.3.2 操作方法的改進

選擇、交叉、變異是遺傳算法的核心內(nèi)容，如何針對具體問題改進3種操作方式將對優(yōu)化結(jié)果產(chǎn)生重要影響。下面具體介紹文中遺傳算法3種重要操作的改進方法。

選擇操作的主要目的是防止種群遺傳基因的丟失，算子選擇不當(dāng)會造成種群進化停滯不前或過早收斂，直接關(guān)系到遺傳算法的計算效率和計算結(jié)果。本文所選取的選擇方式為無放回余數(shù)隨機選擇，這種選擇方式可保證適應(yīng)度大于平均適應(yīng)度的優(yōu)秀個體能夠被遺傳到下一代，選擇誤差較小。

遺傳算法的收斂性主要取決于交叉算子，合理的交叉算子在種群進化中能夠增加群體分布的多樣性。文中所選取的交叉算子為算術(shù)交叉，算術(shù)交叉是指父代個體經(jīng)過線性組合產(chǎn)生2個子代個體。假設(shè)對2個父代個體進行算術(shù)交叉，則交叉后所產(chǎn)生的新個體為

其中，參數(shù)α需根據(jù)問題或進化代數(shù)決定。

變異操作是產(chǎn)生種群新個體的一種有效方法，它和交叉算子相互配合可對搜索空間進行有效的全局搜索和局部搜索。從而使遺傳算法能夠以良好的搜索性能完成對問題的優(yōu)化。文中選用高斯變異的變異操作方法。高斯變異是指進行變異操作時用符合均值為P、方差為P2的正態(tài)分布的一個隨機數(shù)來替換原有的基因值。由搜索方式可見，高斯變異與均勻變異較為相似。算法過程如下所示：

1）首先根據(jù)航班串優(yōu)化模型中的目標(biāo)函數(shù)編寫M文件；

2）根據(jù)具體數(shù)據(jù)編制Aeq、Beq矩陣；

3）在GUI界面中初始化算法參數(shù)：確定種群類型和大小，適應(yīng)度函數(shù)，變量個數(shù)，Aeq、Beq矩陣，算法終止準則，選擇算子概率，交叉算子概率，變異算子概率，適應(yīng)度排序方式，繪圖函數(shù)等；

4）通過設(shè)定的遺傳算法參數(shù)進行種群優(yōu)化，根據(jù)終止準則判斷所得當(dāng)前最優(yōu)解是否滿足條件，如不滿足返回3），繼續(xù)進行優(yōu)化，如滿足繼續(xù)5）；

5）輸出算法最優(yōu)解作為航班串優(yōu)化問題的最優(yōu)解。

2 結(jié)果與分析

本文仿真數(shù)據(jù)選取某航空公司某一天的部分航班派遣計劃數(shù)據(jù)，如表2所示。

表2 航班信息Tab.2 Flight information

計劃共20個航班，維修基地機場為天津機場，機型為B737、B757和A330，其座位數(shù)分別為150座、200座和250座。首先采用深度優(yōu)先搜索算法生成初始可行航班串?dāng)?shù)據(jù)，如表3所示。

對初始航班串進行優(yōu)化，工具箱GUI界面中定義參數(shù)為：精英選擇，精英數(shù)量為2，選擇操作為余數(shù)選擇，交叉算子為算術(shù)交叉，變異為高斯變異，終止準則為進化到70代終止，繪圖選擇最佳個體和最佳適應(yīng)度。調(diào)用目標(biāo)函數(shù)M文件進行運算，得出結(jié)果如圖1所示。

圖1顯示了種群每代所對應(yīng)的適應(yīng)度值，當(dāng)種群迭代到70代左右時適應(yīng)度值較為優(yōu)異，且已穩(wěn)定在6.097 4。圖2顯示了適應(yīng)度值達到最優(yōu)時所對應(yīng)的最優(yōu)變量值所在的位置，圖中的當(dāng)前代最佳個體表示優(yōu)化后的航班串序號，即{J2，J5，J7，J8，J9，J11，J14}，對應(yīng)的航班序號為{F1-F2-F19-F20，F(xiàn)3-F4-F17-F18，F(xiàn)5-F6，F(xiàn)7-F8，F(xiàn)9-F10，F(xiàn)11-F12-F15-F16，F(xiàn)13-F14}，對應(yīng)的航線為：津—穗—津—昆—津，津—滬—津—亞—津，津—蓉—津，津—香—津，津—深—津，津—寧—津—松—津，津—廈—津。優(yōu)化后的航班串最小成本指數(shù)為7.424 7，CPU運行時間約為3.22 s，航班串近優(yōu)解相對穩(wěn)定，計算效率較高，結(jié)果滿足航班覆蓋要求。

表3 初始航班串Tab.3 Initial flight strings

圖1 適應(yīng)度值的變化Fig.1 Changes of fitness value

圖2 當(dāng)前代最佳個體Fig.2 Best individual of current generation

目前航空公司的生產(chǎn)計劃部門對航班串的編制過程多為人工編制，上述航班串計劃需要用數(shù)小時完成一個可行計劃，而本文采用的模型和算法只需不到1 min即可對所有航班進行有效編制。相比人工手動編制，不僅求解結(jié)果精確有效，且求解效率大幅提高，有效節(jié)省了人力資源。

3 結(jié)語

通過對遺傳算法數(shù)據(jù)原理進行分析，建立了基于最小成本的航班串優(yōu)化模型，能夠滿足航班運行需要。并通過Matlab遺傳算法工具箱對模型進行求解。通過實際航班信息對上述模型算法進行驗證，所得遺傳算法優(yōu)化結(jié)果較好，能夠滿足航空公司日常需要，并有效降低運營成本。

[1]楊卉竹.基于多Agent的飛機排班系統(tǒng)設(shè)計與實現(xiàn)[D].南京：南京航空航天大學(xué)，2011.

[2]LIU TUNG KUAN，LIU YU TING，CHEN CHIU HUNG，et al.Multiobjective Optimization on Robust Airline Schedule Recover Problem by Using Evolutionary Computation[C]//IEEE，Montreal，October 7-10，2007：2396-2401.

[3]TORSTEN R，JULIAP，MAROSZEK，et al.IntegratedAircraft Scheduling Problem：An Auto-Adapting Algorithm to Find Robust Aircraft Assignments for Large Flight Plans[C]//2012 45thHawaii International Conference on System Sciences，Maui Jannary 4-7，2012：1267-1276.

[4]ZHAN ZHIHUI，ZHANG JUN，LIU OU，et al.An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J].IEEE Transactions on Intelligent Transportation Systems，2010，11（2）：399-412.

[5]BURKE，EDMUND K，DE CAUSMAECKER，et al.A multi-objective approach for robust airline scheduling[J].Computers and Operations Research，2010，37（5）：822-832.

[6]HAOUARI M，AISSAOUI N，MANSOUR F Z.Network flow based approaches for integrated aircraft fleeting and routing[J].European Journal of Operational Research，2009，193（2）：591-599.

[7]BARD J，YU G，ARGüELLO M.Optimizing aircraft routings in responsetogroundingsanddelays[J].HETransactions，2001（33）：931-947.

[8]HOLLAND J H.Adaptation in Nature and Artificial Systems[M].Michigan：The University of Michigan Press，1975.

[10]曹 嵩，孫富春，胡來紅，等.基于分布估計算法的離港航班排序優(yōu)化[J].清華大學(xué)學(xué)報，2012，52（1）：66-71.

（責(zé)任編輯：黨亞茹）

Research on optimization method of flight string based on genetic algorithm

JIA Bao-hui，DU Jian-xun，LI Yao-hua
（College of Aeronautical Engineering，CAUC，Tianjin 300300，China）

Flight string problem is analyzed，and the connection between flights'average traffic volume and aircraft passenger capacity is considered.The factor of airline passenger overflow cost index is structured，and the optimized model of flight string based on minimum cost is proposed.At last GA based on Matlab is used to study the model. The simulation result with flight data shows that the model and algorithm are practical and effective.The optimization of flight string is meaningful to the airlines.

genetic algorithm；flight string；production planning

V271

：A

：1674-5590（2014）05-0045-04

2013-09-03；

：2013-10-13

：國家自然科學(xué)基金項目（U1233107）

賈寶惠（1971—），女，山西運城人，教授，碩士，研究方向為復(fù)雜工業(yè)過程建模、智能求解算法.