基于齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖模型研究

高利佳

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

基于齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖模型研究

高利佳

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

由于國內(nèi)外大部分機(jī)場的指揮調(diào)度系統(tǒng)無法及時(shí)預(yù)知機(jī)場的復(fù)雜事件，致使機(jī)場無法適時(shí)對保障資源做出科學(xué)合理的調(diào)度分配，造成機(jī)場運(yùn)行效率低下。為了提升機(jī)場運(yùn)行效率，提出了基于齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖模型。利用馬爾科夫建模機(jī)場復(fù)雜事件的關(guān)系，實(shí)現(xiàn)機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖，進(jìn)而提前預(yù)警機(jī)場將會(huì)發(fā)生的事件。研究成果有助于我國機(jī)場研發(fā)新一代的高度智能化的指揮調(diào)度系統(tǒng)，以促進(jìn)“民航強(qiáng)國”戰(zhàn)略的實(shí)施。

機(jī)場統(tǒng)一運(yùn)行視圖 馬爾科夫鏈 機(jī)場指揮調(diào)度系統(tǒng)

0 引 言

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

機(jī)場復(fù)雜事件是對機(jī)場業(yè)務(wù)的抽象與高度概括，其本質(zhì)是對機(jī)場業(yè)務(wù)的描述。由于機(jī)場復(fù)雜事件涉及事件的結(jié)構(gòu)描述、前置條件(促使事件發(fā)生的條件)、處理規(guī)則(事件發(fā)生后的處理動(dòng)作)以及事件間多種類型的依賴關(guān)系(如聚合關(guān)系和層次關(guān)系)等關(guān)鍵問題，因此如何建模復(fù)雜事件與業(yè)務(wù)數(shù)據(jù)之間的關(guān)系和復(fù)雜事件間的依賴關(guān)系，是實(shí)現(xiàn)機(jī)場復(fù)雜事件提前預(yù)知的最關(guān)鍵問題。為了解決上述問題，文章提出構(gòu)建基于齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖，期望以此描述整個(gè)機(jī)場業(yè)務(wù)事件的運(yùn)行情況。之所以采用齊次馬爾科夫鏈，[1,2]一方面是由于齊次馬爾科夫鏈?zhǔn)请x散事件描述模型，每個(gè)節(jié)點(diǎn)能描述事件的結(jié)構(gòu)、前置條件和處理規(guī)則；另一方面是因?yàn)辇R次馬爾科夫鏈能夠準(zhǔn)確表達(dá)機(jī)場復(fù)雜事件間的并發(fā)和異步關(guān)系。

1 相關(guān)工作

本文的目標(biāo)是解決機(jī)場業(yè)務(wù)復(fù)雜事件的主動(dòng)預(yù)測，為此與本文密切相關(guān)的研究工作主要包括機(jī)場資源預(yù)測與分配研究、機(jī)場業(yè)務(wù)趨勢預(yù)測研究。

1.1 機(jī)場資源預(yù)測與分配研究

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

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

1.2 機(jī)場業(yè)務(wù)趨勢預(yù)測研究

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

現(xiàn)有的機(jī)場業(yè)務(wù)趨勢預(yù)測研究主要針對機(jī)場單一業(yè)務(wù)趨勢進(jìn)行預(yù)測，忽略了機(jī)場業(yè)務(wù)之間緊密耦合的關(guān)系，使得單一業(yè)務(wù)趨勢的預(yù)測結(jié)果與實(shí)際存在偏差。因此，為提升機(jī)場業(yè)務(wù)趨勢預(yù)測的準(zhǔn)確性，需要建模機(jī)場所有業(yè)務(wù)間的依賴性，而機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖恰好能解決此類問題。

2 基于齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖算法

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

表1 基于齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖算法流程Tab.1 Algorithm process of airport operations view based on homogeneous Markov chain

2.1 機(jī)場復(fù)雜事件的挖掘

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

2.1.1 正常性航班保障的復(fù)雜事件挖掘

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

2.1.2 突發(fā)性復(fù)雜事件的挖掘

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

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

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

2.2 機(jī)場復(fù)雜事件關(guān)系建模

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

