孟會芳，彭 怡（南京航空航天大學民航運輸優(yōu)化實驗室，211100南京）

一種兩階段的航班延誤模式提取方法

孟會芳，彭 怡
（南京航空航天大學民航運輸優(yōu)化實驗室，211100南京）

針對民航運輸系統日益嚴重的航班延誤問題，提出一種兩階段的航班延誤模式提取方法.該方法運用相空間重構理論和遞歸圖方法，對航班延誤率的混沌特性進行分析.然后，在獲取延誤率子序列的基礎上，結合定量遞歸分析理論，采用K?means聚類技術提取航班延誤模式，并對各種延誤模式進行時變分析.實例驗證表明，該方法不但能有效地提取航班延誤模式，而且可以獲取延誤模式的時變特征，研究成果對機場和航空公司航班延誤預測及預警提供了管理決策依據.

航班延誤；相空間重構；混沌性；定量遞歸分析；延誤模式；時變特征

航班延誤是民航界亟待解決的重要問題，國內外專家學者對航班延誤做過大量的分析研究.文獻［1］設計了航班計劃恢復決策支持系統，在航班已經發(fā)生延誤的情況下，以延誤航班和取消航班架次最少為目標，搜索所有可用飛機和機組資源，恢復被擾亂的航班計劃；文獻［2］以飛機和旅客的恢復成本、取消成本、延誤成本最小化為目標函數，建立了飛機和旅客一體化恢復模型；文獻［3］將風險比例模型運用到航班延誤波及的研究中，從航班運行機制角度入手，對航班延誤因素進行分析，指出過站時間、機型、行李貨郵、維修計劃、旅客和行李處理、天氣是造成離港航班延誤的主要因素；文獻［4］建立了基于貝葉斯網絡的航班延誤因素分析模型，探究了不同因素對航班延誤的影響程度；文獻［5］通過對空中油耗可信度進行分析指出，采取降低巡航高度、修改最佳飛行高度及減小巡航速度等手段可以有效減少地面延誤.這些研究成果主要集中在對航班延誤原因的梳理和延誤后的恢復機制方面，屬于事后處理機制的范疇，是航班延誤發(fā)生后的資源調整和控制，是被動的管理策略.當然，也有部分學者［6－7］提出對航班延誤狀態(tài)評估及延誤預警的方案，但也都是主要研究一段時間內總的航班延誤數量及延誤等級或是以概率性事件預測延誤的可能性，對航班延誤發(fā)生之前的模式規(guī)律研究鮮有涉及.鑒于此，本文在上述研究的基礎上，著力對航班延誤模式進行分析.基于延誤率的變化規(guī)律，運用非線性動力學理論構建了一種定性和定量相結合的航班延誤模式提取方法.

該方法分為2個階段，如圖1所示.

1）定性分析.基于混沌理論對航班延誤率的時間序列進行相空間重構，將重構后的相空間運用到遞歸圖分析（recurrence plot，RP），驗證航班延誤率時間序列的混沌特性.

2）定量分析.在定性分析研究的基礎上，結合CUSUM算法將時間序列劃分為不等長的子序列，然后對每個子序列進行定量遞歸分析（recurrence quantification analysis，RQA），提取特征參數.運用K?means方法獲取航班延誤模式，對每種延誤模式在一周內每一天的分布情況加以分析.

圖1 航班延誤模式提取方法技術路線

1 航班延誤率時間序列混沌特性分析

時間序列的混沌特性分析都是在特定的相空間內進行的，因此，分析航班延誤特征的第1步是進行有效的相空間重構，而遞歸圖則直觀地反映了系統的混沌特性.在航空運輸系統中，航班延誤是由多種原因（機場、航空公司、空管、天氣等）造成的綜合結果，而一般情況下研究人員關注的重點往往只是最終的延誤水平.因此，本文一個最基本的想法是認為所有觀察到的以及未被發(fā)現的影響因素造成的后果都可以通過最終延誤水平這一變量反映出來，即選取平均航班延誤率作為所要考察的時間序列.根據文獻［8］的延遲嵌入定理可知，只要選取合適的延遲時間τ和嵌入維數m，將一維變量投影到高維空間，原系統暗含的動力特征將得以重現.假設原始平均航班延誤率時間序列為X＝｛xi，i＝1，…，N｝，重構相空間后得到一個（N－（m－1）τ）×m的矩陣Y，其中Yi＝(xi，xi－τ，…，xi－（m－1）τ)，i＝（m－1）τ+1，…，N.Yi為航空運輸系統在i時刻的航班延誤狀態(tài)，是m維嵌入空間中的一個相點.

