基于时空特征的终端区多机场航班时刻优化

王兴隆，石宗北，纪君柔

(中国民航大学空中交通管理学院，天津 300300)

1 引言

随着我国民航业的不断发展，在航班运输量不断提高的同时，航班运行正常性的保障压力也随之增大[1]，对延误架次的控制成为了保障安全运行前提下的重要挑战。因此，为航班分配准确的离场时刻对减轻延误有着重大的意义。

目前，航班的离场过程受管制员控制，先到先服务(First Come First Served， FCFS)的理念已逐渐无法满足日益增长的航班量和复杂的终端区运行环境，在增加管制员的负担的同时也增加了航班延误成本及延误时间。有序高效的对离场航班时刻排序成为研究热点，国内外相关学者从不同的角度对离场航班时刻优化开展了大量研究。

离场航班时刻排序问题的研究主要集中于：动态调度、多跑道/多机场协同等方面[2]。Bolender[3]等在2000年对离场问题进行了基础性的研究；GUPTA[4]基于混合整数规划的离场排序策略。随着研究的深入，研究重心逐渐从单机场离场时刻优化逐渐转向了多机场协同离场放行。协同离场放行就是多个机场协同运行，统筹规划放行时刻，合理分配离场点和航线资源，使得运行效率达到最大。Atking等[5]采用遗传算法对离场航班协同放行时刻模型进行求解。Capozzi等[6]提出空域资源和离场航路动态分配的方法，优化了多机场协同离场放行问题。Chevalley等[7]将管制员管理的离场间隔工具与现有的战术离场调度工具相结合，优化多机场终端区航班协同离场问题。国内，吕双回[8]建立了终端区多机场航班协同放行模型，并采用启发式隐枚举算法求解。仇兆巨[9]基于管制运行特点建立了多机场协同离场放行策略模型，并采用禁忌搜索算法求解。程傲[10]基于多机场协同放行和机场协同决策理念提出了珠三角多机场协同放行机制，并对多机场协同放行系统进行了初步设计。通过对已有文献梳理发现：多数研究未对终端区时空特征进行考虑，即1)将每个机场视作同等地位的对象进行建模。2)未考虑不同类型离场航班延误特征不同对终端区造成影响的差异性。

本文在已有的研究基础上，兼顾机场优先级与航班延误等级，以终端区内的各机场群为对象建立总延误成本最小、总延误时间最少的多目标优化模型。并对京津大终端区两地三场进行了仿真验证。结果表明：本文所提方法可有效对多机场终端区离场时刻进行分配，在降低航班延误总时间及延误成本的同时兼顾二者之间的平衡。与先到先服务策略相比，协同排序策略有着较好的优化效果，对辅助管制员决策，提高机场及各航空公司效益，保障航班正常性等方面均有一定意义。

2 问题描述

多机场终端区是一个终端区内具有两个或者两个以上机场构成的机场群，机场间运行相互制约，相互影响，空中交通流量密集，管制运行复杂。在终端区内飞行的航班分为进场，离场以及穿越。终端区内的航班的进场、离场与穿越都需要管制员的协调与排序，避免飞行冲突，安全着陆或起飞，而多机场终端区空域资源有限，多个机场进离场资源共享，因此多机场终端区的运行约束更加复杂。机场统一离场放行的工作原理实际上是一个多元受限的排队问题，航班离场时刻分配受多种因素影响。

在多机场的离场过程中存在各机场间共用离场定位点，航线汇聚点等空域资源的情况。同时，在协同放行过程中单位时间内希望尽可能多的航班完成离场过程。因此终端区多机场协同放行问题兼具空间与时间特征。本文对终端区内不同机场所处的空间位置、功能定位、运行流量等进行考虑以满足离场放行过程中的空间特性；对不同类型航班延误时间对终端区造成的影响进行划分以更好刻画协同放行离场过程中的时间特征。

3 模型建立

设终端区内所有机场m的集合为M，机场m在研究时段内的离场航班集合为Fm。在充分考虑时空特性的基础上提出航班延误等级以及机场优先度的概念，以延误成本最小和延误总时间最少进行多目标建模。

3.1 终端区时空特性描述

3.1.1 航班延误等级划分

航班类型的差异会对机场、公司等造成不同程度的影响，顾绍康[11]根据时间和空间两个角度的评估指标建立了航班延误程度实时评估指标体系。但仅考虑数值属性指标评估延误等级，无法直观有效的判断航班延误程度。

本文同时考虑数值属性指标和类别属性指标，对延误航班进行聚类分析，将延误等级的划分过程转化为聚类过程。选取航班的延误时间、飞行时间、延误人数、航程等四个数值属性以及航空器类型、是否经停两个类别属性进行聚类分析。研究中选取的属性指标值如表1所示。

表1 航班延误等级评价指标

在聚类得出结果的基础上，采用粗糙集理论确定延误航班等级划分规则。

航班延误等级规则生成步骤如下：

