复杂环境下基于价格时间自动机飞机着陆调度*

姬莉霞，张 晗

（郑州大学软件技术学院，河南郑州 450002）

0 引言

如何对到港飞机进行高效合理的排序是管制员的主要职责，管制员根据飞行数据、经验和直观判断，确定飞机着陆次序和时间。现有调度策略一般在满足相邻飞机尾流间隔和其他空管规则的限制下，根据先到先服务（first come first serve，FCFS）原则制定每架飞机的着陆时间。此方法存在很大局限性:首先，管制员在短时间内做出决定，很难详细考虑各种方案的利弊，可能会造成不必要的冲突和延误;其次，从经济效益考虑，调度方案的不科学性将导致着陆总成本的无谓增加。

飞机着陆调度问题在近20年来得到各国研究机构和空管部门的广泛研究［1～4］，主要内容为确定着陆飞机队列的顺序、时间和跑道指派，以达到减小延误、提高系统容量和增强飞行安全的目的。本文在研究相关文献的基础上，主要从三方面着手研究:1）在每架飞机着陆时间窗范围内安排着陆时间;2）满足相邻飞机最小尾流间隔;3）根据机型、环境因素、到达时间等参数安排跑道和着陆时间。采用时间自动［5］（timed automata，TA）机及其扩展分支价格时间自动［6］（priced timed automata，PTA）机作为形式化方法。

1 问题描述与概念模型的建立

假设某机场具有m条不同方向的跑道，交通流量为Δt时间内有n架飞机着陆，集合E={i|1≤i≤n}代表飞机以最佳巡航速度预计到达序列，即飞机最佳着陆时间序列，集合W={［i，j］|1≤i≤2，1≤j≤n}为飞机着陆时间窗，集合S={j|1≤j≤n}为调度后飞机的实际降落时间序列。本文采用的调度结果是得到与E（i）一一对应的S（j），并满足以下约束:

1）飞机在其时间窗内降落

2）同一跑道上连续降落的飞机满足安全尾流间隔。以i⇒j为飞机j尾随i降落在相同跑道;常量C表示基准尾流间隔;集合T={［i］|1≤i≤n}为飞机相应的尾流间隔系数;e为综合环境影响参数，主要包括风力风向、跑道方向、雨雪雾等，这些因素皆能对安全尾流间隔造成影响，从而直接影响后续飞机着陆时间和额外成本

3）着陆时飞机如果能够逆风飞行，不仅可以使状态更稳定，而且着陆后可以更快地在跑道上停止，从而减少所需跑道的长度和安全尾流间隔，因此，尽可能为到港飞机安排逆风的跑道。用R={i|1≤i≤m}为跑道的角度，变量d为风向，两者采用相反的原始坐标和相同的增加方向

飞机着陆调度的目标通常为容量最大或总延误最小，本文兼顾两者，采用额外总成本最优作为目标。假设第i架飞机单位时间内因为提前降落而加速飞行产生的额外费用为F（i），单位时间内延迟降落盘旋产生的费用为Y（i），则额外消耗最优成本问题的概念性数学模型为

2 形式化模型的建立

2．1 时间自动机和价格时间自动机

时间自动机被广泛应用于各类拥有触发事件和时间约束的复杂实时系统，在模型验证方面得到了非常广泛的应用［7］。

定义1:一个时间自动机是一个八元组TA=（L，l0，C，A，E，I，V，T）:L为有限位置集合;l0∈L为开始位置集合;C为有限时钟集合;A为有限动作集合;E⊆L×Ф（C）×A×2C×L为边的集合，边一般伴随有动作、卫士条件和复位时钟集合;I:L→Ф（C）为位置的不变式;V为有穷变量集合;T:L×A→L为转换函数。

价格时间自动机是在时间自动机的基础上扩展价格元素的模型，它是建模和解决成本最优问题的形式化方法。

定义2:一个价格时间自动机是一个九元组PTA=（L，l0，C，A，E，I，V，P，T），其中，L，l0，C，A，E，I，V，T与TA中意义相同，P:L∪E→N0表示给位置和边分配价格元素。