1.1 相關參數的確定

文獻［9］中介紹了多種確定最優(yōu)時間延遲τ和最佳嵌入維數m的方法，為了在Rm空間中充分刻畫出原模型的性質，綜合考慮各種方法的優(yōu)缺點，本文采用文獻［10－11］提出的平均互信息法確定最佳延遲時間τ，用Frase提出的虛假最近鄰算法（FNN）確定嵌入維數m.

1.1.1 延遲時間τ的確定

式中：P(xi)、P(xi+τ)、P(xi，xi+τ)分別為概率；P(xi)、P(xi+τ)可以通過計算時間序列的直方圖獲得；P(xi，xi+τ)可以通過計算時間序列的二維直方圖獲得.選取I(τ)第1次達到局部極小值時的τ為最優(yōu)延遲時間，因為此時觀測時間序列具有最大的獨立性和最小的冗余.

1.1.2 嵌入維數m的確定

虛假最近鄰點是指當嵌入維數較小時吸引子在相空間中不能完全打開而投影到一起，但是原系統中這兩點并不是真正的近鄰點.判定虛假最近鄰為

給定一個閾值R，若a(i，d)＞R，則xNN（i）是x（i）的

1虛假最近鄰點，R∈［10，50］.當m增加到m+1維，虛假最近鄰點的比例小于5%或者不再隨著m的增加而減小時，可以認為混沌吸引子完全打開，此時的m就是最佳嵌入維數.

1.2 航班延誤率時間序列遞歸圖

文獻［12］提出遞歸圖（RP）的概念，旨在以圖形的方式定性地展示動力系統的混沌性、非平穩(wěn)性及周期性等遞歸特性.遞歸圖的構建以相空間重構為基礎的，利用相空間的點得到一個描述時間序列內部動力學特性的二維矩陣圖，其實質則是由0和1組成的N階方陣［12］，如

式中：ε為鄰域半徑，是一個預先給定的閥值，一般取時間序列標準差的15%，Θ（·）為Heavside函數，即

令dij＝‖Yi－Yj‖，dij為狀態(tài)向量Yi與Yj距離遠近的度量.

在周期性時間序列中當i－j ＝nT（n＝0，1，…，T）時，dij＝0，而非周期性時間序列沒有這樣的性質.所以，為直觀反映重構后所有狀態(tài)向量兩兩之間的距離，規(guī)定當dij≤ε時認為兩向量靠近，兩相點遞歸，在點（i，j）處顯示黑點，即j時刻相空間中的1點在i時刻返回到它所在的相空間鄰域中；否則認為兩向量相距較遠，兩相點非遞歸，在（i，j）處顯示白點.也就是說在航班延誤系統中，利用航班延誤率構建遞歸圖，比較重構后兩相點Yi和Yj的距離，若dij大于規(guī)定值，則畫一個黑點，表示i時刻與j時刻的狀態(tài)具有遞歸性；否則畫一個白點，表示i時刻與j時刻的狀態(tài)相互獨立，從而得到一個具有特定圖樣結構的矩陣圖.若遞歸圖中的顏色分布具有一定的規(guī)律性，說明航班延誤系統中存在確定性成分，具有一定的混沌特性，該系統的可預測性強；否則該系統的隨機性較強，難以預知.

2 航班延誤模式提取

航班延誤模式提取方法主要是根據航班延誤率時間序列的變化特點，利用CUSUM算法分割子序列，運用RQA提取出各個子序列的特征參數作為K?means聚類的輸入指標提取出典型的航班延誤模式.

2.1 CUSUM算法分割航班延誤率子序列

人為等時段劃分序列間隔忽略了數據本身的變化特性，是一種生硬的分割方法.為了克服對序列波動過程和統計特征造成破壞，本文根據序列內部變化特性進行自然劃分，通過對樣本序列數據信息的積累，采用CUSUM算法對時間序列進行分割，將小的偏移放大，達到提高檢測數據偏移靈敏度、探測數據序列發(fā)生改變的拐點的目的［13］.算法步驟如下：

1）設置最小分割長度閾值λ，計算航班延誤率時間序列均值x－；＝+

2）計算各點航班延誤率累計和SiSi－1（x，其中i＝1，…，n，取初值S0＝0；

4）對每個子序列基于拐點進行二分，反復進行步驟3）；

5）當每個子序列的長度都小于λ時，算法停止.

2.2 基于RQA的航班延誤率子序列特征參數提取

