基于航空器优先级的场面航空器动态滑行优化*

贾 媛 姜 雨 徐 成 蔡梦婷

(南京航空航天大学民航学院 南京 211106)

0 引 言

近年来，我国航空运输业发展迅速，机场枢纽化趋势日益明显，航空运输系统的运行和管理压力与日俱增.针对航班延误和机场拥堵现象日益严重的现状，提高机场场面资源的运行效率，增加场面容量已经迫在眉睫.

目前国内外学者对航空器场面滑行优化的研究主要分为静态和动态两个方面.在航空器静态场面滑行优化方面，利用混合整数线性规划(MILP)方法[1]、遗传算法(GA)[2]、改进的A*算法[3]等智能算法，得到基于固定路径的滑行路径优化序列.在航空器动态场面滑行优化方面，一部分学者通过利用复杂网络[4]、遗传算法[5]、元胞自动机(CA)[6]、改进的粒子群算法(CPSO)[7]、主动路由选择(AR)[8]、混合整数规划(MIP)方法[9-10]、改进的蚁群算法[11]、多目标免疫优化算法[12]等智能算法，对航空器场面滑行进行动态优化；另一部分学者对模型进行改进，例如，建立跑道和滑行道联合调度的集成优化模型[13]，建立多目标多分枝的航空器场面滑行优化模型[14-15]等.

纵观国内外研究成果，学者们已经从滑行效率和安全两个角度进行航空器动态滑行优化研究，并取得一定成果.但是随着研究的深入，航空器属性，尤其是航空器优先级，越来越成为影响滑行效率和安全的关键因素.因此，如何从优先级角度出发，提高航空器滑行效率和安全，降低场面拥堵，缓解运行压力已经势在必行.

本文以最小化所有进离场航空器运行成本为目标，建立基于航空器优先级的场面航空器动态滑行优化模型.探讨航空器优先级的确定方法，设计滑行冲突解决策略，引入滚动时域方法进行求解.使用MATLAB仿真平台，验证该优化方案的可行性和有效性.

1 基于航空器优先级的滑行冲突解决策略

1.1 航空器优先级的确定

航空器优先级的确定考虑三个因素：时间优先、机型优先、延误优先.三种优先级的高低顺序分别为：时间优先>机型优先>延误优先.

“时间优先”是指根据航班时刻表，预计起飞时间早的航空器比预计起飞时间晚的航空器具有优先级.这样设定优先级，原因为：①航班时刻表相对固定，为保证旅客权益，以及考虑到旅客的满意度，一般不允许航空器提前起飞而造成旅客误机；②不同的航班属于不同的航空公司，不能仅凭机型来决定由哪家航空公司来承担延误损失，考虑到航空公司之间的公平性，只有按照航班时刻表才能保证相对公正，毕竟航班时刻表是各航空公司、空管单位和其他相关部门之间利益平衡的结果.

“机型优先”是指根据《国际民用航空公约》的相关规定和场面航空器运行的实际情况，航空器优先级的确定是由航空器的属性(如专机、故障机、货机等)、机型成本率、载客数、平均耗油率等参数决定.“机型成本率”主要由该机型载客数和平均耗油率这两项主要性能指标确定.“载客数”是估计该机型单位时间内旅客地面等待成本的重要参数，“平均耗油率”是估计该机型在发动机工作时运行成本的重要参数.其他一些因素，如公司信誉、人员工作负荷、飞机维护成本等，可以将其折算到单位乘客等待成本或者航油价格中去.

“延误优先”是指延误航班的优先级低于正常航班的优先级，其中“延误航班”是指在航班时刻表预定的起飞时间15 min后还未能起飞的航班.同时，在所有延误航班内部仍然按照时间优先和机型优先顺序来确定各航空器的优先级.

1.2 航空器滑行冲突解决策略

本文提出的冲突解决策略是通过判断冲突航空器的优先级，优先级高的航空器可以按原计划路径直接通过冲突区域，按原路径继续滑行；优先级低的航空器有两种滑行方案可选：①进入冲突区域前减速等待；②提前选择次优可替代滑行路径(一条不经过冲突区域且到达终点的最短路径).

