基于粒子群優化算法的機場群航班優化配置研究

朱金福 ，馬睿馨,2，彭安娜，嚴 琛

(1. 南京航空航天大學 民航學院，江蘇 南京 211106; 2. 中國航發商用航空發動機有限責任公司 上海 200241)

0 引 言

2016年，中國民用航空局發布的《中國民用航空“十三五”規劃》指出，北京、廣州、上海機場國際樞紐競爭力仍需提高，建設成適合京津冀、珠三角、長三角城市群的世界級機場群，并不斷提高機場群整體效率。然而，隨著我國機場群的不斷發展，機場群內各機場發展并不協調。

從當前的發展勢態來看，我國三大機場群普遍存在一級國際樞紐機場始終處于龍頭地位、容量日益飽和的現象，如京津冀機場群內的北京首都國際機場、長三角機場群內的浦東國際機場和虹橋國際機場以及珠三角機場群內的廣州白云國際機場。機場群內其他機場則存在旅客吞吐量低、與樞紐機場航線同質化嚴重而造成旅客分流的現象。長此以往將不利于機場群各機場之間協調發展，形成惡性競爭。如果能夠對我國機場群的航空資源進行有效整合，在合理定位機場群內機場角色與分工的基礎上，疏解一級國際樞紐機場的航班時刻資源，調整低效航線航班至周邊機場，為符合戰略的航班騰出空間，減少因擁堵引發的航班延誤，則可以改善當前發展不平衡的現狀，提高機場群整體運輸效率和航空公司經濟效益[1]。

關于航線航班時刻資源優化的國內外研究成果較多。在單個機場航班頻率、 航班時刻資源分配研究方向，A. I. CZERNY[2]、H. FUKUI[3]、D. WILKEN等[4]、P. PELLEGRINI等[5]、K.G.ZOGRAFOS等[6]、A. JACQUILLAT等[7]、齊莉[8]、陳梵驛等[9]分別從擁堵、延誤、航空公司公平性、旅客需求、航班波等多個不同角度展開研究，通過建立數學模型，進行優化與調配，使得單機場的航班時刻優化建模更加貼近實際應用。另有許多國內外學者從空管的角度進行航線航班優化，如王倩[10]、朱承元等[11]、楊新湦等[12]分別針對航路容量、航路點沖突、流量限制、地面排隊等待、空域仿真等問題入手，進行單機場或機場群航班時刻優化。在以機場群為整體的研究領域中，R. D. NEUFVILLE[13]、韋薇[14]、夏玉中[15]、陳欣等[16]、曹香玲[17]從協同發展的角度，提出我國機場群協同發展還處于探索的初期，應注重于合作模式、發展路徑，批量調整航線航班，為我國航線航班的優化提出了新思路。在數學模型建模與優化求解中，DENG Wu等[18]、陳嫻等[19]利用粒子群優化算法，求解了各種優化模型，為筆者的求解方法提供了思路。

現有的國內外航班時刻優化研究大多是從單機場角度出發，未能考慮機場群整體與各機場訴求，沒有在機場群發展的戰略層面上依據機場的功能定位進行航班時刻的優化。而國內外關于機場群的研究仍處于探索階段，部分研究機場群的學者應用多種評價模型發現了我國機場群發展不均衡的問題，在管理制度上提出了建議。基于目前對機場群航班時刻優化的研究較少等問題，筆者構建了以機場群效益最大化的航班時刻優化模型，并運用粒子群優化算法進行求解，最后以長三角機場群為例進行實例驗證。

1 航班時刻優化原則

筆者以疏散一級國際樞紐機場航班為目標，將超出機場容量、運行效果差的航班按照機場群內各機場功能定位重新分配起降機場和起降時刻。以此為優化原則，從機場、航空公司和旅客三方角度出發，采用機場準點率、航空公司市場占有率、旅客損失時間、機場功能定位這4個指標評價航班運行效果并作為航班時刻優化目標。

1.1 機場準點率

機場準點率是反映機場實際運行中擁堵情況的重要標準之一。容量飽和、航班時刻資源擁擠的機場，準點率會大大降低。對于準點率較低的機場，有可能是由于容量飽和引起的，應考慮進行航班流量疏散。但由于機場準點率不僅與資源利用是否飽和相關，也與流量控制、天氣等因素有關，故利用起降機場年平均準點率作為指標。

1.2 航空公司市場占有率