1)航班延误属性数值进行离散化处理。

2)利用Johnson算法进行属性约简，将多余的属性值删除。

3)获取等价类和上下近似集。

4)生成航班延误等级的划分规则。

3.1.2 机场优先度划分

终端区内的不同机场由于飞行航线，航班流量以及机场职能偏向等原因导致不同机场相同机型的航班延误成本是不同的，因此在建立多机场协同放行机制时要进一步考虑机场优先度，本文根据所研究的多机场终端区内各个机场的运行情况分析，设定了相应的优先级因子。在本文中，机场优先度由专家综合航线数目、进驻航司数量、航班量、功能定位等因素给出。

3.2 协同离场放行模型

为简化模型复杂度，在本文中，对终端区离场过程做出如下假设：

1)多机场离场航班信息已知。

2)终端区内各机场离场容量已知，离场定位点容量已知。

3)航班不得早于航班时刻表的时间起飞。

4)假设各机场进离场分离。

建立模型所需参数及其定义如表2所示。

表2 变量定义

决策变量定义如下：

在此基础上给出本文构建模型的目标函数。

1)延误总成本最小

(1)

2)延误总时间最小

(2)

3)多目标优化函数

minf=minf1minf2

(3)

3.3 约束条件

1)离场容量约束

终端区内各机场应在单位时间内的离场航班数量满足各机场的容量限制。即集合M内的机场m在t时段的离场流量不大于该机场的离场容量，由式(4)表示

Pmt≤Dm(t)

(4)

2) 尾流间隔约束

不同类型的飞机在离场后会产生尾流，当前机与后机之间起飞不满足尾流间隔时会对后机运行产生较大的安全影响。因此从相同机场起飞的相继航班要满足不同机型的尾流间隔值，尾流间隔约束由式(5)示

(5)

3)公共离场点约束

终端区内不同机场放行的航班在经过公用的同一离场点的航班流量不大于该离场点的离场容量，该约束由式(6)表示

(6)

4) 最大位置调整约束

在排序过程中，为了保持管制员工作负荷与减少延误成本之间的平衡，本文设定航空器被优化后在队列中的位置与先到先服务队列中的位置的差异不得大于5，在对航班次序尽量少的调换基础上实现延误最小化，可由式(7)表示

ηmax≤5

(7)

5) 机场优先度因子约束

对终端区内各机场优先度进行分配，各机场优先度之和为1。由式(8)表示

(8)

6) 航班运行特性约束

为使本文模型更贴近实际情况及运行的公平性，规定离场航班在调整起飞次序之后不得早于航班计划中的离港时间。由式(9)表示

(9)

7)离场时隙约束

每个起飞航班只有一个起飞时隙，如式(10)示

(10)

4 算法实现

4.1 多目标线性递减粒子群算法(LD-MOPSO)

多目标问题往往不能确定最优值，一般得到的解对于其中一个目标是最优解而对于其它目标则不是。多目标粒子群算法(multi-objectiveparticleswarmoptimization，MOPSO)是粒子群算法解决多目标问题的一种算法[12-13]。本文提出一种惯性权重线性递减的粒子群算法(LD-PSO)对所建模型进行求解，平衡了全局和局部搜索能力，更好的提高了算法寻优性能。

4.1.1 速度与位置更新

惯性权重ω对粒子的速度变化进行控制，惯性权重ω越大，粒子的速度越大，全局搜索能力越强，惯性权重ω越小，粒子的速度也越来越小，局部搜索能力越强。惯性权重ω为设为定值时，不能动态的平衡全局和局部搜索能力，对于有多个局部极值点的函数，容易陷入到局部极值，增大结果误差。

多目标粒子群优化的速度与位置更新方法如式(11)和式(12)所示，线性权值递减公式如式(13)示

vi，j(k+1)=ωvi，j(k)+c1r1(pbesti，j(k)-xi，j(k))

+c2r2(gbesti，j(k)-xi，j(k))

(11)

xi，j(k+1)=xi，j+vi，j(k+1)

(12)

(13)

i=1，2，…，N，j=1，2，…，n

4.1.2 外部集更新策略

外部集更新步骤如下：

Step1：算法开始时，将非支配集中的较优个体先存储进外部集内；

Step2：当外部集里有粒子时，任意选取非支配解的某一个个体，假设为i，利用支配关系，依次判断外部集中所有个体与该个体i，若结果是i被支配，则将i从外部集中删除；若i不被任一个体支配或者i支配外部集中某一个或多个个体，则将i存入外部集，且将被支配的所有个体从外部集中删除；

Step3：循环，直至算法完毕。

4.1.3 个体极值与全局极值选取

1)将当前粒子位置(即新解)与当前pbest进行比较，如果新的解支配了当前pbest，则新解作为新的pbest；如果新解和当前pbest彼此不被对方支配，则从二者随机选择一个作为新的pbest。