雖然RP可以直觀地對系統進行定性分析，但是很多情況下人們希望對系統進行量化分析.為了更準確的描述和區(qū)分時間序列的內在規(guī)律，量化遞歸圖的指標受到越來越多學者的重視.文獻［14］提出利用遞歸度、確定性、最長對角線因子、遞歸熵、趨勢5個指標量化遞歸圖中的狀態(tài)點和線段的分布.隨后，文獻［15］又引入了遞歸趨勢、分歧度、分層度、平均對角線長度等量化指標，從而形成了系統的定量遞歸分析方法.不同的RQA指標描述了系統不同的動力學行為，反映了航班延誤率的遞歸特性［16］.考慮到航班延誤的實際情況，本文選取5個常用的非線性指標量化參數.

1）遞歸率（RR）.表示遞歸圖中所有遞歸點（黑點）占全部點數的百分比，也就是當前狀態(tài)遞歸和復顯的可能性，遞歸率越大系統的周期性越強.

2）確定率（DET）.表示所有與主對角線（45°）平行的線段上遞歸點占所有遞歸點的比值，是數據結構確定性的指標，值越大表明系統確定性越強.在周期性時間序列中，有序規(guī)則的線段遞歸點多，DET都大于0；而隨機時間序列中，離散孤立的遞歸點多、對角線少，DET趨近于0.

式中：P（l）表示長度為l的對角線的分布概率，lmin一般取2或3.

3）遞歸熵（ENTR）.刻畫遞歸圖中平行于主對角線的線段的Shannon熵，是數據結構復雜度的指標，值越大表明系統結構越復雜.

4）最長對角線因子（Lmax）.平行于主對角線（不包括主對角線）的所有線段的最大值，表示數據序列非線性特征的指標，值越小非線性越強，混沌性越強越不平穩(wěn).

5）分層度（LAM）.指組成規(guī)則線段（垂直／水平）的遞歸點的百分比，描述系統變化快慢，值越小變化越快.

式中：P（v）為長度為v的線段（水平／垂直）分布概率；vmin為最短線段長度，一般取2或3.

3 實例分析

本文實驗數據來源于國內某大型樞紐機場航班實際生產運行數據，選取2013年11月4日至2013年11月10日一個典型周的數據，由于航班計劃是以5 min為間隔制定的，所以數據統計間隔最小為5 min，分5、10、15 min記錄航班延誤率.

3.1 不同時間尺度的航班延誤率時間序列相空間重構及RP分析

圖2是利用平均互信息法和FNN方法得到的不同時間尺度的延遲時間和嵌入維數，從左到右依次是5、10、15 min.從圖2中可以看出3個時間尺度的延遲時間分別在3、4、3處達到極小，即15、40、45 min，所以最優(yōu)延遲時間為3、4、3；嵌入維數均在2時使虛假最近鄰點趨于穩(wěn)定，所以最佳嵌入維數均取2.

圖2 不同統計時間尺度的延遲時間和嵌入維數

若系統內部隱含某種規(guī)律，那么在遞歸圖中的具體表現形式就是圖形內部線條呈現某種特定形狀.圖3是利用RQA的航班延誤率子序列特征參數提取的方法構建的3種統計間隔的航班延誤率時間序列遞歸圖，從左到右依次是5、10、15 min，3幅圖形均由特定結構的規(guī)則線段和黑點組成，可以看出第1幅圖的黑色規(guī)則線條分布比較均勻，而第2、3幅圖形中規(guī)則線條減少，具有隨機特性的黑點增多，說明每種統計間隔的遞歸圖都呈現出一定的規(guī)律性，并且隨著統計時間間隔的增大規(guī)律性減小，也就是說采用較短的統計間隔能夠減少延誤率時間序列的隨機性，增強周期性，因此以下分析均采用5 min統計間隔的航班延誤率時間序列.

圖3 不同統計時間尺度的航班延誤率遞歸圖

3.2 航班延誤模式提取

