基于HCTC＿Ptri网的机场主要资源调度模型

胡 欣，徐 涛，，曾进进，吕宗磊，

（1.中国民航大学 中国民航信息技术科研基地，天津300300；2.中国民航大学 计算机科学与技术学院，天津300300）

0 引 言

机场资源包括跑道、停机位、廊桥、摆渡车、登机口、机组人员、安检设施等，本文所指的机场主要资源特指跑道和停机位资源，因为这些资源相对紧张，对机场运行效率的影响较大。文献 ［1］基于传统滑行路径和停机位等待理念，建立多跑道机场停机位分配仿真模型，寻求滑行时间最小的分配方案，提高场面运行效率。文献 ［2］从跑道容量评估的角度，对单跑道机场建立容量概率模型，推导出不同情况下单跑道容量的计算公式，并得出不同情况下的跑道容量。文献 ［3］基于停机位类型、航班类型、跑道容量和停机位占用时间，运用蚁群算法，对跑道和停机位进行协调调度，减少飞机滑行时间并节约燃油成本。文献［4］采用离散事件仿真技术根据中转航班旅客到达人数变化实时分配中转资源，并使用软件实现了上海浦东国际机场的中转运行，提高了中转资源的利用率。文献 ［5］为均匀分布指派到机门上的航班，建立基于机门空闲时间数学规划模型并设计了启发式算法进行求解，优化了机门利用率。文献 ［6］基于模块化建模思想，建立先进场面引导并控制系统下航空器场面滑行速度调整特征曲线，并给出场面运行条件变化时对应模型的重构算法。

目前针对多跑道的机场主要资源调度问题的研究主要在提高资源利用率和机场运行效率等方面，本文结合航班时刻分析多跑道机场的主要资源调度问题，可以有效地分析造成航班延误的机场及航班时刻分配方面的原因。提出并建立了机场主要资源调度的HCTC＿Petri网模型，设置合理的控制策略用于动态调节模型参数以及减轻模型运行时的不稳定性。最后，通过实验对模型的准确性和稳定性进行验证，基于新的航班时刻表预测机场的主要资源调度情况。实验结果表明，该模型具有较高的准确性和稳定性，对于新的航班时刻表，若进站之前所有中转航班的总延误时间和架次分别不超过600分钟和22架，则机场对延误情况具有吸收作用，过站后的总延误情况比进站前的有所减轻；若上述2个指标分别超过1000 分钟和31 架，则过站后的总延误情况会加剧。

1 理论与问题分析

库所变迁网称为基本Petri网［7］，适合描述和分析并发处理之间的同步、通信和资源共享问题，但是其表达能力有限，因此产生了多种高级Petri网，其中层次Petri网［8］将系统分层描述，适合大规模系统建模；有色Petri网［9］用不同的颜色区别资源或变迁，可缩小复杂系统的规模；时延Petri网［10］是一种时间相关Petri网，规定变迁的发生具有一个有限的发生时延，反映系统的时间行为；受控Petri网［11］可设计受控库所、受控变迁和控制策略，适合模拟受控系统的运行。

对于多跑道机场而言，停机位数量较多，问题规模较大，可以利用层次Petri网描述大规模系统的能力进行建模，同时利用有色Petri网对不同资源标记不同颜色以简化系统。然而，机场的跑道和停机位被不断使用和释放，利用时延Petri网模拟系统动态行为的能力对资源的使用和释放进行建模，能直观地显示资源的实时占用情况。由于Petri网中多个并发操作产生的结果相互影响，系统运行时会产生不稳定性，通过在受控Petri网中设计控制策略，可以减轻不稳定性，提高系统的正确性。针对机场同时具有资源数量多、问题规模大、实时性和不稳定性的特点，单一使用各模型无法同时满足资源调度中的所有需求，应结合层次、有色、时延和受控Petri网，对机场主要资源调度问题建模。

综上所述，面向机场主要资源调度问题，本文提出结合以上4种高级Petri网的一种混合Petri网 （HCTC＿Petri网），模拟现有航班时刻下并预测新的航班时刻下，机场主要资源调度情况。

2 HCTC＿Petri网定义

记N＝ ｛1，2，3，…｝为正整数集合，k，l，m，n∈N ，下标C和U 分别表示可控和不可控。HCTC＿Petri网 （简称为HCTC＿PN）定义为

其中

式中：Pi——库所的集合。

式中：Ti——变迁的集合；Ci——颜色的集合；Di——定义在变迁上的时间函数的集合。

