基于改進(jìn)飛蛾撲火算法的機(jī)場航班時刻銜接優(yōu)化

嚴(yán) 宇，熊 靜，張文成，劉 超 YAN Yu, XIONG Jing, ZHANG Wencheng, LIU Chao

（上海工程技術(shù)大學(xué) 航空運(yùn)輸學(xué)院，上海201620）

(Air Transport College, Shanghai University of Engineering Science, Shanghai 201620, China)

0 引 言

目前我國航空旅客周轉(zhuǎn)量快速增加，由2014 年的6 334.19 億人次增長到2019 年的11 705.10 億人次。雖然現(xiàn)在的航空網(wǎng)絡(luò)非常發(fā)達(dá)，但也不是任意兩個機(jī)場之間都可以直航，但是可以選擇合適的中轉(zhuǎn)機(jī)場到達(dá)自己的目的地。旅客不希望中轉(zhuǎn)候機(jī)時間太長，這樣就要求中轉(zhuǎn)機(jī)場對到達(dá)航班和接續(xù)航班的時刻能夠很好的銜接。由于樞紐機(jī)場日航班起降量大，要討論的是整個樞紐機(jī)場各個航向上的銜接，計算數(shù)據(jù)量龐大，必須使用優(yōu)化算法對目前航班時刻表進(jìn)行優(yōu)化。

在航班時刻表優(yōu)化問題上，目前使用的算法有：粒子群算法、遺傳算法、模擬退火算法、蟻群算法等。齊莉[1]以航班調(diào)整量最小為目標(biāo)考慮了航班的銜接水平，并用基于小世界效應(yīng)的快速搜索算法求解。徐晨等[2]建立了國際航班中轉(zhuǎn)效率最大為目標(biāo)的航班時刻優(yōu)化模型，提出針對不同航班特性的時隙優(yōu)化方法，最后通過遺傳算法優(yōu)化祿口機(jī)場時刻表。隨著科學(xué)的進(jìn)步，不斷有新的仿生算法出現(xiàn)。澳大利亞的Mirjalili[3]提出了一種模仿夜間飛蛾橫向定位導(dǎo)航方式的新穎啟發(fā)式算法——飛蛾撲火算法（MFO算法），且該算法全局搜索能力和局部收斂速度均優(yōu)于以上優(yōu)化算法。目前，關(guān)于該算法的研究也剛剛開始[4-5]，其應(yīng)用研究有：把飛蛾撲火算法應(yīng)用于水資源的優(yōu)化配置問題[6]、作業(yè)間車輛的調(diào)度問題[7-8]等，用于機(jī)場時刻表的優(yōu)化研究還很少。本文將以樞紐機(jī)場各個中轉(zhuǎn)航班對的平均銜接時間最小為目標(biāo)，利用改進(jìn)飛蛾撲火算法（MFO算法） 給出新的航班時刻表。

1 最小機(jī)場銜接時間的優(yōu)化模型

首先，在航班飛行方向上用繞航系數(shù)篩選合適的城市對；然后在機(jī)場運(yùn)行約束下，針對城市對的銜接航班進(jìn)行最小銜接時刻優(yōu)化。

1.1 相關(guān)概念

繞航系數(shù)影響樞紐機(jī)場對旅客的吸引力[9]。設(shè)Dik為始發(fā)機(jī)場i與樞紐機(jī)場k的距離，Akj是樞紐機(jī)場k與目的地機(jī)場j的距離，Dij是始發(fā)機(jī)場i與目的地機(jī)場j的距離，定義繞航系數(shù)Rij如下：

航班時隙、計劃過站時間、機(jī)場時刻容量需要滿足國家的相關(guān)要求。

1.2 航班時刻表優(yōu)化問題解析與模型構(gòu)建

1.2.1 確定滿足繞航條件的航班對

設(shè)出發(fā)城市集合為X=｛i|i=1,2,3,…,n｝；抵達(dá)城市集合為Y=｛j|j=1,2,3,…,n｝；樞紐機(jī)場為k；由式（1） 繞航系數(shù)的定義可知，一般情況下Dik+Akj≥Dij，即Rij≥1。根據(jù)文獻(xiàn)[11]，繞航系數(shù)Rij的范圍選定可認(rèn)為小于等于1.4 時，轉(zhuǎn)機(jī)有效；大于1.4時，為無效轉(zhuǎn)機(jī)。由此定義轉(zhuǎn)機(jī)決策系數(shù)uij：

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

