基于動態(tài)貝葉斯網(wǎng)的航班延誤傳遞分析

丁建立，趙鍵濤＋，曹衛(wèi)東，胡海生，黃 威

（1.中國民航大學 計算機科學與技術學院，天津300300；2.中國民航信息網(wǎng)絡股份有限公司，北京100010）

0 引 言

航班鏈中的各個航班發(fā)生延誤受到的影響因素是多方面的，對于單個航班在知道上游航班延誤的情況下，很難對下游航班進行預測。然而，可以針對大多數(shù)航班鏈中的延誤傳遞情況進行分析，從中發(fā)現(xiàn)多數(shù)情況下延誤傳遞的普遍規(guī)律，這無疑也具有重要現(xiàn)實意義。

在國外，學者針對航班延誤，從不同角度進行了研究。Pyrgiotis等用排隊論的思想建立了一個機場網(wǎng)絡模型對航班延誤進行研究，指出了在機場網(wǎng)絡模型中考慮延誤傳播的重要性［1］；Barnhart等針對乘客到達延誤，采用了一種自適應的啟發(fā)式方法來估計旅客到達延誤的影響，同時研究了影響航空系統(tǒng)正常運行的主要因素［2］；Hao等研究了某幾個機場的延誤給整個機場網(wǎng)絡帶來影響，得出部分機場的延誤狀況不能夠?qū)φ麄€航空系統(tǒng)的延誤狀況進行估計的結(jié)論［3］；AhmadBeygi等研究了航班計劃與航班延誤的關系，指出了在當前狀況下即使航班計劃預留出松弛時間用于吸收延誤，在上游的航班發(fā)生延誤的條件下，延誤依然會向下游航班傳播［4］，但是可以采取增加航班在機場的周轉(zhuǎn)時間的方式來減少延誤向下游機場的傳遞［5］；Song等從機場容量的角度出發(fā)，研究了天氣對機場容量的影響［6］；Laskey等用靜態(tài)貝葉斯網(wǎng)對各種影響因素及航班延誤之間的關系進行了建模［7］，但是沒有考慮到飛機在機場周轉(zhuǎn)時間等因素。

在國內(nèi)，應圣鋼等運用優(yōu)化方法，研究了如何對飛機進行合理化調(diào)度，以減小潛在損失［8，9］，但沒有涉及如何進行預測；丁建立、徐濤等采用生物免疫、支持向量機、馬爾科夫鏈等方法對機場航班延誤數(shù)量進行預測［10－13］，但沒有涉及航班鏈中延誤的傳播性。曹衛(wèi)東、劉玉潔等用靜態(tài)貝葉斯網(wǎng)絡的方法對航班延誤傳播進行了分析，但沒有考慮到計劃過站時間的因素及網(wǎng)絡參數(shù)學習問題［13，14］。

本文針對航班延誤傳遞的特點，采用動態(tài)貝葉斯網(wǎng)對航班鏈上的航班延誤傳遞狀況進行分析，研究了過站時間對延誤傳播的影響，并對延誤傳遞過程中延誤時間的不確定性進行了度量，比較了延誤傳遞各個過程中的不確定大小。

1 航班延誤傳遞模型

航空公司為了提高飛機利用率，通常會安排一架飛機在一天之內(nèi)執(zhí)行多個航班，當上游航班發(fā)生延誤時，延誤有可能會向下游傳播。若一個航班鏈中有p 個航班，每個航班離港延誤時間為Ti，i＝1，2，…，p，則下一航班離港延誤時間與上一航班離港延誤時間有關系，而與上一航班之前的航班離港延誤時間沒有關系，具有一階馬爾可夫性。離港延誤時間的傳遞關系如圖1所示。

圖1 航班延誤傳遞

將延誤時間離散化，設ti表示延誤時間為第i 個狀態(tài)，第p 個航班離港延誤時間為ti的概率為P（Tp＝ti），運用消元法