由于間隔太短的子序列無法保證遞歸矩陣的有效性，而間隔太長的子序列又會導致一部分延誤率模式變化被平滑忽略，因此，結合數據采樣頻率，經多次試驗判斷，間隔長度取閾值為18，即子序列的最大分割長度不能超過1.5 h.在Matlab7.9平臺上實現了CUSUM算法，分割后共得到173條子序列.對這些子序列進行RQA，利用航班延誤模式提取的方法，計算每個子序列的遞歸參數.同時，考慮到不同時段航班延誤率的大小及子序列的波動水平，將描述子序列統計參數的均值和標準差引入進來，總共7個特征參數作為聚類的輸入矢量.航班延誤沒有既定的模式分類，而模式提取的目的是為航班延誤預測和延誤狀態(tài)評估提供先驗知識，聚類個數太多會導致預測難度增加，太少會掩蓋一些模式.因此，為了合理、科學地提取航班延誤模式，根據文獻［17］將延誤劃分為1、2、3、4個等級，結合該樞紐機場實際生產運行規(guī)定的藍、黃、橙、紅4個延誤等級標準和民航局關于印發(fā)《民航航班正常統計辦法》的通知取k＝4.表1描述的是4種航班延誤模式的聚類中心參數值以及每種模式在復顯性以及統計特性等方面的特征.

表1 航班延誤模式參數及統計特征

圖4描述的是類中心參數歸一化后的4種模式分布.模式4對應暢通狀態(tài)，此時延誤率均值最小，該模式中子序列的波動也最小，狀態(tài)比較平穩(wěn)，對應著航班起降較少的凌晨時段，5個遞歸參數均是4種模式中最大的，統計特征主要表現為具有復雜的確定性結構、復顯性明顯、具有一定的周期性，是一個較平穩(wěn)的過程并且該模式下的系統狀態(tài)變化較慢.暢通流在每天出現的時段基本相同，這與后面的時變分析是一致的.模式2對應輕度延誤狀態(tài)，主要出現在早高峰開始之前的時段，此時延誤率較大，波動最大，遞歸參數是4種模式中最小的，統計特征主要表現為非線性、非平穩(wěn)性，復顯性最低（當前狀態(tài)后續(xù)出現的可能性不大），結構不確定，該模式下的系統變化非常不穩(wěn)定.模式1對應中度延誤狀態(tài)，主要在早高峰8：00－10：00和13：00－14：00左右時段出現，此時工作人員精力充沛，資源相對富足，延誤尚在可控范圍內.模式3對應高度延誤狀態(tài)，主要在9：00－11：00和15：00－19：00左右時段出現，延誤時間普遍較長.模式1和模式3的各個參數非常接近，都具有較高的延誤率，二者在早高峰之后交替出現，復顯性較低.

圖4 類中心參數歸一化后的4種模式分布

3.3 時變特征分析

圖5描述的是根據本文方法提取的一周延誤率模式在每一天的分布情況，通過對比可以得到共同的延誤模式特征.凌晨0點到早晨7點左右處于模式4暢通狀態(tài)，結合表1中模式4的統計特征可知凌晨0點到7點左右的延誤率具有較強的復顯性以及確定性結構，周期性明顯，模式4偶爾也會出現在23點左右，為航班延誤預測提供了一定的先驗知識，比如當某些數據丟失時就可以利用該段時間的數據通過簡單的計算方法填補空缺值.模式2具有很強的隨機性，出現時間很短，也就是系統變化很快，因此，在做預測時必須考慮加入非線性的約束.模式1和模式3在7點到24點之間交替出現，延誤率較高，但是波動增加不多，遞歸參數相較于模式4均略有下降，說明模式1和模式3結構的復顯性低于模式4，但是也有一定的周期性.航班延誤時變分析與實際情況相符，這就為實施相關航班延誤措施提供了理論依據，例如可以盡量減少模式2的出現，模式1和模式3盡可能多的轉變?yōu)槟Ｊ?：模式2延誤率不大，但是隨機性太強，波動大，出現時間沒有規(guī)律，因此，可以在模式2即將出現之時，對相關延誤航班進行重點監(jiān)控、優(yōu)先保障等，從而減少模式2對整個航空運輸系統帶來的擾動；模式1和模式3延誤情況比較嚴重，二者交替出現在白天航班密集的時間段內，為了更好地對該段時間內的航班延誤進行預警控制，可以在制定航班計劃時避開高峰時刻，將航班錯峰分流至航班平峰或者低谷時間段.盡管不一定能夠降低整體延誤率，但是單一的延誤模式可以使整個系統處于可控制的狀態(tài)，從而使未知的航班延誤帶有一定的可預見性.

圖5 4種典型的延誤模式在一周內每天的分布情況

4 結 論

1）首次將遞歸分析理論引入到航空運輸領域，通過實例分析驗證航班延誤率時間序列的混沌特性，得到暢通、輕度延誤、中度延誤、高度延誤4種典型的航班延誤模式，并獲得每種延誤模式在一周內每一天的分布情況.

