航路资源协同分配的多目标优化方法研究

杨 帆，田 文，宋津津

(南京航空航天大学国家空管飞行流量管理技术重点实验室，江苏 南京 210016)

1 引言

协同航迹选择程序(Collaborative Trajectory Options Program，CTOP)是在协同决策(Collaborative Decision Making，CDM)程序的基础上提出的一种新交通管理预案(Traffic Management Initiative，TMI)，用于解决航线和终端空域需求与容量不平衡问题[1]。CTOP的特点在于通过考虑空域使用者的飞行偏好需求，使航空公司参与到航路资源分配的决策中，减少非必要的空中延误。这实现了空域在受限情况下尽可能地高效运行的同时更降低了航空公司的延误成本。CTOP的关键在于航路网络资源(航迹、时隙)高效、公平、合理的分配，因此研究高效科学的时隙航迹资源协同分配方法具有重大意义。

目前对航路网络资源协同分配的研究已取得了较为显著的成果：Andrew等在线性模型的基础上考虑了容量的不确定性，使航路资源分配更合理[2]；杨赛等建立的扇区时隙资源分配模型，降低了航班延误损失，提升了扇区使用效率[3]；Kim等对比分析了四种典型资源分配方案，提出了考虑航空公司偏好信息的航路资源分配有效性评估模型[4]；Cruiciol等提出了在发起CTOP的条件下改进单局决策过程的单人博弈论方法，使航空公司延误相对减少[5]；Rodionova等建立了一种基于线性优化的航班调度方法，显著降低了确定性条件下的航班总延误[6]。

上述成果分别从资源分配的有效性、公平性、可靠性等角度出发，提出了符合空中交通管制部门、航空公司等各方利益的分配理论模型与算法，但较少考虑多角度资源分配条件的均衡性满足问题。因此本文基于有效性、效率性[7]和公平性多角度建立了基于多目标遗传算法的时隙航迹协同分配方法[8]，旨在将多方对航路网络资源分配需求转化为共同的优化目标函数。

2 模型描述

2.1 问题描述与基本假设

当航路拥堵或天气恶劣导致空域容量下降时，会导致航路上出现流量受限区(Flow Constrained Area，FCA)，随后空中交通管制部门发起CTOP，航空公司收到CTOP后将受影响的航班的飞行偏好提交给空中交通管制部门。空中交通管制部门根据接受的各航班飞行偏好为其分配时隙航迹资源，从而尽可能地降低飞行延误，维持空域运行。如图1所示，点A和点B为航路点，两点之间有两条航迹选项，箭头方向为航班飞行方向。本文基于两条航迹选项建模，包括原计划航迹选项和改航航迹选项，两条航迹上各有一个流量受限区，而每架受影响航班都有航迹选项1和航迹选项2两种选择。

图1 航迹选项示例

在CTOP程序的启用时间内，根据流量受限区内的容量限制和划定时隙建模。模型满足两个目标：效率性目标：确保受影响航班的延误成本最低；公平性目标：使得各航空公司间的延误成本分配趋于平等。在满足效率性和公平性目标的前提下，为各受影响航班分配航迹与时隙，该模型成立应建立以下假设条件：

1)所有受影响航班均接受CTOP的调配，且各航班的航迹偏好选项与航班信息公开；

2)流量受限区的范围及其容量已知；

3)各FCA内可用的时隙资源已划定；

4)所有受影响航班至少提交一条航迹选项。

2.2 模型参数设定

基于上述描述进行数学建模，并引入以下变量：

I：受影响的所有航班集合，i∈I；

J：航迹集合，j∈J={1，2}；

S：时隙集合，s∈S；

tij：受影响航班i被分配至航迹j的时隙集合；

δij：二元变量，1表示航班i有提交航迹选项j，0表示没有；

A：航空公司a的集合，a∈A，card(A)=3；

Ia：航空公司a的航班i集合，i∈Ia；

α：地面延误成本系数；

β：空中延误成本系数(一般取2α=β)；

eij：受影响航班i提交的进入航迹选项j内FCA的时间；

τi：受影响航班i提交的所有航迹中最早进入FCA的时间；

