基于齊次馬爾科夫鏈的機場業務統一運行視圖模型研究

高利佳

(北京首都國際機場股份有限公司 北京100621)

基于齊次馬爾科夫鏈的機場業務統一運行視圖模型研究

高利佳

(北京首都國際機場股份有限公司 北京100621)

由于國內外大部分機場的指揮調度系統無法及時預知機場的復雜事件，致使機場無法適時對保障資源做出科學合理的調度分配，造成機場運行效率低下。為了提升機場運行效率，提出了基于齊次馬爾科夫鏈的機場業務統一運行視圖模型。利用馬爾科夫建模機場復雜事件的關系，實現機場業務統一運行視圖，進而提前預警機場將會發生的事件。研究成果有助于我國機場研發新一代的高度智能化的指揮調度系統，以促進“民航強國”戰略的實施。

機場統一運行視圖 馬爾科夫鏈 機場指揮調度系統

0 引 言

面對有限的保障資源(如廊橋、登機口、機位和車輛)及日益增長的航空旅客數量，大型繁忙機場由于無法及時預知復雜事件(如航班延誤、旅客異常行為、信息系統故障)的發生，使得機場無法提前對保障資源做出科學合理的調度分配，進而降低了機場運行效率，甚至有時引發一系列嚴重影響和諧社會構建的群體性事件，如旅客聚眾打砸機場柜臺、旅客與機場管理人員激烈沖突等。因此，如何提升機場復雜事件的預警能力是各個機場面臨的重要難題，同時也是國際民航界的研究熱點。

機場復雜事件是對機場業務的抽象與高度概括，其本質是對機場業務的描述。由于機場復雜事件涉及事件的結構描述、前置條件(促使事件發生的條件)、處理規則(事件發生后的處理動作)以及事件間多種類型的依賴關系(如聚合關系和層次關系)等關鍵問題，因此如何建模復雜事件與業務數據之間的關系和復雜事件間的依賴關系，是實現機場復雜事件提前預知的最關鍵問題。為了解決上述問題，文章提出構建基于齊次馬爾科夫鏈的機場業務統一運行視圖，期望以此描述整個機場業務事件的運行情況。之所以采用齊次馬爾科夫鏈，[1,2]一方面是由于齊次馬爾科夫鏈是離散事件描述模型，每個節點能描述事件的結構、前置條件和處理規則；另一方面是因為齊次馬爾科夫鏈能夠準確表達機場復雜事件間的并發和異步關系。

1 相關工作

本文的目標是解決機場業務復雜事件的主動預測，為此與本文密切相關的研究工作主要包括機場資源預測與分配研究、機場業務趨勢預測研究。

1.1 機場資源預測與分配研究

1999年，Hon Wai Chun[3]研究機場登機口分配時提出資源分配系統和資源仿真系統相結合的辦法，為每個離港航班動態分配登機口資源。2006年，Han等人[4]針對多跑道機場的跑道分配問題，結合馬爾科夫決策過程理論提出了一種最優化分配策略，可降低機場平均延誤代價，提高機場效益。2010年，盧朝陽[5]從跑道容量評估的角度，對單跑道機場建立容量概率模型，推導出不同情況下單跑道容量的計算公式，并得出不同情況下的跑道容量。2011年，在研究機場的中轉設施資源分配問題上，嚴峻等人[6]利用離散時間仿真技術，根據中轉航班旅客到達人數的階段性變化動態地將中轉設施資源指派給各個航班。

現有的機場資源分配模型都側重于機場單一資源的分配，并未考慮機場其他資源的綜合分配問題。然而，在機場實際運行中航班保障同時涉及多種資源，且有些資源在使用過程中相互制約，而單一資源分配方案并不能保障機場所有資源的最大化利用，也不能將航班保障時間最小化。為此，需要從機場整個業務運行角度統籌考慮機場所有資源的分配，而本文正是基于此出發點開展研究。

1.2 機場業務趨勢預測研究

機場業務趨勢預測研究側重于研究機場未來數小時內業務的形勢，主要包括航班備降預測、航班延誤分析、旅客流量趨勢、旅客流程關鍵瓶頸預測、旅客進出港高峰時段預測研究，以及安檢、進港行李、APM 等關鍵節點擁堵預測等。北京航空航天大學開展了時隙分配算法在地面等待程序中的應用研究，提出了進港排序及終端區沖突解脫算法等，進而減少航班地面等待時間。民航數據通信有限責任公司研制了基于協同決策的地面等待程序 CDM-GDP。針對天氣等各種突發事件造成的機場容量大幅度下降、需求/容量比例不平衡等問題，采用 CDM-GDP使航空公司參與到流量協調過程中，及時調整航班計劃，將可能的空中等待延誤時間轉移到地面等待，通過整體壓縮優化排序，減少延誤時間。