设航空器的优先级为p，航空器选择减速等待的最短等待时间为Δt，航空器单位时间滑行成本与单位时间等待成本之比为λ，最短滑行路径与次优可替代滑行路径的长度之差为替代成本Δc，平均滑行速度为v.分别计算两种滑行方案的滑行时间成本：①进入冲突区域前减速等待，将最短等待时间Δt乘以滑行成本与等待成本之比λ，转换为滑行时间成本λΔt；②提前选择次优可替代滑行路径，将替代成本Δc除以滑行速度v，转换为滑行时间成本Δc/v.将Δc/v与λΔt进行比较，选择较小的滑行时间成本，进而选择合理的冲突解决策略，实现所有进离场航空器无冲突滑行且运行成本最小化的目标.当滑行冲突无法通过减速等待或选择次优可替代滑行路径解决时，即发生死锁状况.当发生死锁时，可不严格执行优先级策略，临时交换航空器的优先级，再按相应的冲突解决方法来解决冲突.冲突解决之后，恢复航空器各自的优先级.

2 基于航空器优先级及滑行冲突解决策略的滑行优化模型

2.1 模型假设

1) 航空器匀速滑行，并且速度不能超过机场规定的最大速度55 km/h.

2) 航空器间距符合规定的最小安全间距20 s.

3) 进离场航空器滑行路径连续.

4) 在研究时段内，所有进离场航空器相关信息、标准坐席数、滑行油耗等信息己知.

5) 航空器滑行优化动态连续，本文只研究某一时段T内所有航空器的滑行优化.

2.2 定义符号及变量

2.3 目标函数

(1)

式中：Z1为滑行距离目标函数；Z2为滑行等待时间目标函数；pi

当λiΔti>Δci/ti时，低优先级航空器fi选择次优可替代滑行路径，绕过冲突区域，考虑其增加的滑行距离，滑行成本目标函数Z转化为滑行距离目标函数Z1，最小化研究时段内所有进离场航空器的滑行距离，其表达式为

(2)

当λiΔti<Δci/ti时，低优先级航空器fi选择减速等待，考虑其增加的滑行等待时间，滑行成本目标函数Z转化为滑行等待时间目标函数Z2，最小化研究时段内所有进离场航空器的滑行等待时间，其表达式为

(3)

式中：(Tidi-TBTi)为航空器fi从最早可开始滑行时间起到达目的地所花费的实际时间；(tidi-tioi)为航空器fi从最早可开始滑行时间起到达目的地无冲突滑行的最短时间.

2.4 约束条件

∀fi∈F,∀np,nq∈N

(4)

∀p,q,s∈N

(5)

∀p,q∈N

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

式(4)为滑行路径需符合滑行道容量要求，满足物理链接性；式(5)为滑行路径需连续可行，满足流动平衡性；式(6)为滑行速度约束；式(7)为安全间隔约束.式(8)～(9)为对头冲突约束.式(10)～(11)为超越冲突约束.式(12)为高优先级航空器优先滑行的调度原则.式(13)为所有航空器要在开始滑行时间之后才能开始滑行.

3 基于滚动时域的模型求解过程

滚动时域方法是一种时间分解法，将一个全局大规模优化问题分解为一系列相关联的小规模优化子问题，计算复杂度大大降低，且子问题部分利用全局信息，调度质量明显提高[16].基于滚动时域的航空器场面动态滑行优化模型求解过程如下：

步骤1设调度开始时刻为t0，则ti=t0.

步骤2设在ti时刻，预测时域为Γ，选择调度时域[ti,ti+Γ]内将要开始滑行和正在滑行的航空器组成预测窗口，实时更新航空器的动态信息.

步骤3获取航空器信息，根据Dijkstra最短路算法，求出预测窗口内各航空器的理想滑行路径.

步骤4在计划时域窗口T内形成滑行调度子问题.子问题的目标函数和约束条件同原问题，除新加入的航空器外，还包括上一计划时域窗口未完成滑行的航空器，其开始滑行时间和地点为上一计划时域结束时的状态.

步骤5确定滚动窗口长度m，完成调度的航空器数量n，进行迭代滚动.在滚动窗口内航空器按照其理想滑行路径滑行，若遇到冲突，则冲突解决策略确定等待时间或其他滑行路径.直到该计划时域窗口航空器数量不足n时，结束当前调度.

步骤6ti+1=ti+T，i=i+1，若ti<Γ，转步骤2，否则求解结束.

4 仿真算例

选取我国某大型机场作为研究对象，为方便起见，选取该机场西半区域，将多个相邻停机位抽象成三个集中停机区G1、G2和G3，去掉一些无关滑行道和节点，形成包含37个节点、48条边、2条跑道和3个集中停机区的网络图，见图1.