由于下一段航班離港延誤時間與上一段航班有關系，具有馬爾可夫性，所以

而這個關系正好可以用動態(tài)貝葉斯網(wǎng)來表達。

2 航班延誤傳遞的動態(tài)貝葉斯網(wǎng)絡

動態(tài)貝葉斯網(wǎng)絡以概率論為基礎，是一種把靜態(tài)貝葉斯網(wǎng)絡與時間信息結(jié)合，能夠表達時序數(shù)據(jù)的隨機模型。動態(tài)貝葉斯網(wǎng)絡的可以看成是隨機過程的圖形模式［16］。

動態(tài)貝葉斯網(wǎng)（DBN）可以定義為（B0，B→），其中B0是先驗網(wǎng)絡，定義在初始狀態(tài)上的聯(lián)合概率分布，B→是轉(zhuǎn)移網(wǎng)。設X［t］表示t時刻隨機變量的取值，定義轉(zhuǎn)移概率P（X［t＋1］／X［t］）。在時刻1，X［1］中的父節(jié)點是在先驗網(wǎng)絡B0中的節(jié)點，在時刻t＋1，X［t＋1］的父節(jié)點是那些在t時刻和t＋1中都相關的在B→中的節(jié)點。動態(tài)貝葉斯網(wǎng)假設動態(tài)概率過程是馬氏的，即

也就是說t＋1時刻的取值情況只與t時刻的取值情況有關，而與t時刻之前的取值情況無關。若相鄰時間的條件概率過程是平穩(wěn)的，那么P（X［t＋1］／X［t］）與時間t無關。對于一個DBN 模型，在X［0］，X［0］，…，X［t］上的聯(lián)合概率分布為

針對航班離港延誤傳遞，對離港延誤時間有影響的因素除了有上一航班的離港延誤時間外，還有飛機在下一機場的計劃過站時間。在上一航班離港延誤時間確定的條件下，飛機在下一機場計劃過站時間越長，相當于緩沖時間越多，下一航班離港延誤的可能性就越小。因此，航班延誤傳遞可以表示為在一個時間片中包含兩個節(jié)點的動態(tài)貝葉斯網(wǎng)絡，其中一個節(jié)點表示計劃過站時間，另外一個節(jié)點表示離港延誤時間。航班延誤傳遞的動態(tài)貝葉斯網(wǎng)絡如圖2所示。靜態(tài)貝葉斯網(wǎng)是一個有向無環(huán)圖，弧的方向代表因果指向，而在動態(tài)貝葉斯網(wǎng)中為了表示的方便，允許環(huán)存在。但是，存在的環(huán)不僅代表因果關系，還意味著代表的因果關系能進行時間上的擴展。例如把圖2代表的動態(tài)貝葉斯網(wǎng)進行擴展，擴展時間片為4，展開形式如圖3所示。

圖2 航班延誤傳遞的動態(tài)貝葉斯網(wǎng)絡

3 航班延誤傳遞動態(tài)貝葉斯網(wǎng)絡參數(shù)學習

動態(tài)貝葉斯網(wǎng)絡學習包括了結(jié)構學習與參數(shù)學習。在對航班延誤傳遞進行研究時，采用的是采取經(jīng)驗確定動態(tài)貝葉斯網(wǎng)結(jié)構，然后再根據(jù)確定了的結(jié)構學習參數(shù)的方法。EM 方法和梯度方法是動態(tài)貝葉斯網(wǎng)在不完整數(shù)據(jù)集上學習參數(shù)的兩種方法。

圖3 包含4個時間片的動態(tài)貝葉斯網(wǎng)絡

3.1 EM 方法