現有的機場業務趨勢預測研究主要針對機場單一業務趨勢進行預測，忽略了機場業務之間緊密耦合的關系，使得單一業務趨勢的預測結果與實際存在偏差。因此，為提升機場業務趨勢預測的準確性，需要建模機場所有業務間的依賴性，而機場業務統一運行視圖恰好能解決此類問題。

2 基于齊次馬爾科夫鏈的機場業務統一運行視圖算法

針對現有的機場資源及業務預測模型因未全局考慮業務間依賴關系而導致資源利用率和運行效率低下的問題，本文提出基于齊次馬爾科夫鏈的機場業務統一運行視圖算法，建立機場業務運行統一視圖，從而刻畫機場業務的依賴性。算法首先挖掘機場業務最核心元素——復雜事件，然后利用齊次馬爾科夫鏈描述復雜事件及其依賴關系，最后從機場實際運營數據中學習復雜事件間的依賴程度。算法的流程如表1所示。

表1 基于齊次馬爾科夫鏈的機場業務統一運行視圖算法流程Tab.1 Algorithm process of airport operations view based on homogeneous Markov chain

2.1 機場復雜事件的挖掘

為了能夠更好地描述機場業務，本文抽取機場業務最核心元素——復雜事件。復雜事件主要由兩部分組成，即機場正常性航班保障的復雜事件(如客運保障、貨運保障、機務保障)和機場突發性復雜事件(如旅客異常行為、信息系統故障)。

2.1.1 正常性航班保障的復雜事件挖掘

正常性航班保障的復雜事件挖掘旨在根據民航領域的專業知識，從機場地面保障最核心的 4大流程——旅客流、行李流、貨郵流、飛機流中挖掘所有可能的復雜事件及其前置條件(促使事件發生的條件)和處理規則(事件發生后的處理動作)(見圖 1、圖 2)。

2.1.2 突發性復雜事件的挖掘

圖1 航班地面保障4大流程Fig.1 Four procedures of ground supporting services

圖2 旅客流保障復雜事件的縮略圖Fig.2 Thumbnail of customer flow guarantee measures under complicated events

突發性航班保障的復雜事件挖掘旨在挖掘描述機場的突發性、異常性事件。為此，通過對某大型樞紐機場 2011—2013年每周生產統計報告(簡稱生產周報)進行人工標注，并進一步統計機場航站區、飛行區、公共區和應急救援的復雜事件，進而得到機場所有潛在的異常事件。經統計，某大型樞紐機場2011—2013年生產周報中共包含 127種不同類型的復雜事件(見圖 3)。由于突發性復雜事件出現的次數偏向于長尾分布，為此在實際中應集中研究出現次數多且影響大的復雜事件，丟棄出現次數少的事件。為了選擇合適且恰當的事件出現次數的閾值，研究假設復雜事件出現的次數符合正態分布，選擇雙側置信區間 95%，最終得到事件出現次數的閾值為 3.9，為此論文只選擇52種異常性事件進行研究。

2.2 機場復雜事件關系建模

機場復雜事件關系建模旨在建立復雜事件與其前置條件的依賴性，復雜事件間的依賴關系。部分復雜事件關系的建模如圖 4所示，其中矩形代表事件，圓圈代表事件的前置條件，直線代表關系。

圖3 某大型樞紐機場2010—2013年生產周報中復雜事件的統計結果Fig.3 Statistical result of complicated incidents in weekly production reports of a large airline hub from 2010 to 2013

圖4 機場復雜事件關系建模的縮略圖Fig.4 Thumbnail of the modeling of airport complicated events

假設機場復雜事件集合 E＝{e1，e2，….，en}，每個事件 ei存在 ti(ti≥0)個前置條件 S(ei,1)，S(ei,2)，…，S(ei,ti)，那么在給定復雜事件已發生的序列Om＝{em,1，em,2，…，em,m}E前提下，復雜事件 ei發生的概率Pr(ei|Om)可以展開為：

由于某大型樞紐機場ADMS日志系統記錄了整個機場航班保障運行情況，所以本文將在 ADMS日志數據上學習公式(3)和公式(4)中的模型參數。

3 實驗

為了檢驗齊次馬爾科夫鏈的機場業務統一運行視圖算法的有效性，本文對某大型樞紐機場生產周報數據和ADMS日志數據進行試驗。

3.1 數據集

2010—2013年某大型樞紐機場的生產周報被用來挖掘機場突發性的事件(見圖 5)。某大型樞紐機場生產周報主要記錄：①機場每周有 3大運行指標，分別是飛機起降架次(如總架次、日均架次和高峰日架次)、旅客進出港人次(如總人次、日均人次和高峰日人次)和航班正常性統計(進港航班正常率、出港航班正常率和放行正常率)；②機場航站區、飛行區和公共區發生的異常復雜事件，以及各部門處置情況；③機場每周的應急救援事件。論文主要利用第 2部分和第3部分的數據。