航空公司市場占有率體現了航空公司在航線規劃上的戰略部署。每一家航空公司均對目標航空市場有所規劃，并希望不斷擴大航線上的市場份額。各航空公司在戰略航線上加大運力投放，更有利于本航空公司構建戰略航線網絡和形成航班波，從而提升航空公司競爭力。

1.3 旅客損失時間

旅客損失時間，即旅客預計出發(或到達)時間和實際出發(或到達)時間的偏差，旅客一般都會選擇與預計時間最近的航班，它體現了航班是否能夠滿足旅客出行的需求。同時在現實航班時刻的編排過程中，航班時刻資源變更的困難較大，少有航班時刻能夠進行較大變動。

1.4 航班功能定位

根據民航局對機場群內各機場的功能定位，一級國際樞紐機場為具有國際競爭力的國際航空樞紐，二級樞紐機場為以國內點對點航班和國際優質遠程航線為主的區域樞紐，而機場群內其他干線機場主要發展國內航線航班。

2 航班時刻優化模型

為了有效解決機場群內資源不均衡、航線網絡結構不符合發展要求的矛盾，同時兼顧機場運行容量、航空公司戰略發展、旅客需求、機場戰略定位的條件，筆者以現有航班時刻表為基礎，通過重新分配各航班的起降機場和起降時刻，使各機場容流平衡、減少同質化航線航班，以滿足機場群戰略規劃的要求。

2.1 模型假設

模型包括以下假設條件：

1)機場群內各機場歸屬于同一個機場管理集團，航班時刻資源由機場管理集團統一調配。機場管理集團內行政阻礙少，機場協作制度健全，航空公司能夠配合機場管理集團的資源規劃。

2)不改變航班的執飛航空公司，即重新分配起降機場和時刻的航班仍由原航空公司執飛。

3)優化前后航段飛行時間不變。

4)不考慮對方機場的容量限制。

2.2 目標函數

根據第1節所述航班時刻優化原則，以機場群內準點率、航空公司市場占有率、旅客損失時間和機場功能定位4個角度指標最大化為目標，建立機場群航班時刻優化模型如式(1)、式(2)：

(1)

(2)

2.3 約束條件

2.3.1 航班唯一性約束

航班唯一性約束即一個航班只能有一個起降機場和起降時刻，如式(3)、式(4)：

(3)

(4)

2.3.2 高峰小時容量限制

機場的進離港架次存在容量限制，一旦超出容量容易發生航班堆積和擁堵。因此調整航班時應考慮到起降機場的容量限制情況。筆者以5 min時間片的機場容量為單位進行約束，如式(5)：

(5)

2.3.3 滿足航班連續性約束

作為一個航班串任務內的連續性航班，必須對航空器在機場中轉時最小中轉時間和最大中轉時間進行約束，如式(6)、式(7)：

(6)

(7)

式中：

3 模型求解

3.1 粒子群優化算法概述

粒子群優化算法(PSO)是基于群體的進化算法，起源于對鳥類捕食行為的仿真模擬。當PSO應用于求解優化問題時，問題的解與粒子在搜索空間中的位置相對應。每個粒子包含粒子的位置和速度(決定飛行的方向和距離)以及設計的優化函數適應度值兩個屬性。在每次迭代過程中，粒子通過記憶跟蹤兩個極值來更新自身的位置：一個是粒子自身搜索到的最優解，稱為個體極值點(用Pid表示其位置)；另一個是整個粒子組群體找到的最優解，稱為全局極值點(用Pg,d表示其位置)。在找到這兩個最優解后，粒子將根據式(8)、式(9)，更新其速度和位置：

(8)

(9)

式中:Vid為第i個粒子在第d維度上的速度；w為慣性權值；η1和η2為學習參數；rand()定義為(0,1)之間的隨機數。粒子群初始速度隨機產生，重復應用式(1)和式(2)進行迭代，直到找到滿意的解。

3.2 改進的粒子群優化算法設計

針對研究的問題，設計的粒子群優化算法包括算法編碼、初始解、適應度函數設計和更新規則。

3.2.1 算法編碼

由于筆者涉及到機場群內某個機場和起降時刻兩個維度，同時還涉及到多個航班統一調配，直到找到最佳方案，因此在改進的粒子群算法中，一個粒子的位置表示待求解的航班集合，粒子zi構造如式(10)：

zi=[(x1,v1),(x2,v2),…,(xn,vn)]

(10)

式中：zi為粒子群中的第i個粒子；(xn,vn)為第n個航班于時刻vn從機場群內機場xn起降。

3.2.2 初始解

