基于跑道容量的航班恢復(fù)優(yōu)化調(diào)度

嚴(yán)宇 熊靜 陳聰聰 楊益沁 余佳瑩

摘 ?要：為了降低航班延誤造成的經(jīng)濟(jì)損失，在機(jī)場(chǎng)平穩(wěn)運(yùn)行條件下提高航班運(yùn)行效率。在原有的航班恢復(fù)模型基礎(chǔ)上，引入航空公司公平性模型、跑道容量約束、快速過(guò)站約束和取消航班約束的航班運(yùn)行的四種情況，建立顧及航空公司公平性的總成本最小的航班恢復(fù)目標(biāo)函數(shù)，該模型適用于不同航班數(shù)限制的機(jī)場(chǎng)。算例中對(duì)長(zhǎng)沙機(jī)場(chǎng)的某日4小時(shí)內(nèi)的航班運(yùn)行情況，使用飛蛾撲火算法得到優(yōu)化方案，與機(jī)場(chǎng)原始航班平均運(yùn)行成本相比，本文提及方法能降低機(jī)場(chǎng)的航班運(yùn)行成本。

關(guān)鍵詞：航班延誤恢復(fù);跑道容量;成本;航空公司公平性;飛蛾撲火算法

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

Abstract： In order to reduce the economic losses caused by flight delays， the efficiency of flight operations should be improved under the conditions of stable operation of the airport. On the basis of the original flight recovery model， the airline fairness model， runway capacity constraint， rapid transit constraint and flight cancellation constraint are introduced， and the four situations of flight operation are established to establish a flight recovery with the smallest total cost that takes into account the fairness of the airline objective function， the model is suitable for airports with different flight restrictions. In the calculation example， for the flight operation situation of Changsha airport within 4 hours on a certain day， the moth fire suppression algorithm is used to obtain an optimized scheme. Compared with the average operation cost of the original airport flight， the method mentioned in this paper can reduce the flight operation cost of the airport.

Key words： flight delay recovery; runway capacity; cost; airline fairness; Moth-Flame optimization algorithm

0 ?引 ?言

近年來(lái)，隨著航線及飛機(jī)數(shù)量的增加，世界各個(gè)國(guó)家和地區(qū)的機(jī)場(chǎng)地面和空中交通流量不斷增長(zhǎng)，目前在大部分中型以上機(jī)場(chǎng)產(chǎn)生了越來(lái)越嚴(yán)重的交通擁擠，一旦出現(xiàn)特殊情況，造成的航班延誤也越來(lái)越嚴(yán)重，所以中國(guó)許多機(jī)場(chǎng)開(kāi)始修建多條跑道來(lái)緩解交通堵塞造成的機(jī)場(chǎng)效率低下和航班延誤問(wèn)題。針對(duì)單跑道航班恢復(fù)問(wèn)題的研究相對(duì)比較成熟，該類航班恢復(fù)模型適用范圍不廣，但對(duì)不同跑道數(shù)量和運(yùn)行模式下航班延誤恢復(fù)的研究相對(duì)較少，因此有必要對(duì)此問(wèn)題進(jìn)行深入的探討分析。

針對(duì)航班恢復(fù)的研究，中外學(xué)者大多從航空公司角度出發(fā)，對(duì)于飛機(jī)、機(jī)組、旅客的逐一恢復(fù)和一體化恢復(fù)已經(jīng)有較為豐碩的研究成果[1-3]。從機(jī)場(chǎng)角度出發(fā)，1997年，Gilbo[4]最早構(gòu)建了考慮安全規(guī)則以及天氣影響的單機(jī)場(chǎng)延誤恢復(fù)模型;2004年，馬正平等[5]建立了一種考慮跑道容量的航班延誤優(yōu)化模型;2008年，丁建立等[6]構(gòu)建了機(jī)場(chǎng)大面積航班延誤后的一種航班恢復(fù)模型;丁建立等[7]引入航線因子，綜合考慮了航班延誤造成的經(jīng)濟(jì)損失;2011年，劉艷紅等[8]建立了只考慮顯性損失的恢復(fù)模型;2014年，楊歡等[9]建立了機(jī)場(chǎng)航班優(yōu)化調(diào)整模型，其中以機(jī)場(chǎng)成本、航空公司損失、旅客損失的加權(quán)最小化為目標(biāo)函數(shù);并在2017年首次提出了兩階段法即延誤發(fā)生前和發(fā)生后的航班調(diào)度優(yōu)化模型;汪虹宇[10]和楊順秀[11]分別構(gòu)建了航班延誤后機(jī)場(chǎng)登機(jī)口和停機(jī)位的優(yōu)化調(diào)度模型;2018年，賓云鵬等[12]考慮了各航空公司的公平性，構(gòu)建了以旅客滿意度為目標(biāo)函數(shù)的機(jī)場(chǎng)航班延誤恢復(fù)模型。