圖3 某大型樞紐機(jī)場2010—2013年生產(chǎn)周報(bào)中復(fù)雜事件的統(tǒng)計(jì)結(jié)果Fig.3 Statistical result of complicated incidents in weekly production reports of a large airline hub from 2010 to 2013

圖4 機(jī)場復(fù)雜事件關(guān)系建模的縮略圖Fig.4 Thumbnail of the modeling of airport complicated events

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

由于某大型樞紐機(jī)場ADMS日志系統(tǒng)記錄了整個(gè)機(jī)場航班保障運(yùn)行情況，所以本文將在 ADMS日志數(shù)據(jù)上學(xué)習(xí)公式(3)和公式(4)中的模型參數(shù)。

3 實(shí)驗(yàn)

為了檢驗(yàn)齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖算法的有效性，本文對某大型樞紐機(jī)場生產(chǎn)周報(bào)數(shù)據(jù)和ADMS日志數(shù)據(jù)進(jìn)行試驗(yàn)。

3.1 數(shù)據(jù)集

2010—2013年某大型樞紐機(jī)場的生產(chǎn)周報(bào)被用來挖掘機(jī)場突發(fā)性的事件(見圖 5)。某大型樞紐機(jī)場生產(chǎn)周報(bào)主要記錄：①機(jī)場每周有 3大運(yùn)行指標(biāo)，分別是飛機(jī)起降架次(如總架次、日均架次和高峰日架次)、旅客進(jìn)出港人次(如總?cè)舜巍⑷站舜魏透叻迦杖舜?和航班正常性統(tǒng)計(jì)(進(jìn)港航班正常率、出港航班正常率和放行正常率)；②機(jī)場航站區(qū)、飛行區(qū)和公共區(qū)發(fā)生的異常復(fù)雜事件，以及各部門處置情況；③機(jī)場每周的應(yīng)急救援事件。論文主要利用第 2部分和第3部分的數(shù)據(jù)。

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

圖5 某大型樞紐機(jī)場生產(chǎn)周報(bào)數(shù)據(jù)的截圖Fig.5 Screenshot of a weekly production report of a large airline hub

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

3.2 評價(jià)指標(biāo)

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

其中 s(i)代表按事件發(fā)生概率降序排列的事件列表中第i個(gè)事件的相關(guān)性。當(dāng)與第i個(gè)事件相關(guān)則為 1，否則為 0。在實(shí)驗(yàn)中，k取值一般為 1、3、5、10。

3.3 實(shí)驗(yàn)結(jié)果

將文中提出的算法應(yīng)用于2013年30%的AMDS日志中，實(shí)驗(yàn)結(jié)果如表 2所示?？煽闯?，本文的算法能取得很好的實(shí)驗(yàn)性能。

表2 算法在2013年ADMS日志上的實(shí)驗(yàn)結(jié)果Tab.2 Algorithm experimental result of the ADMS log in 2013

4 結(jié) 語

針對因無法預(yù)知機(jī)場復(fù)雜事件而引起的運(yùn)行效率低下問題，提出了基于齊次馬爾科夫鏈的機(jī)場業(yè)務(wù)統(tǒng)一運(yùn)行視圖算法。算法首先挖掘機(jī)場所有可能的復(fù)雜事件，然后利用齊次馬爾科夫鏈建模復(fù)雜事件間依賴關(guān)系、復(fù)雜事件與其前置條件的關(guān)系，最后在某大型樞紐機(jī)場 ADMS日志學(xué)習(xí)模型參數(shù)。實(shí)驗(yàn)結(jié)果表明，提出的算法能預(yù)測機(jī)場的復(fù)雜事件，為機(jī)場資源智能優(yōu)化奠定基礎(chǔ)。

［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系統(tǒng)模型的跑道容量評估新方法[J].南京航空航天大學(xué)學(xué)報(bào)，2010，42(1)：42-46.

［6］嚴(yán)峻，高強(qiáng)，張曉光.樞紐機(jī)場旅客中轉(zhuǎn)流程優(yōu)化研究[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

中國民航信息化發(fā)展戰(zhàn)略研究C民航局軟科學(xué)研究(MHRD201206)。

2014-11-05