基于Petri网的航班机坪保障指挥调度建模*

朱新平，唐志星，夏正洪

（中国民用航空飞行学院空中交通管理学院，四川广汉618307）

基于Petri网的航班机坪保障指挥调度建模*

朱新平，唐志星，夏正洪

（中国民用航空飞行学院空中交通管理学院，四川广汉618307）

为支持航班机坪保障指挥调度优化，提出基于Petri网的机坪保障指挥调度建模方法。构建包含服务线、模块和任务的机坪保障作业协调关联模型，实现保障过程的层次化分解；将保障作业任务分为单设备作业任务和多设备作业任务，给出其模块化赋时Petri网模型构造方法，并针对设备调派过程建模需要进行扩展；考虑作业任务之间的前置开始关联和前置结束关联两类关系，给出其对应Petri网模型之间的合成方法，并提出基于协调关联模型的保障作业指挥调度过程Petri网模型构造算法。以某航班机坪保障指挥调度建模为例，验证所给建模方法的有效性和适用性。

机场，机坪保障，建模，Petri网

0 引言

机坪保障效率低下已成为大型机场航班延误的重要原因之一［1］。为实现机坪保障指挥调度自动化，需构建对应的信息关联模型。航班机坪保障指挥调度过程由若干离散事件推动（如航空器入位、客舱门开启等），属于一类离散事件动态系统，因而可采取Petri网建模［2］。以往有研究采用赋时Petri网建模机坪保障中加油作业［3］或采用着色Petri网建模整个机坪保障作业［4-5］。也有学者采用AOE（Activity On Edge）网络［6-7］或简单时间网络（Simple Temporal Network）［8］建模机位保障过程。但上述研究对机坪保障资源调度缺乏直观描述。其他学者建立了机坪保障作业仿真模型［9-10］。此外，也有学者将机坪保障指挥调度视为多设备并行作业调度问题建立相应地优化调度模型［11］。总结起来，以往机坪保障指挥调度模型不足主要有：①对机坪保障指挥调度过程描述不直观，不利于建模人员和指挥调度人员交互理解；②采用运筹学方法建立的模型参数较多，求解计算较为复杂。

1 航班机坪保障过程

航班机坪保障涉及始发、过站和航后三类航班。以图1所示过站航班机坪保障为例，飞机进机位上轮挡后，调派保障设备至机位开展进港保障作业和离港保障作业，最后撤轮挡推出完成过站保障。始发航班仅涉及离港保障过程，且可能包括始发拖曳作业；航后航班仅涉及进港保障过程，且可能包括航后拖曳作业。在机坪保障过程中，各作业任务均在离散时刻开始或结束，且作业任务之间存在一定的作业时序约束。大型机场机坪空间大、保障持续时间长，且保障设备分属不同部门，通常采取“责任分区”方式进行。机坪保障指挥调度需要跨部门协作，各部门调度人员多基于现场作业通报或手册开展调度，效率较低。

图1 过站航班机坪保障指挥调度过程概观

2 机坪保障协调关联模型

将机坪保障作业分解成旅客服务线、货邮服务线、飞机服务线，各服务线又分解成设备调派模块和机位保障模块，分别负责保障设备的机坪行驶路线规划和作业调度。进一步地，设备调派模块和机位保障模块分解成多个子任务。建立机坪保障协调关联模型（Coordination Correlation Model for Apron Service，CCMAS），如图2所示。

图2 航班机坪保障协调关联模型

定义1机坪保障协调关联模型CCMAS={V，R，φ，E}，其中，V=Vr∪Vs∪Vm∪Vt，Vr为根结点集合，Vs为服务线结点集合，Vm为模块结点集合，Vt=Vd∪Vo为任务结点集合（Vd为调派任务结点集合，Vo为作业任务结点集合）；关系集R=R1∪R2，其中R1={m，o}为不同层次结点间关系的抽象语义集合，m、o分别对应必选、可选关系；R2={pp，pa}为作业任务结点间关系的抽象语义集合，分别对应前置结束关联、前置开始关联。m，o，pp，paV→φ（V），φ（V）为定义在V上的谓词函数，对∀x∊V，φ（x）表示与结点x存在φ关系的所有结点集合；E={（Vi，Vj）|Vi，Vj∊V}为结点间连接关系集合，即边的集合。