目前機(jī)場(chǎng)航班恢復(fù)問(wèn)題的研究已經(jīng)取得了一定的成果，但依然存在以下不足：（1）歷史研究中的航班恢復(fù)模型大多只適用于跑道構(gòu)型一定的機(jī)場(chǎng)，且未考慮到機(jī)場(chǎng)進(jìn)出港之間相互影響，適用性不強(qiáng);（2）在為航班安排合適的起飛和落地時(shí)間時(shí)，未考慮到航空公司的公平分配;（3）歷史研究中，未考慮快速過(guò)站的情況;（4）未考慮機(jī)場(chǎng)的實(shí)際運(yùn)行情況約束機(jī)場(chǎng)的航班取消;（5）在恢復(fù)過(guò)程中，未充分考慮航班的狀態(tài)。

針對(duì)以上不足，本文將以航空公司公平性和成本最小化為目標(biāo)函數(shù)。引入多跑道機(jī)場(chǎng)的容量約束，并結(jié)合機(jī)場(chǎng)航班快速過(guò)站，建立數(shù)學(xué)模型。選取我國(guó)某大型機(jī)場(chǎng)某日的航班實(shí)際運(yùn)行，通過(guò)飛蛾撲火算法對(duì)提及模型進(jìn)行求解。

1 ?問(wèn)題描述與假設(shè)

本文研究的問(wèn)題是考慮在機(jī)場(chǎng)容量限制下、多機(jī)型進(jìn)行航班任務(wù)調(diào)整的航班恢復(fù)問(wèn)題。在進(jìn)行航班調(diào)整時(shí)，同時(shí)考慮航空公司的運(yùn)行成本最小化和航空公司的公平性。

（2）不考慮機(jī)場(chǎng)的停機(jī)位容量;

（3）各航班的飛行時(shí)間是常量;

（4）飛機(jī)在機(jī)場(chǎng)均為降落—起飛。

2 ?模型建立

2.1 ?目標(biāo)函數(shù)

針對(duì)多機(jī)型、多跑道機(jī)場(chǎng)的航班恢復(fù)問(wèn)題，本文在兼顧機(jī)場(chǎng)航班運(yùn)行成本最低的目標(biāo)上，在考慮航空公司公平性的基礎(chǔ)上建立目標(biāo)函數(shù)。

2.6 ?航班取消數(shù)量約束

機(jī)場(chǎng)為保障旅客的權(quán)益，機(jī)場(chǎng)當(dāng)日的航班取消的情況不得過(guò)多。因此，限制當(dāng)天取消航班的航班數(shù)量不超過(guò)當(dāng)天航班總數(shù)的20%。

3 ?模型算法

本文使用格里菲斯大學(xué)學(xué)者M(jìn)irjalili提出的飛蛾撲火算法（Moth-flame optimization algorithm，MFO）。

設(shè)次日所有的航班時(shí)刻集合為一個(gè)飛蛾位置，飛蛾的位置限制需滿足約束條件限制，通過(guò)飛蛾撲火算法尋找目標(biāo)函數(shù)最低的值。

針對(duì)飛蛾撲火算法存在的易陷入局部最優(yōu)的問(wèn)題及搜索效率問(wèn)題，令飛蛾在靠近火焰時(shí)，通過(guò)指數(shù)遞減策略，以達(dá)到平衡全局搜索和局部搜索的能力。

