基于Graph WaveNet模型的機場網絡延誤預測

姜 雨 戴垚宇 劉振宇 吳薇薇 顧 欣

(南京航空航天大學民航學院1) 南京 211106) (北京工業大學北京市交通工程重點實驗室2) 北京 100124)

0 引 言

航班延誤不僅會擾亂機場運行秩序,甚至可能波及整個機場網絡,打亂航班計劃,對機場和航空公司造成嚴重損失[1].準確可靠的航班延誤預測是降低延誤影響的關鍵,能夠提高航班延誤應對效率,為運行決策提供重要依據.

目前,國內外學者針對航班延誤進行了一系列研究。王春政等[2]闡述了航班延誤成因,并對現有延誤預測研究進行系統性分類總結.傳統方法、機器學習及深度學習等方法都廣泛應用于航班延誤預測研究.傳統方法和機器學習研究中。羅赟騫等[3]以上游機場離港延誤為輸入,采用支持向量機建立延誤模型預測下游航班的到港延誤。郭野晨風等[4]針對惡劣氣象條件引入天氣影響交通指標(WITI),采用多元線性回歸及BP神經網絡建模進行機場延誤預測。王語桐等[5]采用逐步回歸算法和主成分分析法篩選影響延誤的顯著因素,基于支持向量回歸和線性回歸組合預測航班延誤.深度學習研究中,Guvercin等[6]采用聚類模型對美國機場網絡建模,選取典型機場進行延誤預測。王春政等[7]面向機場網絡各子系統交互作用下的延誤特征涌現建立Agent模型,基于貝葉斯估計及模糊k階鄰域方法參數挖掘,并進行機場網絡延誤預測。吳仁彪等[8]引入注意力機制構建CBAM-CondenseNet模型,考慮延誤波及影響進行航班延誤預測。屈景怡等[9]提出基于區域殘差和長短時記憶的深度學習模型,融合機場、氣象及航班信息進行機場延誤預測,預測精度優于傳統算法.此外,航班延誤對機場網絡的波及傳遞影響近年來也備受關注.Baspinar等[10]采用傳染病模型模擬航班延誤發生、傳播及恢復,分析航班延誤的傳播機理.Baspinar等[11]將排隊網絡模型應用于歐洲機場網絡,模擬延誤在網絡中的傳播,提出機場容量低于特定臨界值時將導致延誤激增.

以上研究多面向單一或數個機場進行延誤預測,缺乏從機場網絡角度考慮航班延誤在機場間的傳播影響.同時,深度學習模型普遍基于固定的網絡結構挖掘空間關聯性,易受不確定因素和數據不完全等干擾.而且現有研究實驗數據集規模較小,在處理高維機場網絡大數據時需要降維,易導致數據特征缺失。文中提出一種基于深度Graph WaveNet(GWN)模型的機場網絡延誤模型.GWN模型了融合時間卷積網絡(temporal convolutional network,TCN)和圖卷積網絡(graph convolutional network,GCN),保留時間卷積網絡并行計算、低內存等優勢,高效處理高維延誤數據,引入圖卷積層挖掘空間關聯性.GWN模型對機場網絡整體建模,挖掘圖結構化的航班延誤信息,通過雙向卷積捕捉航班延誤傳播規律,加入自適應鄰接矩陣提升預測效果,對網絡中所有機場進行多步延誤預測.

1 模型建立

1.1 機場網絡延誤問題簡述

機場網絡延誤預測問題的本質是時序預測問題.將機場網絡抽象為一個有向權重圖G=(V,E,A).V為含有N個機場節點的集合;E為機場之間連接關系的邊的集合;A∈RN×N為預設權重的鄰接矩陣,其中Aij用來表征由Vi機場至Vj機場的連接度.機場網絡中,機場間的航線數量直接影響延誤傳播,因此選用機場間有向通航航線數量作為空間連接度指標.