式中：SNi——子网的集合。

式中：Fi——弧的集合。

式中：Ctrli——控制策略的集合；INi和OUTi——HCTC＿PNi的输入集和输出集，M0i——初始标识的集合。

若HCTC＿PNi为另一个HCTC＿PNj的子网，则

否则INi＝OUTi＝。

若i∈ ｛1，…，k｝，- （SNi＝）∩ （INi＝）∩（OUTi＝）则HCTC＿PN 是一类不含层次概念的混合Petri网；若i∈ ｛1，…，k｝，-Ci＝，则HCTC＿PN是一类不含颜色概念的混合Petri网；若i∈ ｛1，…，k｝，-Di＝，则HCTC＿PN 是1类不含时延概念的混合Petri网；若i∈ ｛1，…，k｝，- （PiC＝）∩ （TiC＝）∩（Ctrli＝），则HCTC＿PN 是一类不含受控概念的混合Petri网。

3 机场主要资源调度的HCTC＿Petri网模型

3.1 机场主要资源调度流程

本文将经过某机场的航班分为3 类：着陆航班、中转航班和起飞航班。其中着陆航班是将该机场作为目的机场，并且到达后当天不再离开的航班；中转航班是指到达后当天离开该机场的航班；起飞航班是将该机场作为当天飞行计划的第1站，离开后当天不再返回的航班。着陆航班和中转航班达到机场空域时，首先向空管部门提出着陆申请，然后占用跑道着陆，接着进行地面服务，所不同的是着陆航班最终进入停机状态，而中转航班要再次申请跑道资源进行起飞，最终进入飞行状态。起飞航班则是申请获得跑道资源以后起飞，进入飞行状态。机场主要资源调度的流程如下：

步骤1 初始化跑道、停机位、航班等资源；

步骤2 判断航班类型，若为起飞航班，转步骤6；

步骤3 判断可用跑道数，若为0，则空中等待，直到可用跑道资源数不为0；

步骤4 着陆，地面滑行之后进入停止状态，完成各项地面服务；

步骤5 判断航班类型，若为着陆航班，则进入停机状态，转步骤7；

步骤6 判断可用跑道数，若为0，则地面等待，直到可用跑道资源数不为0，起飞，进入飞行状态；

步骤7 结束。

3.2 机场主要资源调度的HCTC＿Petri模型

本文将HCTC＿Petri网理论应用于解决多跑道机场的主要资源调度问题，得到机场主要资源调度的HCTC＿Petri网模型 （简称HCTC＿PN，如图1所示），模型中的主要库所及变迁含义见表1。

表1 模型中库所和变迁的含义

图1 机场主要资源调度的HCTC＿Petri网模型

机场主要资源调度的HCTC＿Petri网模型的定义如下：HCTC＿PN＝ ｛HCTC＿PN1，…，HCTC＿PN5｝，其中，HCTC ＿PN1＝ （P1，T1；C1，D1，SN1，F1，Ctrl1，IN1，OUT1，M01），如图1 （a）所示，P1＝ ｛p0，p2，p3，p4，p5｝；T1＝ ｛t1，t2，t3，t4，t5｝；C1＝｛seed，flight｝，seed表示种子资源，flight表示航班资源；D1＝ ｛0，n，0，0，0｝表示变迁t1、t3、t4、t5的时延均为0，变迁t2的时延为n；SN1＝ ｛HCTC＿PN3，HCTC＿PN4，HCTC＿PN5｝，表示HCTC＿PN1包含3个子模型；F1＝ ｛＜p0，t1＞，＜t1，p2＞，＜p2，t2＞，＜t2，p3＞，＜p3，t3＞，＜p3，t4＞，＜p3，t5＞，＜t3，p4＞，＜t4，p5＞，＜t5，p5＞｝Ctrli＝；IN1＝ ｛p4，p5｝；

OUT1＝ ｛p3｝；M01＝ ｛seed0｝，seed0 用于引发变迁t1，启动模型。HCTC＿PN1的功能是对整个机场主要资源调度情况的抽象，初始化航班资源，并根据航班类型将不同航班分配给不同的下层子模型处理。

HCTC＿PN2的功能是初始化跑道和停机位资源，并以一定的概率进行跑道维修、跑道除冰、停机位维修等作业，使跑道或停机位进入不可用状态，如图1 （b）所示。