對(duì)基于跑道容量的航班恢復(fù)問(wèn)題的求解的算法基本思路如下：

Step1：初始化算法參數(shù)，設(shè)置飛蛾種群大小，優(yōu)化變量的維數(shù)，最大迭代次數(shù)以及初始火焰數(shù)量;

Step2：初始化飛蛾的位置;

Step3：計(jì)算每只飛蛾的適應(yīng)度值，找出最優(yōu)飛蛾個(gè)體賦給火焰;

Step4：更新每只飛蛾與火焰的位置，并記錄當(dāng)前最優(yōu)火焰適應(yīng)度值;

Step5：判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到則輸出整個(gè)迭代過(guò)程中最優(yōu)火焰位置以及對(duì)應(yīng)的適應(yīng)度值，算法結(jié)束。

4 ?算例分析

4.1 ?數(shù)據(jù)來(lái)源

本文中以長(zhǎng)沙黃花機(jī)場(chǎng)（CSX）為例，對(duì)本模型的有效性進(jìn)行驗(yàn)證分析。選取長(zhǎng)沙黃花機(jī)場(chǎng)在2021年某日12：00～14：00航班信息（共有60架次航班的起降），并舍去原取消航班去除誤差，航班信息如表1所示。

在本文的目標(biāo)函數(shù)中，機(jī)型影響系數(shù)λ與機(jī)型的類別有關(guān)，根據(jù)最大起飛質(zhì)量、尾流類型將機(jī)型分為三類，如表2所示。

根據(jù)歷史航線航班量大小和城市距離，通過(guò)景崇毅[15]在論文中提及因子分析法和聚類分析法，對(duì)選取時(shí)間段長(zhǎng)沙機(jī)場(chǎng)涉及航班的航線因子λ進(jìn)行計(jì)算并歸一化處理，計(jì)算結(jié)果如表3所示。

4.2 ?測(cè)試結(jié)果分析

為驗(yàn)證本文提及模型的可行性，機(jī)場(chǎng)在12：15時(shí)，由于天氣原因，機(jī)場(chǎng)的跑道容量由原來(lái)的30架/小時(shí)降低為20架/小時(shí)，通過(guò)對(duì)比實(shí)際航班恢復(fù)中航司航班均恢復(fù)成本和本文提及方法的航班均恢復(fù)成本，驗(yàn)證本方法的優(yōu)勢(shì)。

通過(guò)本文對(duì)航班進(jìn)行恢復(fù)的結(jié)果如表4所示。

由于長(zhǎng)沙機(jī)場(chǎng)12：00～14：00的航班涉及到15家航空公司，在此分析部分航企的航班均運(yùn)行成本如表5、表6所示。CZ航司的航班均運(yùn)行成本低于MU、MF航司及機(jī)場(chǎng)航班均運(yùn)行成本，認(rèn)為由于CZ航司在長(zhǎng)沙機(jī)場(chǎng)建立了運(yùn)行基地，因此航班均運(yùn)行成本低。

5 ?結(jié) ?論

本文主要建立了考慮航空公司公平性的機(jī)場(chǎng)航班成本最低模型，并設(shè)置機(jī)場(chǎng)跑道約束、航班快速過(guò)站約束等約束來(lái)模擬機(jī)場(chǎng)航班實(shí)際運(yùn)行中的突發(fā)情況，最終利用飛蛾撲火算法計(jì)算航班的延誤成本。最后對(duì)比原始機(jī)場(chǎng)航班的運(yùn)行成本和航空公司公平性，本模型優(yōu)化后航班運(yùn)行時(shí)間較原始情況成本降低、公平性提高。

參考文獻(xiàn)：

[1] 趙秀麗，朱金福，郭梅. 航空公司不正常航班機(jī)組恢復(fù)模型和算法研究[J]. 交通科學(xué)與工程，2010，26（4）：76-79.