cij：受影响航班i选择航迹选项j的附加航程时间成本；

Fj：航迹选项j内FCA的容量限制；

μij：受影响航班i选择航迹选项j时的不确定性成本；

ni：受影响航班i的乘客数量。

2.3 模型建立

本文旨在解决拥堵空域内的时隙航迹分配问题，为降低算法复杂性，假设每一个FCA区域只含有一条航路，进而将原有的时隙航迹分配问题转化为时隙分配问题。时隙分配兼具有效性、效率性和公平性三个属性。有效性是模型成立的基础，表示问题的约束条件。效率性和公平性是模型建立的目标，旨在通过同时满足效率性和公平性使问题得到优化。然而事实上，效率与公平通常是对立的，无法使两者同时达到性能最优。因此，本文考虑建立多目标优化模型，最大程度地兼顾效率性与公平性，使得航路资源分配更加均衡合理，优化目标包括：

1)系统效率性：航班延误不仅会对航空公司带来巨大的经济损失，更会造成旅客时间成本的损失。因此应该尽量减少所有受影响航班的总延误，满足效率性的目标。

2)系统公平性：由于在CTOP的发起时间内，各航空公司受影响航班的数量不同，所载旅客也不同，各航路资源分配方案造成的各航空公司延误也不同。为了使各航空公司都愿意加入CTOP，服从调配，必须要使系统分配方案具有公平性，即分配延误趋于相等。

2.3.1 系统效率性

第一个目标为使目标函数的效率最高，即令系统的总延误成本最低

目标函数

(1)

约束条件

tij≥eij·δij;∀i，i∈I;∀j，j∈J

(2)

(3)

(4)

(5)

(6)

(7)

在上述模型中，式(1)为目标函数，共分为三个部分：第一部分为航班被分配至航迹选项内FCA所造成的地面等待延误；第二部分为航班更改航路造成的空中延误成本；第三部分是受影响航班的随机延误成本，服从(0，σ2)正太分布；式(2)规定航班被分配的时隙必须在该航班提交的进入该航迹选项FCA的时间之后；式(3)规定各受影响航班只能被分配至一个时隙；式(4)规定各时隙内最多进入一架受影响航班；式(5)规定只有航班选择该航迹选项，其才可以被分配至该航迹选项内的FCA时隙中；式(6)规定了各FCA的容量限制；式(7)规定受影响航班的排序按照各航班最早进入FCA的时间进行排序。

2.3.2 系统公平性

第二个目标即解决各个航空公司之间的公平性问题。公平性体现在受限空域内，所有空域使用者所分配的空域资源平等，损失成本平等。公平损失偏差系数可以反映资源分配的公平性程度，因此，本文采用各航空公司之间资源分配的公平损失偏差系数来体现系统公平性。公平损失偏差系数可以理解为资源分配的基尼系数，即反映资源分配的公平性，其值位于[0，1]区间，系数越小，则表示分配越公平。

目标函数

(8)

式中Pa为航空公司a的总延误成本

(9)

qa表示航空公司a的当量航班量与总当量航班量之比，当量航班量是指将所有航班按照某种性质统一换算成的航班数总量。由于在受限空域内，各航空公司的航班数不同，采用延误时间等方法无法准确比较各航空公司之间航班的性质。因此，就需要引入当量航班量来充分比较各航空公司在延误分配过程中所占比例。当量航班量越大，则该航空公司的受影响航班被分配的延误成本也就越大。

(10)

式中：ωi表示当量航班量。本文采用各航班的平均乘客数量作为同一性质换算各航空公司的当量航班量。因此，qa即可表示为航空公司a的乘客的延误与所有受影响航班乘客的总延误成本之比。

3 时隙航迹协同分配的多目标遗传算法

3.1 多目标遗传算法

遗传算法通过模拟生物遗传进化的过程，不断进化搜索更优子代，从而获得最优解，其在解决多目标优化问题时有较好的适用性。多目标遗传算法的结果是一群不具有相互支配关系的最优解集，称为近似Pareto最优解集，决策者可以根据问题的实际情况以及参与者的需求确定最满意的最优解[9]。本研究针对某空域内的时隙航迹分配问题，选取NSGA-II(Non-dominated Sorting Genetic Algorithm II)算法进行求解。该算法具有适值分配、保持种群多样性和防止优秀个体流失等优点，综合考虑了不同航空公司、不同载客人数、不同航迹选项的延误成本，使受限空域以最高效的效率运行的同时满足航空公司对所分配延误相对均衡合理的要求，从而在解决时隙航迹协同分配的问题的同时保证了 Pareto 最优解集的可靠性和准确性。