2013年某大型樞紐機場ADMS日志數據主要被用來計算復雜事件間的依賴關系(見圖 6)。某大型樞紐機場ADMS日志數據主要記錄航班保障業務處理過程，主要包括提交時間、部門、模塊、提交人、日志內容、事件號和是否有附件。ADMS日志數據因不能直接用于計算復雜事件間的依賴關系，所以需要對其進行整理，步驟為先從 ADMS日志中人工標注事件的類型；再對已標注的事件，按照事件發生時間進行排序，從而得到事件依賴關系。本文將 2013年ADMS日志拆分成兩部分，70%數據用來訓練模型，而剩下30%數據用來測試。

圖5 某大型樞紐機場生產周報數據的截圖Fig.5 Screenshot of a weekly production report of a large airline hub

圖6 某大型樞紐機場ADMS日志數據的截圖Fig.6 Screenshot of the ADMS log data of a large airline hub

3.2 評價指標

為了客觀評價算法的性能，使用指標準確率Precision[7]進行衡量，見公式(5)。算法的具體評估過程為：①首先根據公式(1)和(2)算出每個事件 ei的發生概率；②按照概率降序排列事件；③將產生的事件列表與測試數據中真實列表(按照事件發生的時間先后)進行對比，其中對比的公式為公式(5)；④對所有事件準確率 Precision進行求平均，其平均值為算法的性能。

其中 s(i)代表按事件發生概率降序排列的事件列表中第i個事件的相關性。當與第i個事件相關則為 1，否則為 0。在實驗中，k取值一般為 1、3、5、10。

3.3 實驗結果

將文中提出的算法應用于2013年30%的AMDS日志中，實驗結果如表 2所示。可看出，本文的算法能取得很好的實驗性能。

表2 算法在2013年ADMS日志上的實驗結果Tab.2 Algorithm experimental result of the ADMS log in 2013

4 結 語

針對因無法預知機場復雜事件而引起的運行效率低下問題，提出了基于齊次馬爾科夫鏈的機場業務統一運行視圖算法。算法首先挖掘機場所有可能的復雜事件，然后利用齊次馬爾科夫鏈建模復雜事件間依賴關系、復雜事件與其前置條件的關系，最后在某大型樞紐機場 ADMS日志學習模型參數。實驗結果表明，提出的算法能預測機場的復雜事件，為機場資源智能優化奠定基礎。

［1］L.R.Rabiner.A tutorial on hiddenmarkovmodels and selected applications in speech recognition[J].Proceedings of the IEEE，1989，77(2)：257-286.

［2］E.B.Leonard，P.Ted，G.Soules，et al.A maximization technique occurring in the statistical analysis of probabilistic functions ofMarkovchains[J].Annals of Mathematical Statistics，1970，41(1)：164-171.

［3］Hon W.C.Intelligent resource simulation for an airport check-in counter allocation system[J].IEEE Transactions on Systems，Man，and Cybernetics，Part C：Applications and Reviews，1999，29(3)：325-335.

［4］Han S.C.，Cheng L.Y.Optimization of dispatch strategy with multi-runway by Markov Decision Process[C].The 1st International Symposium on Systems and Control in Aerospace and Astronautics，2006，73-76.

［5］盧朝陽.基于 T系統模型的跑道容量評估新方法[J].南京航空航天大學學報，2010，42(1)：42-46.

［6］嚴峻，高強，張曉光.樞紐機場旅客中轉流程優化研究[J].中國民航航空期刊，2011(123)：39-42.

［7］Ricardo A.Baeza-Yates，Berthier A.Ribeiro-Neto.Modern Information Retrieval-The Concepts and Technology Behind Search[M].2nd edition.Boston：Addison-Wesley Professional，2011.

A Homogeneous Markov Chain-based Airport Operations View Model

GAO Lijia
(Beijing Capital International Airport Co.，Ltd.，Beijing 100621，China)

In most airports，both at home and abroad，the command and dispatching system is unable to predict complicated incidents in advance，which causes a poor performance of airport operation as the airports cannot make reasonable allocation of supporting resources in good time.To address this issue，the paper proposed a model of airport operations view based on the homogeneous Markov chain.The key idea of the model is to apply the theory in the modeling of correlation of airport complex events to warn airports of what will happen.This research achievement will help airports in China develop a more automatic and intelligent scheduling system and promote the implementation of the strategy of a “Strong Civil Aviation Nation”.

airport operations view；Markov chain；airport command and dispatching system

TP391

A

1006-8945(2014)12-0010-05

中國民航信息化發展戰略研究C民航局軟科學研究(MHRD201206)。

2014-11-05