粒子群優化算法對初始解有較強的依賴性。初始解較差則可能降低粒子群優化算法的收斂速度。筆者將初始的航班數據作為初始可行解。

3.2.3 適應度函數設計

適應度函數是對每個粒子是否最優的評價。筆者以模型中的目標函數，作為適應度函數。

由于模型中4個指標的權重為1，但各自度量單位不同，需要把有量綱表達式變成無量綱表達式，使不同單位或量級的指標能夠進行比較和加權。因此，應當根據標準化原則對4個指標進行標準化處理后，再計算適應度函數，如式(11)：

(11)

同時，為了有效約束新生成的粒子在可行解范圍內，將不滿足約束粒子的適應度值加上無限大的懲罰值M。即每個粒子zi的適應度函數構造如式(12)：

(12)

式中：M=10 000；ui為0-1變量，當粒子z滿足模型約束條件時ui=0，不滿足時ui=1。

3.2.4 更新規則

粒子的位置和速度更新規則為式(8)、式(9)，其中c1=c2=2，w作為慣性權重系數，很大程度上影響粒子群的全局搜索能力。由程序反復試驗確定改進的粒子群算法中采用0.9～0.4線性遞減的策略，如式(13)：

(13)

式中：wini為初始慣性權重系數，取wini=0.9；wend為迭代至最大次數時的慣性權重系數，取wend=0.4；Gmax為最大迭代次數，取Gmax=100;k為當前迭代次數。

算法步驟如下：

Step 1依據初始航班數據生成1個粒子，并隨機產生49個粒子，組成一個粒子群。其中粒子的位置zi代表一組解。

Step 2計算每個粒子的適應度值，根據式(12)計算。

Step 3由式(14)更新每個粒子的最好位置：

(14)

(15)

Step 4更新所有粒子的位置和速度，根據式(8)、式(9)計算。

Step 5重復Step 2到Step 4，直到最大迭代次數和相鄰兩次迭代的差值滿足最小閥值的終止條件。

Step 6輸出最終結果。

4 實例應用

4.1 樣本選取和參數設計

以2019年長三角機場群運行情況為例，上海虹橋機場與浦東國際機場的旅客吞吐量占整個機場群旅客吞吐量的49%，起降架次占比達43%。長三角機場群內其他機場的旅客吞吐量和起降架次卻不足17%。浦東國際機場旅客中轉率達12%，沒有達到規劃中的15%～20%，還未建設成具備擁有國際競爭力的中轉樞紐。浦東國際機場的通航點中，與周邊機場重復的通航點占37%。虹橋國際機場的通航點中，有62%的通航點與周邊機場重復。可見機場群內各機場存在航線同質化程度高、運輸效率低等問題。

筆者以長三角機場群內的浦東國際機場、虹橋國際機場、杭州蕭山國際機場、南京祿口國際機場(機場編號i=1，2，3，4)4個機場作為研究對象，從OAG公布的2017年11月的國內外航班時刻表作為歷史數據，從飛常準網站公布的機場準點率作為準點率數據，以民航局公布的國內主要機場小時容量數據作為容量限制數據。其中，各機場5 min高峰航班起降架次容量為C1=6架次/5 min，C2=3架次/5 min，C3=3架次/5 min，C4=3架次/5 min。4個機場的進離港準點率為D1=73.01%,D2=77.1%,D3=61.35%,D4=64.18%。

4.2 模型驗證

由于對全天的航班時刻進行優化，數據量大、模型復雜，故先選取小范圍數據進行模型驗證，再應用于大范圍的全天航班時刻優化。以2017年11月21日08:00—09:00長三角機場群4個機場共142個航班時刻為對象進行模型驗證，其中上海浦東國際機場(PVG)共70個航班，上海虹橋國際機場(SHA)37個航班，杭州蕭山國際機場(HGH)16個航班，南京祿口國際機場(NKG)19個航班。部分初始數據如表1。

表1 長三角機場群航班時刻數據(部分)Table 1 Flight schedule data of Yangtze River Delta multi-airportsystem (partial)

采用Python進行粒子群優化算法編程求解。粒子群適應度值變化曲線如圖1。當迭代至40次左右，適應度值基本保持不變，粒子群算法收斂，對所研究問題的適用性較強。

圖1 適應度值變化曲線Fig. 1 Change curve of fitness value

4.3 結果分析

根據計算結果，上海兩場08:00—09：00的107個航班中，共調整了其中的18個航班。18個航班的調整優化情況如表2。

表2 航班時刻優化結果Table 2 Flight schedule optimization results