考慮所有可中轉(zhuǎn)城市對的所有航班的平均銜接時間，使得它們的和最小。目標(biāo)函數(shù)為：

其中：是i市到j(luò)市的中轉(zhuǎn)等候時長；kij表示一條i市到j(luò)市的轉(zhuǎn)機(jī)線路。對航班時刻表的優(yōu)化，符合繞航系數(shù)的城市對是航班時刻優(yōu)化的前提，機(jī)場時刻容量、航班最小過站時間相互影響，又是航班時刻優(yōu)化的約束，目的是使樞紐機(jī)場平均旅客的銜接時間最小。

1.2.3 約束條件

在本研究中，根據(jù)已有航班時刻表，認(rèn)為航空公司已安排合適的機(jī)組和機(jī)型。因此，認(rèn)為航班時刻表優(yōu)化問題的限制條件為機(jī)場運(yùn)行時刻限制、飛行器最小過站時間限制和航班調(diào)整時間限制。

定義以下參數(shù)：ij城市對航班中，i城市到樞紐機(jī)場的航班抵達(dá)時刻（k1代表某航班）；ij城市對航班中，樞紐機(jī)場到j(luò)城市的航班出發(fā)時刻（k2代表某航班）；樞紐機(jī)場的平均旅客銜接時間Zk；i市到j(luò)市的轉(zhuǎn)機(jī)線路總數(shù)Xij。航班時刻表應(yīng)滿足約束如表1 所示。

表1 模型約束條件

2 改進(jìn)飛蛾撲火算法

2.1 傳統(tǒng)飛蛾撲火算法

2015 年格里菲斯大學(xué)學(xué)者M(jìn)irjalili 根據(jù)飛蛾圍繞火焰做對數(shù)螺旋曲線軌跡的行為提出了飛蛾撲火算法（Moth-flame optimization algorithm，MFO）。設(shè)矩陣M為飛蛾的集合，即當(dāng)前的搜索位置，矩陣OM為飛蛾的適應(yīng)度值；矩陣F為燭火的集合，即當(dāng)前的搜索的最優(yōu)解位置，矩陣OF為燭火的適應(yīng)度值。問題的變量為空間中飛蛾的位置，通過改變飛蛾的位置向量，逐步得到最優(yōu)的燭火位置。

記：

式中：n指飛蛾的數(shù)量，d指變量的維數(shù)。

MFO算法是一個近似優(yōu)化問題全局最優(yōu)的三元組：

I是一個生成飛蛾隨機(jī)種群和相應(yīng)適應(yīng)度值的函數(shù)。I的模型如下：

算法中的主函數(shù)P，它負(fù)責(zé)在搜索空間中的移動飛蛾。這個函數(shù)接收M的矩陣，并最終返回其更新后的矩陣。函數(shù)P可以表示為：

T函數(shù)是終止條件判斷函數(shù)。若終止條件滿足，T函數(shù)返回true，如果終止條件不滿足，返回false。函數(shù)T可以表示為：

記Mi為第i只飛蛾的位置，F(xiàn)j為第j個火焰的位置，b為對數(shù)螺旋函數(shù)的一個常數(shù)；t為［-1,1 ］之間的隨機(jī)數(shù)。飛蛾的螺旋模擬飛行公式如下：

飛蛾通過此迭代公式不斷更新自己的位置，最后求得火焰的位置。由于飛蛾的路徑是逐步接近火焰的，所以其迭代過程很容易陷入局部最優(yōu)解。因此，得到新的火焰后，對所有火焰的適應(yīng)值排序，通過式（13） 得到火焰數(shù)量的自適應(yīng)變化公式。其中，N為燭火數(shù)目的最大值，l為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)。

2.2 改進(jìn)的飛蛾撲火算法

傳統(tǒng)MFO算法中飛蛾位置的更新機(jī)制是使飛蛾飛向燭火，但易使飛蛾錯過全局最優(yōu)，有一定的不足。本文引進(jìn)自適應(yīng)權(quán)重方法，當(dāng)飛蛾在靠近最優(yōu)解時，自適應(yīng)權(quán)重的值減小，可以提高算法后期的探測能力[10]。自適應(yīng)權(quán)重ω 的具體計算公式如下：