時間窗口t中,機場網絡的延誤狀態以動態的圖信號Xt∈RN×D表示.采用多步延誤預測,即基于已知的P個時間窗口的歷史觀察值和表征空間結構的圖G遞歸預測未來Q個時間窗口的機場離港航班準點率.其映射關系為

(1)

式中:(Xt-P+1,…,Xt)∈RP×N×D,(Xt+1,…,Xt+Q)∈RQ×N×D.

1.2 空間卷積層

采用基于切比雪夫濾波器的一階近似,通過對節點鄰域信息進行聚合和變換來平滑節點信號,且適用于多維輸入.圖卷積層的定義為

Y=AWX

(2)

式中:Y∈RN×M為輸出圖信號;A∈RN×N為鄰接矩陣;W∈RD×M為模型參數;X∈RN×D為含N個節點和D類特征的輸入圖信號.

上述模型的缺點是只適用于無向圖結構.為抓取有向圖的空間關聯性,Li等[12]提出適用于有限k階圖信號的前向和后向擴散卷積.擴散卷積建模為

(3)

式中:Pk為轉移矩陣的冪級數;K為擴散階數.前向轉移矩陣為Pf=A/rowsum(A),后向轉移矩陣為Pb=AT/rowsum(AT).研究表明雙向擴散卷積有效提高了預測模型的靈活性和有效性.

GWN模型引入自適應鄰接矩陣Aapt,可視作隱性擴散過程中的轉移矩陣,隨機初始化之后,基于隨機梯度下降原理,通過端對端的循環訓練來挖掘隱藏的空間關聯性.Aapt由兩個隨機初始化的可學習參數E1、E2組成的節點嵌入字典構成,表達式為

(4)

式中:E1為源節點嵌入參數;E2為目標節點嵌入參數.ReLU激活函數和SoftMax函數分別用于剔除不顯著關聯性的影響以及歸一化處理.

空間卷積層由機場網絡鄰接矩陣Y和自適應鄰接矩陣Aapt兩部分構成.機場網絡鄰接矩陣通過k階前向和后向擴散卷積捕獲k階空間關聯性.自適應鄰接矩陣用于捕捉網絡的隱藏空間關聯性.空間卷積層的結構見圖1,表達式為

圖1 空間卷積層結構

(5)

式中:Wk3為可學習參數矩陣.

1.3 時間卷積層

鑒于機場網絡的復雜運行特性和超長時間序列數據輸入,選擇一維擴展因果卷積作為時間卷積層.通過跳過指定的輸入步長,具備呈指數級擴大的感受野,結構示意圖見圖2.

圖2 因果卷積和擴展卷積結構

該模型用較少層數對長時序數據建模,有效緩解了梯度爆炸問題.用x∈RT表示一維序列輸入,f∈RK表示卷積核,時間窗口t上的擴展因果卷積表達式為

(6)

式中:*為卷積運算;d為擴展因子;K為卷積核的尺寸.

門控機制是時間卷積網絡的重要部分,能夠有效控制信息流從進而影響卷積效果.時間卷積網絡的門控策略為

h=g(Θ1*χ+b)⊙σ(Θ2*χ+c)

(7)

式中:χ∈RN×D×S為輸入;Θ1,Θ2,b,c為模型參數;⊙為內積運算;g(·)為激活函數;σ(·)函數控制信息進入下一層的比例.選擇正切雙曲線的tanh函數作為激活函數g(·);sigmoid函數作為衰減因子σ(·)來控制各隱含層的信息流;g(·)和σ(·)統稱為門控激活函數.

1.4 Graph WaveNet模型

圖3 Graph WaveNet模型結構

(8)

2 數據預處理與模型設置

2.1 數據預處理

選取美國年旅客吞吐量超過1000萬人次的51個民用運輸機場構建機場網絡.機場延誤數據取自聯邦航空管理局(FAA)發布的航空系統性能指標(aviation system performance metrics,ASPM).樣本數據囊括2011—2019年間3 287 d的實際機場運行信息,共167 637條.選擇機場離港航班平均準點率作為延誤指標,機場信息采集案例見表1.

