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

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

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

0 引 言

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

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

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

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

1 航班延誤傳遞模型

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

圖1 航班延誤傳遞

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

由于下一段航班離港延誤時(shí)間與上一段航班有關(guān)系，具有馬爾可夫性，所以

而這個(gè)關(guān)系正好可以用動(dòng)態(tài)貝葉斯網(wǎng)來表達(dá)。

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

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

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

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

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

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

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

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

圖3 包含4個(gè)時(shí)間片的動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)

3.1 EM 方法

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

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

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

EM 算法步驟見表1。

3.2 梯度方法

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

表1 EM 算法步驟

對參數(shù)求偏導(dǎo)

用梯度上升來更新每一個(gè)θijk，即

其中，η是學(xué)習(xí)率。然后再將θijk′歸一化

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

梯度法步驟見表2。

表2 梯度法步驟

3.3 參數(shù)學(xué)習(xí)比較

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

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

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

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

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

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

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

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

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

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

圖6 航班離港延誤時(shí)間概率分布1

圖7 航班離港延誤時(shí)間概率分布2

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

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

表5 不同情況下離港延誤時(shí)間熵值

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

5 結(jié)束語

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

［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）. ［應(yīng)圣鋼，孫富春，胡來紅，等.基于多目標(biāo)動(dòng)態(tài)規(guī)劃的多跑道進(jìn)港排序［J］.控制理論與應(yīng)用，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）.［李曉嵐，樂美龍.多目標(biāo)飛機(jī)和旅客恢復(fù)分階段啟發(fā)式算法 ［J］.計(jì)算機(jī)應(yīng)用研究，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ī)場航班延誤自適應(yīng)實(shí)時(shí)預(yù)測方法 ［J］.南京航空航天大學(xué)學(xué)報(bào)，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）. ［丁建立，仝冠生，徐濤.基于免疫否定選擇算法的機(jī)場航班延誤狀態(tài)檢測與實(shí)現(xiàn)［J］.高技術(shù)通訊，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ī)的機(jī)場航班延誤預(yù)警［J］.航空學(xué)報(bào)，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ī)場大面積航班延誤預(yù)警方法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(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)絡(luò)分析 ［J］.計(jì)算機(jī)應(yīng)用，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)絡(luò)的航班延誤與波及預(yù)測［D］.天津：天津大學(xué)，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)絡(luò)參數(shù)學(xué)習(xí)及對無人機(jī)的決策支持 ［M］.北京：國防工業(yè)出版社，2012：70－100.］