由此得到更新的飛蛾位置：

隨著迭代的進(jìn)行，ω 的值由1 到0 逐步減少，迭代步長變短，避免了飛蛾錯過最優(yōu)解。通過測試函數(shù)檢驗(yàn)，改進(jìn)后的MFO算法具有較好的收斂精度和全局尋優(yōu)能力，尋優(yōu)效果優(yōu)于傳統(tǒng)的MFO算法。

改進(jìn)MFO算法流程結(jié)構(gòu)如圖1 所示。

圖1 改進(jìn)MFO 算法流程圖

3 運(yùn)算實(shí)例分析

西安咸陽機(jī)場是我國西部重要的航空樞紐機(jī)場。本文以西安咸陽機(jī)場為中轉(zhuǎn)樞紐機(jī)場，利用改進(jìn)飛蛾撲火算法，以優(yōu)化銜接時間最小為目標(biāo)進(jìn)行時刻優(yōu)化。根據(jù)2019 年7 月8 日西安咸陽機(jī)場的國內(nèi)航班時刻表，通過Matlab R2018a 仿真，得到以下優(yōu)化結(jié)果。

（1） 航班平均銜接時間

使用傳統(tǒng)MFO算法與改進(jìn)MFO算法航班優(yōu)化后平均銜接時間與迭代次數(shù)的關(guān)系如圖2所示。

由圖2，傳統(tǒng)MFO算法得到的平均銜接時間為1.45 小時，改進(jìn)的MFO算法得到的平均銜接時間為1.26 小時，說明改進(jìn)的MFO算法尋優(yōu)能力優(yōu)于傳統(tǒng)MFO算法。

圖2 西安機(jī)場的航班時刻表優(yōu)化的目標(biāo)函數(shù)值計算

（2） 優(yōu)化后中轉(zhuǎn)信息

輸出優(yōu)化后的西安機(jī)場航班時刻表符合要求的中轉(zhuǎn)航班對共有1 688 對，數(shù)據(jù)較大，此處不一一列出。僅舉一例，延安機(jī)場一天有2 班至西安的航班，按改進(jìn)MFO算法優(yōu)化后的轉(zhuǎn)機(jī)銜接航班共有21 個，如表2 所示。

表2 優(yōu)化后的西安機(jī)場時刻表延安與其他城市的中轉(zhuǎn)航班對

（3） 航班調(diào)整時間量

原始航班時刻表經(jīng)改進(jìn)MFO算法優(yōu)化后航班需調(diào)整時間如表3 所示（部分）：

表3 優(yōu)化后西安機(jī)場時刻表的調(diào)整時間

（4） 調(diào)整量分布

原始航班時刻表經(jīng)改進(jìn)MFO算法優(yōu)化后航班調(diào)整時間分布如圖3 所示。

在西安機(jī)場起降的812 個航班中，有618 個航班的調(diào)整量為26～30min。可見為了滿足轉(zhuǎn)機(jī)條件，航班需要進(jìn)行較大規(guī)模的調(diào)整，若機(jī)場航班時刻表的優(yōu)化應(yīng)用則需要多方面協(xié)調(diào)。

圖3 西安機(jī)場時刻表優(yōu)化后航班調(diào)整時間分布

4 總 結(jié)

航班時刻表中轉(zhuǎn)時刻優(yōu)化對我國建設(shè)區(qū)域樞紐機(jī)場及支線航班網(wǎng)絡(luò)建設(shè)有較大的實(shí)用價值。本文首先篩選適合中轉(zhuǎn)的航班對，建立優(yōu)化模型，通過仿真實(shí)驗(yàn)，介紹飛蛾撲火算法的原理，并說明使用改進(jìn)飛蛾撲火算法優(yōu)化航班中轉(zhuǎn)銜接時間優(yōu)于傳統(tǒng)飛蛾撲火算法，改進(jìn)后的航班提高了樞紐機(jī)場的整體銜接水平。本文算法還可以給出各機(jī)場在中轉(zhuǎn)機(jī)場具體的各方向中轉(zhuǎn)時刻表，適用性廣。

下一步研究，航班時刻模型可以涉及機(jī)場資源、航路資源等，在CDM 系統(tǒng)上對航班時刻中轉(zhuǎn)優(yōu)化。