表1 機場信息案例

航空公司通常每周制定航班計劃,分別統計一周內機場網絡中每個機場至其余50個機場的航班數量表示機場網絡連接關系.航空公司數據同樣源自美國聯邦航空管理局.由于同一航線的往返航班頻次存在差異,本文構建的機場網絡是有向的、非嚴格對稱的.基于機場網絡抽象出以機場為節點,航線為邊的有向圖.表征有向圖的權重鄰接矩陣表示為

(9)

式中:aij為邊的權重;fij為機場i與j間周航班頻次;fmax和fmin分別為網絡中每周航班頻次最大值和最小值;ε為控制權重矩陣分布和稀疏性的閾值.

原始數據預處理步驟如下:①將所有延誤數據聚合為以1 d為間隔形式,對缺失數據進行線性插值;②對輸入數據進行Z-score歸一化處理;③數據切片,前7年數據用于訓練,第8年數據用于驗證,第9年數據用于測試.

2.2 模型設置

所有深度學習模型都基于python 3.6版本運行,GWN模型使用Pytorch(1.1.0版本)實現,STGCN模型使用Tensorflow(1.9.0版本)實現.實驗研究采用多步預測,基于7 d歷史數據預測未來3d的機場離港航班準點率.GWN模型中,時空卷積塊的數量設置為5,隱藏層數設置為8.模型共包括10層Graph WaveNet,擴展因子分別設為1,2,1,2,1,2,1,2,1,2.式(3)即為擴散階數K=2的圖卷積層.模型使用Adam優化器進行訓練,初始學習率設定為0.02.為防止過度擬合,dropout rate設定為0.17,衰減速率設定為0.000 1.所有模型都進行50期的訓練,批次大小設定為50.

選擇4個深度神經網絡模型作為基線模型,包括門控循環單元模型(GRU)、長短時記憶網絡模型(LSTM)、堆疊式自動編碼器(SAEs)和時空圖卷積神經網絡(STGCN).其中,時空圖卷積神經網絡為實驗的主要基線模型.

2.3 評價指標

采用平均絕對誤差(MAE)、平均絕對百分比誤差(MARE)和均方根誤差(RMSE)作為預測結果評價指標.MAE、MARE和RMSE的表達式為

(10)

(11)

(12)

3 結果與分析

3.1 預測結果分析

GWN模型和四個基線模型在三個評價指標下的預測表現見表2.表中預測指標為機場網絡中所有機場預測結果的平均值.結果表明:預測第1天延誤時,GWN模型的MAE較LSTM,SAEs,GRU,STGCN分別下降12.13%,8.32%,7.73%,1.93%;預測第2天延誤時,MAE分別下降6.78%,7.25%,4.10%,2.45%;預測第3天延誤時,MAE分別下降7.47%,13.27%,6.06%,4.20%.綜合來看,GWN的預測性能在多數指標上表現最優,對未來第3天的預測精度顯著優于其它模型,表明其在多步預測上具有突出優勢.與STGCN相比,GWN對未來第1、2天的預測精度略優,對未來第3天的預測精度有顯著提升,MAPE較STGCN提高0.2%.

表2 多模型預測結果對比

圖4為五種模型的預測誤差箱型圖.由圖4可知:GWN的MAE和MAPE分布較其它模型更為集中,中位數優于大部分模型,僅MAPE中位數略高于STGCN.此外,GWN的上下四分位差IQR及預測誤差上限顯著優于其它模型,表明GWN在預測精度及穩定性上有顯著優勢.選取2019年9月1日—12月22日間歷史數據及預測結果繪制折線圖,見圖5.由圖5可知:離港航班準點率相對穩定時,各模型的預測結果接近;當準點率出現較大波動時,GWN在捕捉準點率波動峰值的表現上較STGCN更優,對數據變化趨勢更敏感.綜上,GWN預測表現優于其它基線模型,能夠有效實現航班延誤預測.