[2] 朱博，朱金福，高強(qiáng). 飛機(jī)和機(jī)組一體化恢復(fù)的約束規(guī)劃模型[J]. 交通運(yùn)輸工程學(xué)報(bào)，2013，13（1）：77-83.

[3] 楊歡，龐明寶，吳維. 基于動(dòng)態(tài)環(huán)境的機(jī)場(chǎng)航班實(shí)時(shí)調(diào)度優(yōu)化研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2017，47（1）：63-69.

[4] ?Gilbo E P. Optimizing airport capacity utilization in air traffic flowmanagement subject to constraints at arrival and departure fixes[J]. IEEE Transactions on Control Systems Technology， 1997，5（5）：490-503.

[5] 馬正平，崔德光. 機(jī)場(chǎng)航班延誤優(yōu)化模型[J]. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2004（4）：474-477，484.

[6] 丁建立，計(jì)金玲，黃劍雄. 基于免疫機(jī)制的航班延誤快速恢復(fù)模型及實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2008（19）：5029-5032.

[7] 丁建立，王新茹，徐濤. 航班延誤恢復(fù)調(diào)度的混合粒子群算法[J]. 交通運(yùn)輸工程學(xué)報(bào)，2008（2）：90-95.

[8] 劉艷紅，高林，李耀華. 基于經(jīng)濟(jì)損失的航班延誤恢復(fù)模型研究[J]. 中國(guó)民航大學(xué)學(xué)報(bào)，2011，29（1）：46-50.

[9] 楊歡，龐明寶，陳靜. 基于航班延誤的機(jī)場(chǎng)調(diào)度調(diào)整優(yōu)化研究[J]. 河北工業(yè)大學(xué)學(xué)報(bào)，2014，43（5）：101-105.

[10] 汪虹宇. 航班延誤后恢復(fù)及登機(jī)口資源調(diào)配研究[D]. 南京：南京航空航天大學(xué)（碩士學(xué)位論文），2017.

[11] 楊順秀. 面向延誤情景的機(jī)場(chǎng)停機(jī)位優(yōu)化調(diào)度研究[D]. 西安：西安理工大學(xué)（碩士學(xué)位論文），2018.

[12] 賓云鵬，邵荃，姜柯，等. 基于旅客滿意度與公平性的機(jī)場(chǎng)航班計(jì)劃恢復(fù)[J]. 科學(xué)技術(shù)與工程，2018（14）：275-278.

[13] ?Bengi Manley， Lance Sherry. Analysis of performance and equity in ground delay programs[J]. Transportation Research Part C， 2010，18（6）：910-920.

[14] 孫海勇，劉裕旭. 不同運(yùn)行模式下的遠(yuǎn)距平行跑道容量研究[J]. 航空計(jì)算技術(shù)，2019，49（5）：59-62，66.

[15] 景崇毅，孫宏. 基于因子分析和聚類分析的航線市場(chǎng)細(xì)分方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào)，2013，35（1）：122-126.

收稿日期：2021-07-25

作者簡(jiǎn)介：嚴(yán) ?宇（1997-），男，江蘇南京人，上海工程技術(shù)大學(xué)航空運(yùn)輸學(xué)院碩士研究生，研究方向：優(yōu)化算法、交通運(yùn)輸規(guī)劃;熊 ?靜（1979-），女，江西九江人，上海工程技術(shù)大學(xué)航空運(yùn)輸學(xué)院，副教授，碩士，研究方向：民航信息工程;陳聰聰（1995-），女，江蘇徐州人，上海工程技術(shù)大學(xué)航空運(yùn)輸學(xué)院碩士研究生，研究方向：交通運(yùn)輸規(guī)劃與管理;楊益沁（1997-），女，上海人，上海工程技術(shù)大學(xué)航空運(yùn)輸學(xué)院碩士研究生，研究方向：交通運(yùn)輸規(guī)劃與管理;余佳瑩（1995-），女，遼寧鞍山人，上海工程技術(shù)大學(xué)航空運(yùn)輸學(xué)院碩士研究生，研究方向：交通運(yùn)輸與規(guī)劃管理。