HCTC＿PN3、HCTC＿PN4、HCTC＿PN5 分别模拟起飞航班、中转航班和着陆航班在机场的调度情况，具体如图1 （c）、 （d）、 （e）所示。库所p27－p29 是受控库所，动态调节与其直接相连的变迁的发生时延，影响模型的动态行为。

3.3 控制策略

模型中的控制策略主要体现在2个方面：

（1）设置优先级

由于模型中部分并发变迁发生的先后顺序不同，模型调度结束后的航班延误情况差异较大，产生不稳定性。通过设置优先级规定并发变迁发生的先后顺序，可以提高结果的稳定性，方法是引入抑止弧 （一端是实心圆的曲线），如模型中T20优先级比T15高。

（2）引入受控库所

通过程序分析不同输入数据的特点，动态设置受控库所的内部资源，而这些资源直接控制模型中与受控库所直接相连的变迁的发生时延，从而使模型兼容差异较大的输入数据，具有更高的准确性。

4 实验验证及结果分析

本文利用CPN Tools工具软件［12］对机场主要资源调度问题建模并仿真分析，采用国内某个具有2条跑道的机场1个月内的实际航班数据，提取其中每天上午高峰时段 （9点到11点）的数据进行实验。

4.1 模型的准确性验证

在前站延误已知的情况下，模拟机场调度的情况，共进行31组实验，每组实验20次，将实验得出的航班离开机场的后站延误与实际的后站延误相比，取均值，其结果如图2所示。中转符合率、起飞符合率、着陆符合率和总符合率分别指所有中转航班、所有起飞航班、所有着陆航班和所有航班经过模型调度后的延误架次与实际运行中的延误架次的比值。

图2 各类航班的后站延误符合率对比

由图2 可知，通常，中转航班的符合率平均高达90.0%，而起飞航班的符合率平均仅为77.1%，由于着陆航班到达机场后当日不再离开，不存后站延误，其符合率为100%，总符合率较稳定，平均90.7%。通过上述分析可见，HCTC＿Petri网模型的准确性较高。

4.2 模型的稳定性验证

由于Petri网模型本身的不稳定性，导致即使将同一组数据集输入模型中，多次实验的结果可能相差很大，本文设计的控制策略能较好地减轻上述结果的不稳定性。对8号上午9点到11点的数据进行90次实验，并将每次实验得到的延误情况与实际延误情况相比，统计其误差如图3所示。

图3 仿真与实际的误差统计

由图3可知，对于同一组输入数据集，实验得出的延误情况与实际延误情况相比，其误差不超过7%，由此可见，HCTC＿Petri网模型的稳定性较好。

4.3 机场主要资源调度情况预测

生成10份航班时刻表 （其中包含中转航班总架次、中转前站延误总时间、中转前站延误总架次、起飞航班总架次、着陆航班总架次），分成10组作为模型的输入数据集进行实验，每组实验20次，得出中转后站延误总时间和总架次的变化量以及起飞延误总时间和总架次，分别取均值，实验结果见表2。

表2 新航班时刻表的机场调度预测

由表2可知，前4组实验中，新排航班时刻表的中转航班前站延误总时间不超过600分钟，中转前站延误总架次不超过22架，预测得出中转航班后站延误总时间或总架次均有所减少，延误情况有所缓解，此时机场对前站延误可起到吸收作用；在第5到第8组实验中，中转航班前站延误总架次在24到31之间，从预测的结果可知，其后站延误架次大部分有所较少，但是后站延误的总时间都增大，中转航班延误的吸收情况不明显；在后2组实验中，中转航班前站延误总时间和总架次分别超过1000分钟和31架，从预测的结果可知，中转后站延误总架次明显增加，可见中转航班延误情况加剧。此外，预测起飞航班延误的总时间和总架次不具有明显规律。

5 结束语

本文结合层次Petri网、有色Petri网、时延Petri网和受控Petri网理论，提出了HCTC＿Petri网，并将HCTC＿Petri网应用于多跑道机场主要资源调度问题，建立了机场主要资源调度的HCTC＿Petri网模型，设置合理的控制策略调节模型参数，实验结果表明，该模型具有较高的准确性和稳定性。对于新的航班时刻表，HCTC＿Petri网模型能预测机场的调度情况，分析中转航班进站前的延误总时间和总架次对过站后延误的影响情况，可以为机场保障能力评估以及航班时刻分配与评价提供参考依据。