图1 我国某大型机场西半区域滑行道系统部分构型图

航空器数据选取该机场2016年7月某天08:00-08:15内的高峰小时航班数据，见表1.

表1 我国某大型机场研究时段内进离场航空器相关信息

本文使用滚动时域方法求解模型时，具体参数设置如下：高峰时段内预测窗口航空器数量为16架，计划时域窗口T为3 min，即180 s，由Dijkstra最短路径算法求得的航空器理想滑行路径集可知，最后一架航空器完成调度的时间是1 094 s，|1 094/180|=7(向上取整)，则共有7个调度时域窗口，形成7个调度子问题.求解这7个调度子问题，得出在基于理想滑行路径的调度方案下，航空器冲突点的总个数为11个，共有6对航空器发生冲突.本文的算法设计就是建立在理想调度的基础上，通过基于航空器优先级的冲突解决策略动态处理滑行冲突，以此保证航空器滑行安全并最小化滑行成本.

4.1 仿真结果分析

通过采用滚动时域方法，对研究时段内的16架航空器进行基于航空器优先级的场面滑行优化仿真.优化后的滑行路径集避免了11处滑行冲突.为体现本文优化算法的优越性，增加基于先到先服务(FCFS)的固定路径下的调度结果作为比较，调度结果对比见图2.

图2 基于FCFS与基于优先级调度结果对比图

分别比较基于理想滑行路径、基于FCFS的固定路径滑行和基于航空器优先级的动态路径滑行的总等待时间、总滑行距离、总替代成本和冲突数，结果见表2.

表2 三种不同优化方案的结果对比

综合比较三种方案的优化结果，在理想滑行路径的优化方案下，各航空器选择最短滑行路径到达其终点，过程中无需等待，但这必然造成滑行冲突.在本仿真中，冲突点的总个数为11个.而在实际滑行过程中，不允许有滑行冲突点存在.虽然后两种优化方案都能解决滑行冲突问题，但是付出的代价却不同.

由图2和表2可知， 基于航空器优先级的动态路径滑行方法的结果显著优于基于FCFS的固定路径滑行方法，这是因为前者可以通过运行冲突解决机制，令优先级较低的航空器选取次优可替代滑行路径，或者减速等待来规避冲突，并选取成本较低的方法完成滑行；而后者无法选择较短路径，只能通过减速等待方式避免冲突，所以无论是在滑行路径长度上还是在等待时间上，基于航空器优先级的动态路径滑行方法都优于基于FCFS的固定路径滑行方法.

4.2 优先级保障分析

在航空器的滑行过程和冲突解决过程中，都必须考虑航空器的优先级，本文提出的基于航空器优先级的动态滑行优化算法能够确保当发生滑行冲突时，优先保障优先级高的航空器的滑行，见表3.

由表3得知，当发生滑行冲突时，在基于航空器优先级的优化方法下，保障了所有优先级高的航空器的优先权.而FCFS方法根据到达时间调度，只有航空器3,15,14在遇到滑行冲突时是因其先到达滑行区域而优先滑行的，并不能保障优先级高的航空器能够优先滑行.故本文提出的基于航空器优先级的优化能够保证优先级高的航空器优先滑行，符合实际情况.

表3 航空器优先级保障

4.3 冲突解决策略过程分析

在冲突方面，若所有航空器采用理想滑行路径滑行，将存在11个冲突点，采用基于FCFS的固定路径滑行和基于航空器优先级的动态路径滑行都不存在冲突点，但是其解决冲突的方式有所差异.

图3为超越冲突解决策略过程分析图，由图3可知，当提前检测到航空器3和航空器4在滑行道(4,3)段发生超越冲突时，基于FCFS的固定路径滑行方法是令后机(航空器3)降低滑行速度，不改变其原来的滑行路径，跟随前机，增加了后机的等待时间.而基于航空器优先级的动态路径滑行方法是令后机提前在节点6处选择次优可替代滑行路径6-7-5-2通过冲突区域，到达滑行终点.有效避免滑行冲突，无需进行等待，不增加滑行距离.

图3 超越冲突解决策略过程分析图