在完整數(shù)據(jù)集中用統(tǒng)計方法對參數(shù)進行估計時，每個樣本的權重為1。而在運用含有缺失數(shù)據(jù)的數(shù)據(jù)集對參數(shù)進行學習時，EM 方法基于當前參數(shù)對缺失數(shù)據(jù)集進行修補。一個缺值樣本經(jīng)過修補之后權重不再是1，而是對每一種修補情況都附加一個權重。在進行數(shù)據(jù)修補后，計算當前樣本集的最大似然參數(shù)估計，然后基于新的參數(shù)估計值計算似然函數(shù)值。若似然函數(shù)值增大，則基于新的參數(shù)估計值重新修補缺失數(shù)據(jù)，否則以當前參數(shù)值作為最終的參數(shù)估計值。

其中，P（Xl＝xl／Dl，）為以Xl＝xl方式修補樣本的權重。當Xl＝ 時，樣本是完整的，P（Xl＝xl／Dl）＝1。當對數(shù)似然函數(shù)取得最大值時

以此作為下一次迭代的參數(shù)，其中，mtijk是修補后數(shù)據(jù)Dt中所有滿足Xi＝k，π（Xi）＝j的樣本權重之和，ri為節(jié)點Xi的取值個數(shù)

EM 算法步驟見表1。

3.2 梯度方法

同神經(jīng)網(wǎng)絡使用梯度下降的方式尋找節(jié)點間連接權重的方法類似，動態(tài)貝葉斯網(wǎng)參數(shù)估計選擇也可以采用梯度優(yōu)化的方法來尋找參數(shù)。與神經(jīng)網(wǎng)絡以誤差最小化作為優(yōu)化準則不同，貝葉斯網(wǎng)以似然函數(shù)最大化作為優(yōu)化準則。神經(jīng)網(wǎng)絡中經(jīng)過迭代之后收斂到誤差曲面的一個局部最小值，而貝葉斯網(wǎng)絡中經(jīng)過迭代之后將收斂到似然函數(shù)曲面的一個局部最大值。給定D ＝（D1，D2，…，Dm）為一組獨立同分布數(shù)據(jù)集，給定動態(tài)貝葉斯網(wǎng)結(jié)構，參數(shù)的對數(shù)似然為

表1 EM 算法步驟

對參數(shù)求偏導

用梯度上升來更新每一個θijk，即

其中，η是學習率。然后再將θijk′歸一化

計算似然當前參數(shù)下的似然函數(shù)值，若似然函數(shù)值變大，則更新參數(shù)值，否則不更新。這樣經(jīng)過迭代之后，將得到參數(shù)的一個局部最大似然假設。

梯度法步驟見表2。

表2 梯度法步驟

3.3 參數(shù)學習比較

下面對兩種參數(shù)學習方法進行比較，用其中比較好的方法作為航班延誤傳遞分析動態(tài)貝葉斯網(wǎng)的參數(shù)學習方法，其中梯度法η設置為0.02。實驗中采用的數(shù)據(jù)是國內(nèi)某大型航空公司在某省的航班數(shù)據(jù)。數(shù)據(jù)預處理后共有3800條數(shù)據(jù)。圖4所示為兩種方法的學習曲線。

圖4 航班延誤傳遞動態(tài)貝葉斯網(wǎng)絡參數(shù)學習曲線

似然度越大，即負的對數(shù)似然值越小，說明得到的參數(shù)越符合訓練數(shù)據(jù)。從圖4 中可以看到，在計算參數(shù)時，EM 方法在收斂速度和對樣本數(shù)據(jù)的擬合能力上，均比梯度方法效果好。

4 基于動態(tài)貝葉斯網(wǎng)EM 參數(shù)學習方法的航班延誤傳遞分析

首次航班的計劃過站時間為首發(fā)計劃起飛時間減去上一天最后一個航班的計劃降落時間，由于首次航班的延誤時間不考慮過站時間的影響，因此在展開后的動態(tài)貝葉斯網(wǎng)中去掉了指向首次航班離港時間的過站時間節(jié)點。訓練后結(jié)果如圖5所示。

圖5 基于EM 參數(shù)學習方法的航班延誤傳遞學習結(jié)果