CCMAS需满足：①对（V1，V2）∊E，V2∊m（V1）∪o（V1）∪pp（V1）∪pa（V1），即边集合中的元素必对应某一协调关系；②对∀V1∊V，|{x∊V|V1∊m（x）}|+| {x∊V|V1∊o（x）}|+|{x∊V|V1∊pp（x）}|+|{x∊V|V1∊pa（x）}|≤1，即同一对结点间仅允许同时存在一种关系；③对V1，V2∊m（x）∪o（x）且V1，V2∊Vo，x∊V，则V2∊pp（V1）∪pa（V1），即与同一模块结点存在关联的作业任务结点之间一定对应着前置作业关联或后置作业关联。

3 典型作业任务Petri网模型

3.1 单一设备作业任务Petri网模型

定义2单一设备作业任务Petri网模型UPN= {P，T，I，O，M0，Ω}，其中，P={Ps}∪{Pr}∪{Ps0，Ps1}，过程库所Ps表示某任务状态（s对应于任务编号），设备库所Pr表示完成此次作业的设备（r对应于设备编号），Ps0，Ps1分别表示作业任务准备就绪和完成状态库所；变迁ts0，ts1∊T分别表示开始和结束作业任务；I（O）为模型的输入（输出）函数；M0为模型的初始标识；Ω：{Ps}→（Q+∪0）×（Q+∪∞）为作业过程库所对应的任务耗时约束，ps→Ωps=［ai，bi］，其中0≤ai≤bi，Q+为正有理数集。

单一设备作业任务Petri网模型UPN及其简化模型如图3所示。对某一作业任务，用ij表示作业任务耗时，取值在时间区间［ai，bi］且实际指挥调度过程中可视情优化。

图3 单一设备作业任务Petri网模型及其简化模型

3.2多设备作业任务Petri网模型

多设备作业任务包括串联型作业和并联型作业。串联型作业在同一时间仅允许一台设备进入机位开展作业，并可分解为若干子任务，其Petri网模型如图4（a）所示。

图4 多设备保障作业及其对应的Petri网模型

并联型作业任务在同一时间可允许多台设备进入机位作业，其对应Petri网模型如图4（b）所示。对上述模型采用以下方法扩展，以描述保障设备的场面调派行驶过程，如图5所示。具体步骤：对每一作业任务PN模型增加资源库所Rr描述保障设备无任务状态；增加变迁分别描述设备被调用或结束调用，使得，同时对变迁赋时以描述设备由驻地进入机位所需行驶时间；最后，在库所和变迁之间增加使能弧，表明作业任务结束后，相应地设备资源必须释放。

4 机坪保障Petri网模型构造算法

机坪保障作业任务之间存在以下关系：①前置结束关联，即前一作业任务完全结束之后方可开展后一作业任务；②前置开始关联，即一旦前一任务的机位作业开始便可开展后一任务机位作业。对典型任务Petri网模型合成方式如图6所示。若两任务之间满足“前置结束关联”关系，则对其模型可采取第1种合成方式；若两任务之间满足“前置开始关联”关系，则对其模型可采取第2种合成方式。

图5 作业任务对应Petri网模型的设备调派过程扩展

图6 典型作业任务Petri网模型的合成方式

机坪保障指挥调度Petri网模型构造算法思路：首先，对CCMAS模型搜索，找出从根结点到作业任务结点路径上的元素；其次，明确最底层各作业任务结点之间的协调关系；再次，基于典型作业任务Petri网模型构造方法得到各任务结点对应Petri网模型，并依据协调关系进行合成；最后，对所有服务线任务结点对应的Petri网模型进行合成。

算法1：机坪保障指挥调度Petri网模型构造算法。

Step1：确定CCMAS模型各服务线、模块、任务构成，并明确各结点间的协调关系；

Step2：确定CCMAS模型中从根结点到各作业任务结点的路径集合A={r1，r2，…，rn}；

Step3：对路径ri，rj∊A，若存在服务线结点s1∊ri∩rj，进入Step4；

Step4：依据ri，rj中作业任务结点之间的协调关系，利用典型作业任务Petri网模型及其合成方法，得到作业任务Petri网模型；

Step5：对其他路径ri，rj∊A，重复Step3至Step4。

5 实例

以停靠远机位的过站航班机坪保障为例，构建对应的机坪保障指挥调度Petri网模型。该航班机坪保障服务线及作业任务信息如下页表1所示（注：2辆摆渡车同时到机位开始作业）。

表1 航班机坪保障作业服务线及作业任务信息

图7 某航班保障作业对应的CCMAS模型

依据定义1可得到该航班保障作业对应的CCMAS模型如图7所示。