图4为交叉点冲突解决策略过程分析图，由图4可知，当提前检测到航空器14跟航空器16在节点14处将发生交叉点冲突时，基于FCFS的固定路径滑行方法是令后到达的航空器16在到达节点14前等待18.2 s，以使两架航空器满足最小安全间隔要求.而基于航空器优先级的动态路径滑行方法是令航空器16提前在节点15处选择次优可替代路径15-16-17通过冲突区域，绕行距离160 m，用时13.3 s，小于18.2 s，由此可见本文动态滑行的优越性.

图4 交叉点冲突解决策略过程分析图

本文基于航空器优先级的动态路径冲突解决策略明显优于基于FCFS的固定路径冲突解决策略，主要区别在于后者仅考虑到前后两架航空器到达冲突区域(滑行道节点或路段)时间顺序，令先到达冲突区域的航空器优先通过，而没有考虑到航空器的机型、任务性质、突发状况等方面，这不符合场面实际运行情况，不利于航空公司控制运行成本，也不利于机场提高场面运行效率.而本文提出的基于航空器优先级的动态路径冲突解决策略克服了FCFS方法的种种缺点，可以有效缓解大型枢纽机场场面运行效率无法满足实际运行需求的现状，增加场面容量.

5 结 束 语

本文结合准确的机场场面网络结构，以最小化研究时段内所有进离场航空器滑行成本为目标，建立基于航空器优先级的大型机场场面航空器动态滑行优化模型，探讨了场面滑行优化中航空器优先级的确定方法，提出基于航空器优先级的滑行冲突解决策略，在保证航空器优先级和滑行安全的前提下最小化滑行成本，为大型机场场面航空器的动态滑行提供符合实际运行情况的优化理论与方法.

在此研究基础上，未来可进一步考虑航空公司间的公平性、航空器碳排放等因素，对大型机场场面航空器动态滑行进行更深层次的研究.

参考文献

[1] SMELTINK J W, SOOMER M J, WAAL P R D, et al. An optimisation model for airport taxi scheduling [J]. Mathematical Problems in Engineering,2008(1):55-58.

[2] DEAU R, GOTTELAND J B, DURAND N. Airport surface management and runways scheduling[J]. Transportation Research Part C: Emerging Technologies ,2009(2):478-482.

[3] ZHOU H, JIANG X. Research on taxiway path optimization based on conflict detection [J]. Plos One, 2014,10(7):897-901.

[4] LANDRY S J, CHEN X W, NOF S Y. A decision support methodology for dynamic taxiway and runway conflict prevention[J]. Decision Support Systems, 2013,55(1):165-174.

[5] JIANG Y, LIAO Z, ZHANG H. A collaborative optimization model for ground taxi based on aircraft priority[J]. Mathematical Problems in Engineering, 2013(2):1-9.

[6] MORI R. Aircraft ground-taxiing model for congested airport using cellular automata[J]. Intelligent Transportation Systems, IEEE Transactions on, 2013,14(1):180-188.

[7] JINGNAN Z. Airport taxi scheduling strategy based on particle swarm optimization algorithm[J]. 2014.

[8] WEISZER M, CHEN J, STEWART P. A real-time active routing approach via a database for airport surface movement[J]. Transportation Research Part C: Emerging Technologies, 2015,58:127-145.

[9] GUÉPET J, BRIANT O, GAYON J P, et al. The aircraft ground routing problem: analysis of industry punctuality indicators in a sustainable perspective[J]. European Journal of Operational Research, 2016,248(3):827-839.

[10] 张天慈,丁萌,左洪福,等.基于区域控制的航空器滑行轨迹优化模型[J].系统工程与电子技术,2016,38(1):136-141.

[11] 高加凯.基于广州白云机场平行跑道航空器滑行路径优化研究[D].德阳:中国民用航空飞行学院,2017.

[12] 王湛,熊佳俊,陈浩.航空器场面滑行速度与油耗研究[J].武汉理工大学学报(交通科学与工程版),2017,41(3):391-394.

[13] YU C. Integrated optimization of airport taxiway and runway scheduling[J]. Journal of Automation and Control Engineering ,2014(4):578-586.

[14] RAVIZZA S, CHEN J, ATKIN J A D, et al. Aircraft taxi time prediction: Comparisons and insights[J]. Applied Soft Computing, 2014,14:397-406.

[15] CHEN J, WEISZER M, ATKIN J, et al. A heuristic approach to greener airport ground movement[J]. European Journal of Operational Research,2014(3):587-596.

[16] 王冰.滚动时域调度方法及其性能分析研究[D].上海：上海交通大学,2005.