圖4 預測模型誤差箱型圖

圖5 預測結果曲線對比(第1天)

典型機場歷史數據及預測結果對比見圖6.所選機場包括檀香山國際機場(HNL)、鹽湖城國際機場(SLC)、亞特蘭大杰克遜國際機場(ATL)以及孟菲斯國際機場(MEM).HNL機場和SLC機場的MAE最小,分別為2.34%和2.64%.HNL機場預測誤差小可歸因于其地理位置遠離美國本土,與其它機場連接度較低,因而機場網絡中的延誤傳播影響被削弱.同理,位于阿拉斯加的安克雷奇國際機場的MAE也較低,為2.71%.SLC機場與HNL機場的年吞吐量相近,而該機場地處美國西部腹地,與機場網絡連接度更高,因此延誤波動更顯著.ATL機場年吞吐量超1.1億人·次,旅客中轉率超過70%,網絡連接度和重要度較高.ATL機場的MAE分別為4.81%,與整體MAE相近,表明GWN對大型樞紐機場同樣具有穩定的預測表現.由圖6可知:GWN能夠準確預測準點率的波動趨勢,然而對波峰波谷的預測精度有待提升.MEM機場MAE最大,達到10.91%,其本身是美國最大的貨運樞紐機場,也是聯邦快遞的總部.MEM機場的離港航班準點率波動顯著,同時航空貨運對機場準點率影響較大,本文僅選取客運航班數據,導致預測誤差較大.

圖6 典型機場GWN預測結果

GWN預測結果的正負誤差分布見圖7.51個機場中,29個機場的負誤差天數多于正誤差天數.正誤差天數主要集中在160～180 d,而負誤差天數主要集中于180～200 d.由此可見,GWN傾向于低估機場的離港航班準點率.結合預測曲線分析,GWN在機場出現嚴重延誤時預測誤差較大,導致負誤差天數整體偏高.

圖7 GWN模型正負誤差統計

3.2 靈敏度與鄰接矩陣分析

實驗對三個模型參數作靈敏度分析,包括最大擴散階數K、時空卷積塊數B以及隱藏層數H.實驗中,隨著擴散階數K的增加,模型預測誤差也逐步增大.當K設置較小時,卷積過程能夠提取更多信息,同時也會造成計算工作量激增、過擬合等問題.實驗結果表明,在K=2,B=5,H=8時,模型預測表現最佳.

實驗對比5種鄰接矩陣來驗證空間卷積層構造的優越性.5種鄰接矩陣構造對未來3天預測表現見圖8.Identity、Forward、Apt、Bidir、Bidir_Apt分別為單位矩陣、基于預設權重矩陣作前向卷積、自適應鄰接矩陣、基于預設權重矩陣作雙向卷積以及融合雙向卷積和自適應鄰接矩陣.由圖8可知:僅采用自適應矩陣的預測結果優于單向卷積,表明其能夠有效挖掘隱藏的空間關聯性.融合雙向卷積與自適應鄰接矩陣的空間卷積層預測表現最優,表明雙向卷積矩陣能有效捕捉顯性空間關聯性,自適應鄰接矩陣挖掘隱藏空間關聯性,綜合提高預測精度.

圖8 鄰接矩陣預測結果對比

4 結 束 語

文中提出一種基于深度Graph WaveNet的機場網絡延誤預測模型.GWN模型對機場網絡整體建模,融合時間和空間卷積神經網絡對網絡中所有機場進行多步延誤預測.時間卷積層中引入擴展因果卷積及門控機制,大幅縮短訓練時間,有效解決梯度爆炸等問題,提升模型訓練效率.其次,采用圖卷積網絡處理圖結構化的機場網絡延誤數據,通過雙向卷積和自適應鄰接矩陣捕捉航班延誤傳播的顯性和隱性空間關聯性.結果表明:GWN模型的預測精度較其它基線模型有顯著提升,在多步預測上具有突出優勢,且對不同吞吐量級機場均有優越穩定的預測表現.