［1］YIN Jianan，HU Minghua，ZHAO Zheng.Simulation model and algorithm of multi－runway airport gate assignment ［J］.Journal of Traffic and Transportation Engineering，2010，10（5）：71－76 （in Chinese）. ［尹嘉男，胡明华，赵征.多跑道机场停机位分配仿真模型及算法 ［J］.交通运输工程学报，2010，10 （5）：71－76.］

［2］LU Chaoyang.New method for runway capacity assessment based on T system model［J］.Journal of Nanjing University of Aeronautics＆Astronautics，2010，42 （1）：42－46 （in Chinese）. ［卢朝阳.基于T 系统模型的跑道容量评估新方法［J］.南京航空航天大学学报，2010，42 （1）：42－46.］

［3］DING Jianli，LI Xiaoli，LI Quanfu.Ant scheduling model for critical resources based on airport taxi［J］.Application Research of Computers，2011，28 （4）：1279－1282 （in Chinese）. ［丁建立，李晓丽，李全福.面向场面滑行的机场关键资源蚁群调度模型［J］.计算机应用研究，2011，28 （4）：1279－1282.］

［4］ZHANG Xiaoguang，ZHU Jinfu，TAO Jingjing.Simulation on hub－airport transfer based on resource optimization ［J］.Journal of Wuhan University of Technology （Transportation Science＆Engineering），2012，36 （1）：188－191 （in Chinese）.［张晓光，朱金福，陶婧婧.基于资源优化的枢纽机场中转仿真 ［J］.武汉理工大学学报 （交通科学与工程版），2012，36 （1）：188－191.］

［5］ZHENG Pan，HU Siji，ZHANG Chen.Gate assignment modeling and heuristic algorithm design ［J］.Journal of Systems Engineering，2011，26 （1）：127－131 （in Chinese）.［郑攀，胡思继，张晨.机门指派模型建立与启发式算法设计［J］.系统工程学报，2011，26 （1）：127－131.］

［6］ZHU Xinping，TANG Xinmin，HAN Songchen.Reconfigurable Petri net modeling of airport surface operation under control of A－SMGCS ［J］.Journal of WUT （Information＆Management Engineering），2013，35 （1）：23－27 （in Chinese）.［朱新平，汤新民，韩松臣.A－SMGCS机场场面运行可重构Petri网建模 ［J］.武汉理工大学学报 （信息与管理工程版），2013，35 （1）：23－27.］

［7］PAN Li，ZHAO Weidong，WANG Zhicheng，et al.On the step problem for Petri nets ［J］.Journal of Software，2009，20 （3）：505－514 （in Chinese）. ［潘理，赵卫东，王志成，等.Petri网的步问题研究 ［J］.软件学报，2009，20 （3）：505－514.］

［8］LIU Ming，ZHANG Guoyin，YAO Aihong，et al.Research on modeling and analyzing method of Real－time system based on hierarchical real－time colored Petri net ［J］.Journal of Electronics ＆Information Technology，2011，33 （3）：580－586.［刘铭，张国印，姚爱红，等.基于层次实时有色Petri网的实时系统建模与分析方法研究 ［J］.电子与信息学报，2011，33（3）：580－586.］

［9］LI Peiwu，LEI Jin’e.Extended usage control strategy model based on colored Petri net design ［J］.Computer Engineering and Applications，2012，48 （33）：96－100 （in Chinese）. ［李沛武，雷金娥.有色Petri网的扩展使用控制策略模型设计［J］.计算机工程与应用，2012，48 （33）：96－100.］

［10］YANG Nianhua，YU Huiqun，SUN Hua.Model checking of timed colored Petri nets with inhibitor arcs ［J］.Computer Science，2011，38 （1）：170－176 （in Chinese）.［杨年华，于慧群，孙华.带抑制弧的时延着色Petri网模型检测技术［J］.计算机科学，2011，38 （1）：170－176.］

［11］ZHENG Han.Explicit－controller design for controlled Petri net based on simplification ［D］.Hangzhou：Zhejiang University，2010 （in Chinese）.［郑寒.基于简化技术的受控Petri网的显式控制器设计 ［D］杭州：浙江大学，2010.］

［12］ZHAN Dongsheng，ZHANG Wei，GU Mingjia.The modeling and simulation technique study based on CPN tools ［J］.Microcomputer Information，2010，26 （5－1）：164－166 （in Chinese）.［占东生，张伟，顾明甲.基于CPN TOOLS的网络协议建模与仿真技术研究 ［J］.微计算机息，2010，26（5－1）：164－166.］