多个并发的PTA可以构成价格时间自动机网络，每个PTA都有自身的状态，它们之间共享时钟变量和全局数据变量，并通过边上的动作同步协作，通过共享全局变量进行传值通信。格局用于描述价格时间自动机网络中所有PTA的运行状态。

定义3:假设有n个价格时间自动机PTA1，…，PTAn，由这n个价格时间自动机构成的网络为价格时间自动机的积，记为PTAN≡PTA1‖PTA2…‖PTAn，它的一个格局表示为一个三元组c=〈l，r，v〉，其中

2．2 调度主体的PTA模型

飞机着陆问题牵涉的最重要对象是飞机，取样n架飞机，抽象得到如图1所示的价格时间自动机模型Aircraft。在模型中，位置Approach表示飞机进入管制台雷达视线范围，位置 Early，Ontime，Delay分别为飞机提前［W（1，i），E（i）］、准时E（i）和延后［E（i），W（2，i）］，在转换约束下，这3个位置仅有1个可能处于活动状态。位置Early产生的额外成本为引擎加速飞行造成，计算方法为该位置的价格与其处于活动状态的时间的积。位置Ontime为紧迫位置，也就是当其转换条件满足时毫无延迟的发生，在此位置不产生额外成本。位置Delay产生的额外成本为盘旋等待着陆产生的消耗，计算方法为该位置的价格与该位置处于活动状态的时间的积。紧迫位置Urg保证在临近时间窗结束时，暂时不考虑成本因素，优先降落。位置Special表示在综合环境影响参数高于安全着陆阈值时，收到广播信号poor，此时飞机等待着陆或备降信号。

图1 飞机的价格时间自动机模型示意图Fig 1 Diagram of PTA model of aircraft

2．3 交互实体的PTA模型

在着陆过程中，与飞机交互作用的实体应具备以下特征:拥有唯一的身份标识以区别于其他实体;拥有一定的物理或者虚拟属性，状态可以被改变或者可以被感知;具有通信能力。如果将各个交互实体看作对象，那么相同属性的实体可以被抽象为类，从飞机着陆过程中，可以抽象出控制台、管制员、雷达、跑道、环境等类，为弱化系统内部交互，将雷达和管制员并入控制台类，则各实体的PTA模型示意如图2所示。

图2 交互实体的价格时间自动机模型示意图Fig 2 Diagram of PTA models of interacting entities

跑道（runway）模型的位置Idle和Use分别表示跑道空闲和使用，跑道的选择通过边ready的价格参数来确定，优先为飞机安排空闲逆风跑道，跑道选定后判断风力是否为积极影响，并据此影响尾流间隔。环境属性只能被感知而不能被改变，其模型 Enviorment的固有属性es，ew，er，es，ef和wdir分别表示当前风力参数、降雨参数、冰雪参数、雾霭参数、其他环境系数以及当前风向，当综合环境影响参数超出安全着陆阈值时，通过控制器发出广播信号poor。控制器模型 Control主要通过信道 approach，ready，land，done以及广播信道poor与飞机、环境和跑道协同交互。

3 最优成本可达性问题

最优成本可达性问题就是找到一个到达给定目标位置的最小花费［2，8］。由于时钟被定义为非负整数，价格转换系统可以是无限的，与价格符号状态［9］相关的成本也可能是无限的。在探索过程中，如果沿不同的路径到达相同的状态的成本不同，则丢弃更昂贵的状态。类似于时间自动机，PTA的价格符号状态通过时钟域的简单约束来表示，成本通过价格时钟域［9］上的仿射平面给出。

在PTA验证工具UPPAAL CORA中，最优成本的可达性分析使用如下所示标准分支界定算法，算法可以使用不同的搜索策略，目前有广度优先、（随机）深度优先、最佳深度优先、最佳优先和用户启发式等。

Cost记录当前已知最优成本，列表Passed和Waiting分别记录已搜索过的和待搜索的符号状态，算法迭代搜索直至没有状态需要搜索。在While循环中，根据分支策略选择未搜索状态S，如果S被已搜索状态主导或者其成本不可能更低，则跳过此状态;否则，如果S是目标状态，则得到最优成本;如果S不是目标状态，则将其所有后继加入Waiting序列并进行下一次迭代。