表3和表4為部分情況下的轉(zhuǎn)移概率。對比兩個表可以發(fā)現(xiàn)，相同條件下的轉(zhuǎn)移概率并不相等，其它條件下也有類似的情況，說明航班延誤傳遞是一個非穩(wěn)態(tài)過程。

在航班實際執(zhí)行之前，航班計劃是已知的，所以飛機在各個機場的計劃過站時間也是已知的。因此，在上游航班延誤狀況已知的前提下，根據(jù)動態(tài)貝葉斯網(wǎng)學習結(jié)果，可以得出后續(xù)航班的離港延誤時間的概率分布。圖6所示為首發(fā)航班時延誤時間為30～40分鐘，后續(xù)航班的計劃過站時間都為40～50分鐘時，后續(xù)航班離港延誤時間的概率分布。圖7所示為首發(fā)航班時延誤時間為30～40分鐘，后續(xù)航班的計劃過站時間都為70～80分鐘時，后續(xù)航班離港延誤時間的概率分布。

表3 離港延誤時間 ［1］轉(zhuǎn)移概率

表4 離港延誤時間 ［2］轉(zhuǎn)移概率

圖6 航班離港延誤時間概率分布1

圖7 航班離港延誤時間概率分布2

對比圖6和圖7可以看到，當上游航班發(fā)生離港延誤時，若下游航班過站時間充分，大多數(shù)情況下延誤是可以被逐漸吸收的。其它條件下也有類似的情況。為了度量各時間片中離港延誤時間的不確定性，計算各離港延誤時間的熵值，熵的定義如下

式中：P（xi）——狀態(tài)xi出現(xiàn)的概率，n——狀態(tài)個數(shù)。以變量X1，X2，X3分別代表各個時間片中的離港延誤時間，按10分鐘為一個狀態(tài)，由公式計算上述兩種不同條件下各時間片中離港延誤時間的熵值，結(jié)果見表5。

表5 不同情況下離港延誤時間熵值

分析數(shù)據(jù)可以看出，上述兩種情況下，在航班離港延誤時間傳遞的過程中，隨著時間片的遞增，離港延誤時間的熵是在不斷增大的，即不確定性是在逐漸增大的，預測準確的可能性是在逐漸降低的。在其它條件下也有類似的情況。

5 結(jié)束語

本文用動態(tài)貝葉斯網(wǎng)對航班延誤傳遞進行研究，并對典型的動態(tài)貝葉斯網(wǎng)參數(shù)學習的效果進行了比較，對其中較好的學習結(jié)果進行了分析。分析結(jié)果表明，若過站時間充分，在大部分情況下，航班延誤在傳遞的過程中是可以被逐段吸收的。另外，隨著航班延誤動態(tài)貝葉斯網(wǎng)時間片的增加，離港延誤時間的不確定性逐漸增大的，預測準確的可能性是逐漸減小的。

［1］Pyrgiotis N，Malone K M，Odoni A.Modelling delay propagation within an airport network ［J］.Transportation Research Part C：Emerging Technologies，2013，27：60－75.

［2］Barnhart C，F(xiàn)earing D，Vaze V.Modeling passenger travel and delays in the national air transportation system ［J］.Operations Research，2014，62 （3）：580－601.

［3］Hao L，Hansen M，Zhang Y，et al.New York，New York：Two ways of estimating the delay impact of New York airports［J］.Transportation Research Part E：Logistics and Transportation Review，2014，70：245－260.

［4］AhmadBeygi S，Cohn A，Guan Y，et al.Analysis of the potential for delay propagation in passenger airline networks［J］.Journal of Air Transport Management，2008，14 （5）：221－236.

［5］Ahmadbeygi S，Cohn A，Lapp M.Decreasing airline delay propagation by re－allocating scheduled slack ［J］.IIE Transactions，2010，42 （7）：478－489.