利用所给模型生成算法，首先，从建立的CCMAS模型中获取由根结点到各作业任务结点的路径集合A={r1，r2，…，rn}；其次，明确作业任务结点之间的协调关系；再次，对各作业任务结点建立相应的Petri网模型。以r1={v0，v1，v5，v14}，r2={v0，v1，v5，v15}为例，r1和r2具有相同的服务线结点v1，且作业任务结点v14是v15的“前置开始关联”结点。利用第3节所给典型作业任务Petri网模型构建方法，其对应地作业Petri网模型可记为P-NV14、P-NV15，如图8所示；最后，对该服务线中其他任务结点进行建模，并依据作业任务协调关系及对应地模型合成方法，得到该服务线对应地Petri网模型，如图9所示。

进一步，对其他服务线所含的任务结点建立对应的Petri网模型，并合成得到该航班机坪保障指挥调度Petri网模型，如下页图10所示。

图8 任务结点V12、V13对应的Petri网模型

图9 旅客服务线对应的Petri网模型

6 结束语

提出一种基于Petri网的机坪保障指挥调度过程建模方法。其优点在于：①CCMAS模型能从全局视角直观、清晰地体现机坪保障作业任务协调关系；②以CCMAS模型和典型作业任务Petri网模型为基础，可动态生成机坪保障指挥调度Petri网模型，保证了建模灵活可扩展。进一步研究包括模型特性分析及基于所建模型的机坪保障指挥调度优化算法设计。

图10 航班机坪保障指挥调度Petri网模型

［1］Wu C L，Robert E.Modeling and Optimization of Aircraft Turnaround Time at An Airport［J］.Transportation Planning and Technology，2004，27（1）：47-66.

［2］袁崇义.Petri网原理［M］.北京：北京大学出版社，1999.

［3］宋丽娟，刘长有.基于赋时库所Petri网的飞机地面车辆资源配置［J］.中国民航大学学报，2008，26（增刊）：194-196.

［4］Vidosavljevic A，Tosic V.Modeling of Turnaround Process Using Petri Nets［C］//Proceedings of the 14th ATRS World Conference.Porto，Portugal.2010.

［5］Miquel A，Alexey N，Cesar T.A Simulation Model to Improve Air Cargo Operations in Passenger Aircraft［C］//Proceedings of the 2010 Summer Computer Simulation Conference，San Diego，2010.

［6］赵桂红，刘利.延误航班停机坪作业运行控制研究［J］.中国民航学院学报，2006，24（4）：58-61.

［7］孙瑞山，张子仝.基于CPM的停机坪航班保障工作方法研究［J］.中国民航学院学报，2011，29（5）：23-26.

［8］Leeuwen P，Witteveen C.Temporal Decoupling and Determining Resource Needs of Autonomous Agents in the Airport Turnaround Proces［R］.NLR-TP-2009-336.

［9］Wu C L，Robert E.Modelling of aricraft roatation in a multiple airport environment［J］.Transportation Research，2002，38（2）：265-277.

［10］陶婧婧.机坪保障服务设备调度仿真与优化［D］.南京：南京航空航天大学，2011.

［11］Du Y Q，Zhang Q，Chen Q S.ACO-IH：An Improved Ant Colony Optimization Algorithm for Airport Ground Service Scheduling［C］//Proceedingsofthe2008IEEE International Conference on Industrial Technology.2008.

Petri Net-based Modeling of Command and Dispatch for Flight Apron Service

ZHU Xin-ping，TANG Zhi-xing，XIA Zheng-hong
（School of Air Traffic Management，Civil Aviation Flight University of China，Guanghan 618307，China）

To support the optimization of apron service tasks scheduling，a Petri net-based modeling method for apron service process is proposed.The Coordination Correlation Model for Apron service（CCMAS）is established，including service lines，modules，and tasks，which demonstrates the hierarchal structure of apron service.The service task is categorized into single-equipment service and multi-equipments service process，and the corresponding time Petri net-based modeling approach is provide，including the extension for equipment dispatch process modeling.The composition method for different models is proposed for the front-start and front-end correlation among the corresponding tasks，and also the modeling algorithm of apron service based on the CCMAS was provided.Finally，the effectiveness and applicability of the proposed approach is demonstrated by one flight apron service process modeling.

airport，apron service，modeling，Petri net

V355.1

A

1002-0640（2015）12-0048-05

2014-12-05

2015-02-19

国家自然科学基金委员会与民用航空局联合资助（U1433126）；中国民航飞行学院科研基金面上项目（J2013-60）

朱新平（1983-），男，湖南常德人，博士。研究方向：新一代空中交通管理系统。