4 仿真分析

某机场由3条跑道组成，交通需求平均88架/h，表1给出某时间段的一组数据。以该机场为例，在 UPPAAL CORA中，将系统模型实体化，追踪模拟系统运行状况，得到多种运行轨迹。

表1 部分到港飞机数据Tab 1 Datas of partial inbound aircraft

图3给出单条跑道极限容量下1 h内对40架飞机仿真调度示意。不同长度的黑色线段代表不同类型的飞机;E0表示最优着陆时间序列，存在严重冲突;S1表示忽略环境影响时现有FCFS调度结果，各飞机的着陆时间被匀化，一旦延迟发生，将不可避免的造成后续延迟累加，平均延时约191 s;S2表示与S1对应的基于PTA的调度结果，平均延时约156 s;S1＇表示风向随机波动、环境影响参数在安全着陆范围内随机波动情况下现有FCFS调度结果，平均延时约221 s;S2＇表示与S1＇对应的基于PTA的调度结果，平均延时约169 s。

表2给出该机场24 h对2113架飞机仿真优化调度成本、延误和容量等分析结果。在不考虑和考虑环境影响2种情况下，平均延误减小幅度分别为30．22%和32．70%;跑道容量增幅分别为5．28%和6．71%;因加速、盘旋、环境等造成额外成本减幅分别为32．92%和34．28%。从该结果可以看出:在以最优成本为目标的PTA方法中，平均延时和额外成本有较大幅度下降，跑道容量也有一定的提升空间，在考虑环境影响因素情况下效果尤为显著。

图3 单跑道调度结果示意图Fig 3 Scheduling result diagram of a single runway

表2 24 h仿真调度结果分析Tab 2 Simulation scheduling results analysis in 24 h

5 结束语

针对目前飞机着陆调度方法的不足，以着陆消耗成本为目标，考虑环境因素的影响，给出了飞机着陆调度需要满足的限制条件和最优成本问题的数学描述。使用价格时间自动机作为形式化建模方法，对飞机、跑道、控制器、环境等交互实体进行建模，使用UPPAAL CORA对模型实体进行模拟分析和求解最优成本的可达性，并对某机场飞机着陆调度数据进行仿真实验和分析。为复杂环境下安全高效地进行飞机着陆调度提供了科学的建议。

［1］ Alur R，Trivedi A．Relating average and discounted costs for quantitative analysis of timed systems［C］∥The 11th ACM International Conference on Embedded Software，New York，2011．

［2］ Behrmann G，Larsen G K G，Rasmussen J I．Priced timed automata:Algorithms and applications［C］∥International Symposium Formal Methods for Components and Objects（FMCO），Berlin，Heidelberg:Springer-Vedag，2004．

［3］ Chen Shuang，Xia Xuezhi．Researches on optimal scheduling model for aircraft landing problem［C］∥2009 WASE International Conference on Information Engineering:IEEE Computer Society，2009:418-421．

［4］ 余 江，刘晓明，蒲 云．飞机着陆调度问题的MPS优化算法研究［J］．系统工程理论与实践，2004（3）:119-133．

［5］ Alur R，Dill D L．A theory of timed automata［J］．Theoretical Computer Science，1994，126:183-235．

［6］ Behrmann G，Felmker A，Hune T，et al．Minimum-cost reachability for priced timed automata［C］∥Lecture Notes in Computer Science，Berlin，Heidelberg:Springer-Verlag，2001．

［7］ 周清雷，姬莉霞，王艳梅．基于UPPAAL的实时系统模型验证［J］．计算机应用，2004，24（9）:129-131．

［8］ Behrmann G，Larsen K，Rasmussen J．Optimal scheduling using priced timed automata［C］∥ACM SIGMETRICS Perfoin’lance E-valuation Review，New York:ACM，2005．

［9］ Larsen K，Behrmann G，Brinksma E，et al．As cheap as possible:Efficient cost-optimal reachability for priced timed automata［C］∥Proc of Computer Aided Verification，2011:493-508．