［6］Lixia S，Craig W，Daniel G，et al.Methodologies for estimating the impact of severe weather on airspace capacity ［C］／／The 26th Congress of International Council of the Aeronautical Sciences，2008：1－8.

［7］Laskey K B，Xu N，Chen C H.Propagation of delays in the national airspace system ［C］／／Proceedings of the Twenty－Second Conference on Uncertainty in Artificial Intelligence，2012.

［8］YING Shenggang，SUN Fuchun，HU Laihong，et al.Multiobjective dynamic programming algorithm for aircraft arrival sequencing and runway scheduling ［J］.Control Theory ＆Applications，2010，27 （7）：827－835 （in Chinese）. ［應圣鋼，孫富春，胡來紅，等.基于多目標動態(tài)規(guī)劃的多跑道進港排序［J］.控制理論與應用，2010，27 （7）：827－835.］

［9］LI Xiaolan，LE Meilong.Heuristic algorithm in stages of multi－objective aircraft and passenger recovery ［J］.Application Research of Computers，2014，31 （8）：2270－2274 （in Chinese）.［李曉嵐，樂美龍.多目標飛機和旅客恢復分階段啟發(fā)式算法 ［J］.計算機應用研究，2014，31 （8）：2270－2274.］

［10］DING Jianli，YANG Haitong，GU Bin.Adaptive real－time forecasting method of airdrome flight delay based on fuzzy immunization strategy ［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2011，43 （2）：257－261 （in Chinese）.［丁建立，楊海彤，顧彬.基于模糊免疫策略的機場航班延誤自適應實時預測方法 ［J］.南京航空航天大學學報，2011，43 （2）：257－261.］

［11］DING Jianli，TONG Guansheng，XU Tao.Detecting and implementing of airport scheduled flight delay state base on immune negative selection algorithm ［J］.Chinese High Technology Letters，2008，18 （4）：387－391 （in Chinese）. ［丁建立，仝冠生，徐濤.基于免疫否定選擇算法的機場航班延誤狀態(tài)檢測與實現(xiàn)［J］.高技術通訊，2008，18 （4）：387－391.］

［12］XU Tao，DING Jianli，GU Bin，et al.Forecast warning level of flight delays based on incremental ranking support vector machine ［J］.Acta Aeronautica Et Astronautica Sinica，2009，30 （7）：1256－1263 （in Chinese）. ［徐濤，丁建立，顧彬，等.基于增量式排列支持向量機的機場航班延誤預警［J］.航空學報，2009，30 （7）：1256－1263.］

［13］LV Xiaojie，WANG Hong.Method for swept flight delay early warning of large aeronautic hub ［J］.Computer Engineering and Design，2011，32 （8）：2829－2832 （in Chinese）.［呂曉杰，王紅.大型樞紐機場大面積航班延誤預警方法研究 ［J］.計算機工程與設計，2011，32 （8）：2829－2832.］

［14］CAO Weidong，HE Guoguang.Bayesian networks analysis for sequence flight delay and propagation ［J］.Journal of Computer Applications.2009，29 （2）：606－610 （in Chinese）.［曹衛(wèi)東，賀國光.連續(xù)航班延誤與波及的貝葉斯網(wǎng)絡分析 ［J］.計算機應用，2009，29 （2）：606－610.］

［15］LIU Yujie.Flight delay transmit forecast based on Bayesian network ［D］.Tianjin：Tientsin University，2009 （in Chinese）. ［劉玉潔.基于貝葉斯網(wǎng)絡的航班延誤與波及預測［D］.天津：天津大學，2009.］

［16］REN Jia，GAO Xiaoguang.Bayesian network parameter learning and decision support for UAVs ［M］.Beijing：National Defence Industry Publisher，2012：70－100 （in Chinese）.［任佳，高曉光.貝葉斯網(wǎng)絡參數(shù)學習及對無人機的決策支持 ［M］.北京：國防工業(yè)出版社，2012：70－100.］