基于齐次马尔科夫链的机场业务统一运行视图模型研究

高利佳

(北京首都国际机场股份有限公司 北京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