3.2 算法设计

1)编码设计

本文采用了一条染色体中各基因数不会出现重复数的排列编码法。一条染色体代表一种时隙航迹分配的结果；染色体长度表示受影响航班的总架数，染色体内每个基因位置表示各航班选择的航迹与时隙编号。染色体基因编码实例如图2所示。各基因数所对应的选择方案见表1。

图2 染色体基因编码实例图

表1 染色体基因选择方案

2)适应度函数确定

由目标函数，定义每条染色体有2个适应度函数：

(11)

(12)

3)遗传操作

选择算子：采用二元锦标赛算子，该算子会对每代种群有放回地抽取并选择最优个体，从而确保问题在搜索过程中，每一代的最优个体向子代遗传，使解集不断收敛。

交叉算子和变异算子：采用部分匹配交叉算子(Partial-Mapped Crossover)和多项式变异算子进行交叉、变异操作。以确保染色体在各组基因交叉变异时始终不会产生冲突基因，形成新的一对可行的子代基因。

4)算法步骤

具体算法实施流程如图3所示。

图3 算法流程图

4 实例分析

本文基于南中国海地区三亚情报区历史运行数据进行实例分析，拥有两条航迹选项的航路在某日19时至20时预计飞越航班共23架，受恶劣天气影响，两条航迹选项各生成一个流量受限区。航路的相关信息如航迹性质、容量及延误成本见表2所示。空中管制部门发布的航迹可用时隙信息见表3。空中交通管制部门在收到各航空公司受影响航班的具体信息和偏好需求后，将会为其分配航迹与时隙资源。所有受影响航班的详细信息以及飞行偏好如表4所示。

表2 航路相关信息

表3 可用时隙信息

表4 航班信息表

通过上述数据基于Python的Geatpy2平台运行多目标遗传算法，取种群规模为50，最大进化代数为200，交叉概率设为0.9，变异概率为0.2。求得的帕累托最优解集如图4所示。

图4 帕累托最优前沿

从图中可以看出，该算法的求解结果较好地描绘了帕累托解集的最优前沿，符合效率性与公平性的对立关系。最优Pareto解集中共有6组解，6组染色体如表5所示，对应的延误值与公平系数见表6。

表5 帕累托解集染色体

表6 帕累托解集函数值

将经多目标优化后得出的最优帕累托解集各方案的结果与传统的按时刻表分配(Ration-by-schedule，RBS)算法结果比较分析。经计算，RBS方案的总延误成本为303.55分钟，公平损失偏差系数为0.0678。两种算法结果对比如表7所示，帕累托解集各方案与RBS算法结果的对比如图5所示。

表7 解集方案与RBS方案对比

图5 解集方案与RBS结果比较图

根据表7的对比分析可知，基于多目标遗传算法求解的帕累托解集的结果比RBS算法有较大的提升，其平均延误成本降低了8.5%，平均公平损失偏差系数降低了70.6%，效果较好，验证了NSGA-II算法的可行性。该算法为空中交通管制部门提供了诸多选择，空中交通管制部门的决策可以根据空域的实际情况选择最终时隙航迹分配方案。

5 结束语

本文建立了基于效率性与公平性的时隙航迹协同分配的多目标优化方案。在CTOP的条件下，结合航空公司的航迹选项偏好，通过多目标遗传(NSGA-II)算法，实现了减少航班总延误以及航空公司平均延误趋于公平的两个最优目标。实验结果表明，采用的多目标遗传算法可以高效的求解航路资源协同分配的问题，且与传统的RBS算法相比效率与公平性都有很大的改善。决策者可以根据实际需求选择最终的分配方案。在此基础上，可以通过增加更多航路运行条件，使模型考虑更为全面，进一步提高空域运行效率。