以FM9415航班為例，原航班應于08:00從上海虹橋國際機場起飛，現調整為08:20從杭州蕭山國際機場起飛。原航班應于09:30到達連云港白塔埠機場，經優化后由于航段飛行時間不變，調整為09:50到達。圖2顯示了長三角機場群4個機場優化前后的航班數量變化情況。由圖2可以看出，上海浦東國際機場調整量較大，其中國際航班保留不變，優化的均為將國內航班疏解至周邊機場，符合預期的優化策略。同時，南京祿口國際機場航班增幅略微大于杭州蕭山國際機場。分析原因是由于南京祿口機場的準點率高于杭州蕭山機場，所以大部分航班會優先分配到南京祿口機場。

圖2 長三角機場群08:00—09:00機場航班數量變化Fig. 2 Flight number change of Yangtze River Delta multi-airportsystem from 08:00 to 09:00

圖3描述了各機場優化前和優化后航班時刻分布情況和變化趨勢。優化前各機場起降架次波動幅度較大，某些時刻下航班起降架次過于突出。經過優化調整后，各機場起降架次較相對穩定，航班在各時刻分布相對平均。起降架次基本控制在機場容量范圍內，避免因為某時刻航班量過大而引發延誤。

圖3 長三角機場群優化前后時刻表變化Fig. 3 Change of flight schedule of Yangtze River Delta multi-airport system before and after optimization

由圖3可以看出，用筆者模型算法調整機場群航班時刻比較符合實際情況，能夠合理配置機場群航班時刻資源。但模型驗證中選擇的數據集模型較小，僅為1 h內數據(08:00—09:00)，不能反映該天內航班計劃優化情況，故選取2017年11月21日全天共2 707個航班數據再次進行優化求解。

對該天長三角機場群運行情況進行調研，將重要的機場運行特征數據進行統計，如表3。由表3可以看出，在1 d為周期范圍內，浦東國際機場與虹橋國際機場航班架次遠遠超過該機場的起降容量，而南京祿口機場和杭州蕭山機場仍有起降架次的增長空間。

表3 長三角機場群運行特征數據統計Table 3 Statistics of operation characteristics of Yangtze River Deltamulti-airport system

通過粒子群優化算法求出，長三角機場群單位時間窗的最大調整量為45架次，航班調整總量為143架次。其中，浦東國際機場調整量為128架次，虹橋國際機場的調整量為15架次。

使用Python進行編程求解，將長三角機場群該天24 h優化前后的航班時刻優化方案輸出如圖4。

圖4(a)展現了優化前后上海浦東國際機場的航班時刻分布情況，由對比可知，單位時間窗的高峰架次經優化由121調整為76。優化前09:00—11:00和21：00—22：00是上海浦東國際機場的繁忙時段，優化后09:00—22:00的進離港架次較為平均。圖4(b)展現了優化前后的上海虹橋國際機場航班時刻分布情況，對超出機場容量的12:00—14:00和15:00—16:00兩個時段航班計劃進行了優化，各時段架次得到有效控制。圖4(c)、圖4(d)分別是杭州蕭山機場和南京祿口機場優化前后的航班時刻分布情況。由圖4(c)～(d)可以看出，在部分不繁忙時刻增加航班量分擔了上海浦東和虹橋機場超負荷運行的航班，同時也不超過自身機場的運行容量限制，分擔了樞紐機場高峰時段航班運行壓力。

圖4 長三角機場群全天航班時刻表Fig. 4 All day flight schedule of Yangtze River Delta multi-airport system

綜上所述，經航班時刻優化，長三角機場群各時段架次均得到有效控制，各機場高峰時段航班架次分布更均衡，有效緩解樞紐機場超負荷運行造成航班延誤的壓力，高峰時段航班架次顯著降低。

5 結 語

我國三大機場群自規劃建設以來，始終缺乏統一的航班時刻資源調整與分配。機場群內一級國際樞紐機場旅客吞吐量處于機場群內龍頭地位，但各機場之間航線同質化程度高，如此發展難以達到機場群規劃中的戰略要求。筆者建立的模型，從機場群內航空公司、機場、旅客3個角度出發，以解決不平衡發展為目的，將一級國際樞紐機場運行效果差的航班資源合理配置至周邊機場。設計改進的粒子群優化算法進行求解，并以長三角實際數據進行了案例研究，優化后長三角機場群的各機場起降架次普遍控制在容量限制范圍內，航班在各時刻分布較為均衡，為機場群航班時刻資源配置提供優化手段和參考依據。