嚴(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 引 言

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

在航班時(shí)刻表優(yōu)化問題上，目前使用的算法有：粒子群算法、遺傳算法、模擬退火算法、蟻群算法等。齊莉[1]以航班調(diào)整量最小為目標(biāo)考慮了航班的銜接水平，并用基于小世界效應(yīng)的快速搜索算法求解。徐晨等[2]建立了國(guó)際航班中轉(zhuǎn)效率最大為目標(biāo)的航班時(shí)刻優(yōu)化模型，提出針對(duì)不同航班特性的時(shí)隙優(yōu)化方法，最后通過(guò)遺傳算法優(yōu)化祿口機(jī)場(chǎng)時(shí)刻表。隨著科學(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ī)場(chǎng)時(shí)刻表的優(yōu)化研究還很少。本文將以樞紐機(jī)場(chǎng)各個(gè)中轉(zhuǎn)航班對(duì)的平均銜接時(shí)間最小為目標(biāo)，利用改進(jìn)飛蛾撲火算法（MFO算法） 給出新的航班時(shí)刻表。

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

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

1.1 相關(guān)概念

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

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

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

1.2.1 確定滿足繞航條件的航班對(duì)

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

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

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

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

1.2.3 約束條件

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

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

表1 模型約束條件

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

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

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

記：

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

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

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

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

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

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

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

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

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

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

隨著迭代的進(jìn)行，ω 的值由1 到0 逐步減少，迭代步長(zhǎng)變短，避免了飛蛾錯(cuò)過(guò)最優(yōu)解。通過(guò)測(cè)試函數(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í)例分析

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

（1） 航班平均銜接時(shí)間

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總 結(jié)

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

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