2)从外部集的非支配解中随机选择一个解作为粒子的全局极值。

4.2 模型求解

对所提模型的多目标求解算法流程如下，算法示意图如图1所示。

图1 基于多目标粒子群的模型求解流程图

Step1：读取终端区内各个机场航班信息、机场容量信息、确定所选时段内终端区离场定位点容量以及不同机型航班在终端区内标准飞行时间，根据各个机场所选时段的航班流量确定机场优先级因子，所选时段多机场终端区内所有离场航班为粒子群P。

Step2：根据离场航班计划时刻表结合尾流间隔利用先到先服务策略确定离场航班的初始起飞顺序、起飞时间和过点时间。以航班初始起飞顺序作为粒子。

Step3：初始化粒子群P，粒子位置x和粒子速度v；计算每个延误程度评价指标，由制航班延误等级划分，确定航班延误等级损失系数g，计算每个粒子适应度值。

Step4：按照Pareto支配关系要求，将非支配集中较优个体存储进外部集中，从非支配集中选取群体极值gbest；

Step5：更新粒子的速度和位置，计算所有粒子新的适应度值。更新外部集，更新个体极值pbest和群体极值gbest；

Step6：达到迭代次数停止，否则返回Step4。

5 实例验证

随着大兴机场的投入运营，京津地区两地三场的终端区运营模式逐渐成为具有代表性的多终端区空域系统。本节将新开航的大兴机场纳入研究范围，以天津、北京两地三场的大终端区运行情况为背景进行仿真验证。大兴机场开航后的终端区空域结构如图2所示。

图2 京津地区终端区空域结构示意图

5.1 参数选取

选取某大型枢纽机场一月份的4557条延误航班数据作为样本进行航班延误等级划分，经过k-prototype聚类及粗糙集划分后得出的延误等级如表3所示。

表3 航班延误等级划分规则表

京津终端区共包含北京首都机场、北京大兴机场、天津滨海机场等两地三场，其中北京大兴国际机场运营航司15家，航线量144条；天津滨海国际机场至今，运营航司47家，航线量达205条。本文结合实际情况及专家评分设定优先因子，首都机场为0.5，天津机场为0.2，大兴机场为0.3。

以大兴开航后繁忙时刻京津终端区8：00至8：30内首都机场，大兴机场和天津滨海机场的100架次离场航班为例，在考虑时空特征的前提下，从航班延误时间、航班延误成本两方面统筹安排多机场航班协同放行时刻。

假设天津机场最大容量为12架次/15分钟，北京机场最大容量为20架次/15分钟，大兴机场最大容量为30架次/15分钟，各个离场点最大可用容量为5架次/10分钟。结合本文实际问题，设置种群大小为300，最大粒子迭代次数为300代c1=0.5，c2=0.7。假设同延误等级的航班单位时间延误成本如表4所示，不同机型起飞尾流间隔标准规定如表5所示，大兴机场开航后，大兴机场及其它两机场计划航班时刻表如表6所示。

表4 单位时间延误成本

表5 航空器起飞尾流间隔标准规定

表6 8∶00-8∶30计划航班时刻表

5.2 仿真结果分析

当算法最后到达所设置的停止代数时，Pareto最优前沿图如图3所示，选取一组延误成本与延误时间相对平衡的Pareto解，图4为一组Pareto解计划与实际对比图。

图3 Pareto最优前沿图

图4 一组Pareto解计划与实际对比图

表7 不同机场延误成本与延误时间

表7为基于一组Pareto解得到的不同机场延误成本与延误时间。表8为不同角度下延误时间与延误成本对比。由表9可得航班总延误成本为72200元，航班总延误时间为3982分钟。由表8可得，Pareto一组得到的延误成本较基于延误成本角度增加0.32%，较基于延误时间角度降低了1.23%，得到的延误时间较基于延误成本角度降低了2.3%，较基于延误时间角度增加了4.1%。上述结果表明，多目标优化结果更好的平衡了总延误成本与总延误时间，从而避免单一优化一个目标函数而牺牲另一个目标函数，更加的符合实际放行运行情况，验证了模型的有效性。同时，相比于先到先服务策略，本文所提方法在延误成本和延误时间方面分别减少了22.3%和17.5%，证明了本文所提方法的有效性。

表8 不同目标对比

6 结论

本文主要对基于时空特性的多机场终端区基于机场优先级的协同放行问题进行了研究，考虑延误分级以及机场优先度，建立了以航班总延误成本和总延误时间最小化的多目标函数，构造考虑延误分级下基于机场优先级的多机场协同放行模型，并采用多目标线性递减粒子算法对模型进行求解，然后通过京津终端区新增大兴机场的情况下的算例进行仿真分析，最后分别求得基于最小延误时间，基于最小延误成本以及同时考虑延误时间和延误成本的多机场协同放行策略，通过分析对比，验证了模型的有效性，从而为多机场终端区构建统一协同放行机制提供了理论方法和科学依据。