2）研究結果不僅有利于航空從業(yè)人員用超前的眼光和科學的方法來應對即將發(fā)生的延誤，并提前采取相應措施，還在一定程度上減輕了后續(xù)延誤航班恢復的工作量和恢復難度.這對于改善航班延誤狀況具有十分重要的理論意義和實際應用價值，為機場當局和航空公司開展航班延誤工作的研究提供了一個全新的角度.

［1］ABDELGHANY K F，ABDELGHANY A F，EKOLLU G. An integrated decision support tool for airlines schedule recovery during irregular operations［J］.European Journal of Operational Research，2008，185（2）：825－848.

［2］JAFARI N，ZEGORDI S H.Simultaneous recovery model for aircraft and passengers［J］.Journal of the Franklin Institute，2011，348（7）：1638－1655.

［3］WONG J T，TSAIA S C.A survival model for flight delay propagation［J］.Journal of Air Transport Management，2012，23：5－11.

［4］邵荃，羅雄，吳抗抗，等.基于貝葉斯網絡的機場航班延誤因素分析［J］.科學技術與工程，2012，20（30）：8120－8124.

［5］DELGADO L，PRATS X.Operating cost based cruise speed reduction for ground delay programs：effect ofscope length［J］. Transportation Research Part C：Emerging Technologies，2014，48：437－452.

［6］袁瑗，陳兵，徐濤，等.基于先驗知識的多類CVM航班延誤預警模型［J］.吉林大學學報（工學版），2010（3）：161－166.

［7］劉雄.基于樞紐機場的航班延誤預警評價研究［D］.廣漢：中國民用航空飛行學院，2012.

［8］TAKENS F.Detecting strange attractors in turbulence［M］. Berlin，Heidelberg：Springer?Verlag，1981.

［9］王海燕.非線性時間序列分析及其應用［M］.北京：科學出版社，2006.

［10］KIM H S，EYKHOLT R，SALAS J D.Nonlinear dynamics，delay times，and embedding windows［J］.Physica D：Nonlinear Phenomena，1999，127（1）：48－60.

［11］FRASER A M，SWINNEY H L.Using mutual information to find independent coordinates for strange attractors［J］. Phys.Rev.A，1986，33：1134－1140.

［12］宋曉，李平，徐公林，等.基于遞歸定量特征的變壓器勵磁涌流識別［J］.中南大學學報：自然科學版，2013（5）：1932－1937.

［13］XIAO Z，CHEN Z，DENG X.Anomaly detection based on a multi?class CUSUM algorithm for WSN［J］.Journal of Computers，2010，5（2）：306－313.

［14］MARWAN C，ROMANO M C，THIEL M，et al. Recurrence plots for the analysis of complex systems［J］. Physics Reports，2007，438（5）：237－329.

［15］BASTOS J A，CAIADO J.Recurrence quantification analysis of global stock markets［J］.Physica A：Statistical Mechanics and its Applications，2011，390（7）：1315－1325.

［16］李新杰.河川徑流時間序列的非線性特征識別與分析［D］.武漢：武漢大學，2013.

［17］劉小飛.基于數據挖掘的航班延誤預測模型及方法的研究［D］.南京：南京航空航天大學，2010.

（編輯 張 紅）

Two?stage extraction method for flight delay pattern

MENG Huifang，PENG Yi
（Optimization Laboratory of Civil Aviation Transportation，Nanjing University of Aeronautics and Astronautics，211100 Nanjing，China）

For the problem of severer flight delays，based on the relative research achievements in domestic and aboard，this paper proposes a two?stage method for extracting flight delay patterns.Firstly，this method uses the phase?space reconstruction theory and Recurrence Plot to analyze the chaotic characteristics of flight delay rate. Then，after acquiring the delay time subsequences，the Recursive Quantitative Analysis and K?means Clustering technology were used to extract flight delay patterns，and the characteristics of time?varying of flight delay patterns were analyzed.Finally，the example verifies this method can not only effectively extract flight delay patterns，but also can get the time?varying characteristics of the patterns.The resultprovides managerialand decisive reference of prediction and warning of flight delay for airports and airlines.

flight delay；phase?space reconstruction；chaotic characteristics；recurrence quantification analysis；delay pattern；time?varying characteristics

F56

A

0367－6234（2015）10－0070－06

10.11918／j.issn.0367?6234.2015.10.014

2014－11－04.

國家裝備預研基金（NAA13002）.

孟會芳（1988—），女，碩士研究生.

孟會芳，huifang_meng＠sina.cn.