汇聚航路航班排序的遗传算法研究

赵嶷飞　王惠斌（中国民航大学空管学院，天津 300300）

汇聚航路航班排序的遗传算法研究

赵嶷飞王惠斌
（中国民航大学空管学院，天津 300300）

基于汇聚航路的特点，结合区域流量控制的实际情况，建立了汇聚航路航班排序模型，并设计了相应的遗传算法。在模型中提出了多路编码算法，并对交叉算子和变异算子进行了改进，提高了算法的求解性能。解决了在流量控制情况下，汇聚航路上的航班排序问题。最后对算法进行了仿真验证。结果表明，该遗传算法在较快求得全局最优解的前提下，能有效减小汇聚航路航班的空中延误。

航班排序 遗传算法 流量控制

随着民航运输量的迅速增长，航班量的不断增大，由于有限的空域资源而导致的流量控制次数和时长也在不断地增加。如何有效地解决由于流量控制原因而导致的空中航班延误成为当务之急。流量控制通常是由于某一区域，机场或航路点的容量下降而产生的。常见的控制形式有点控制和区域控制。控制的方式多为限制飞机以一定的时间间隔或者距离间隔通过某一航路点。然而无论采用那种方式都会对实施流量控制所在航路点的上游航班造成影响，随着延误的传播，往往还会对相邻管制区的航班造成影响。解决这一问题的方法有两种：（1）通过合理的设置流量控制值来减少航班的空中延误。（2）通过合理的航班排序来减少航班的空中延误。本文主要针对第二种方法进行研究。

而以往的航班排序问题多是针对终端区航班排序或是地面等待问题的航班排序，对由于流量控制原因导致的航路上飞行的航班延误排序的研究却较少。然而传统的航班排序算法又并不适合此问题的求解，而且运行效率较低，收敛速度较慢。因此本文对解决传统排序问题遗传算法进行了改进，并针对汇聚航路的特点提出了多路编码的编码方式，根据流量控制的实际情况，进行了建模。本文的结构如下：首先对流量控制点上游的航路特点进行了分析，提出了汇聚航路航班排序模型，其次，对传统的遗传算法进行了改进，最后，对算法进行了仿真，并与传统的排序算法进行了比较，证明了算法的有效性。

1　问题描述

图1　汇聚航路结构示意图

图2　三条航路汇聚示意图

飞往流量控制点的航班通常经由多条汇聚于流量控制点的航路到达，如图1所示。图中A点为流量控制点，1-N对应了汇聚于A点的N条航路，其中2，3航路的航班汇聚于B后再飞往A点，4，5航路的航班汇聚于C点后再飞往A点。对下游实施流量控制往往会对上游的航班造成延误影响，如果延误过大，超出了流量控制点所在管制区对延误的吸收能力，延误将会沿着航路向上游管制区传播。这时如何合理的对空中航班进行排序，减少空中的延误显得尤为重要。管制区对飞行中的航班延误，多采用雷达引导，调速，空中等待等方式进行处理。而空中等待不仅十分耗油，需要较大的空域进行实施，而且会增加管制员的工作负荷，因此对航路上飞行航班的排序时，在保证航班总延误最小的情况下，还要尽量减少航班空中的等待的发生。

2　汇聚航路航班排序模型建立

综合以上分析，建模方法如下：

（1）以流量控制点的流量控制时间长度为基准，凡是在此时间长度区间内飞行的航班即为所要进行排序的航班，记航班总数为n。

（2）每一条汇聚于流量控制点的航路记为1路，设总共有m条航路汇聚于流量控制点，即共有m路。选择标准为所需要进行排序的航班经过的航路，如果航路在流量控制点前交汇于某航路点，以该航路点上游的航路作为区分，如第2路，第4路，该航路点到流量控制点之间的航班标记为编号较小的路的航班。

（3）在第m条路上飞行的航班组成一个队列，该队列中的航班不允许出现航班超越，且该队列的航班在排序前和排序后经过流量控制点的顺序不变。

（4）考虑到航路飞行航班的实际情况，针对不同的航班的优先级设置不同的延误权值。

2.1参数定义

N：汇聚航路的集合；

F：航班的集合；

Cnf：第n条航路上第f航班的延误权值；

n（f）：第n条汇集航路上的航班集合；

ETAnf：第n条航路上第f航班预计到流量控制点的时刻；

Xnf：第n条航路上第f航班实际到达流量控制点的时刻；

V：流量控制点处的时间间隔；

2.2目标函数

2.3约束条件

（1）航班不可加速提前到达流量控制点：Xnf-ETAnf≥0

（2）到达流量控制点的过点航班满足间隔约束：

（3）由上游航路到达流量控制点的同一行路上的航班不允许超越：（ETAnf2-ETAnf1）·（Ynf1nf2+1）＞0

（4）航班Xnf实际到达流量控制点的时刻：

表1　FCFS与遗传算法仿真结果

3　多路编码遗传算法设计

根据以上模型并结合约束条件，设计遗传算法，来实现航路航班的最优排序，并以三条汇聚航路为例对算法进行解释说明，如图2所示。

3.1编码方法设计

以往的遗传算法在解决航班排序问题时，编码方式多为格雷编码，二进制编码，浮点编码等，而这些编码方式在解决该模型下的航班排序问题时并不是最合理的选择，因此针对该模型中航班排序的问题，提出了多路编码的编码方式。

所谓多路编码是指航班（基因）在染色体中的值，是用该航班所在航路的航路号表示，航路的标号遵循上文中建模方法（2）中的方法进行标记。如图2所示，三条汇聚航路的标号分别1，2，3。将1航路上的航班都记为1，将2和3航路上的航班分别记为2和3。设第一条航路上有5架航班，第二条航路上有5架航班，第三条航路上有2架航班，则染色体由5个1，5个2，2个3排列组合而成，该染色体共有12个基因。其中5个1代表着1号航路上按顺序排列的5架航班。5个2，2个3的意义同上。染色体形式例如：

G=（112122123213）

若有N条航路汇聚于流量控制点，则每个基因可能取值的最大范围记为1到N。本例中每个基因取值的最大范围为1到3。对于航路3的情形，假设航路3与航路2的航路交汇点到流量控制点间的航路上有m架航班。为了保障同条航路上不出现航班的超越，则当某一基因取值为3时，必须保证该基因前有m个或m以上个基因取值为2。因此初始化种群时若出现如下基因应予以舍弃。

G=（312311221212）出现航班超越

3.2初始种群

如果在算法开始时能得到一个平均适应度较高的初始群体，再进行进化，将会显著地提高算法的求解性能。针对这一问题首先引入最大交换位置MPS这一概念。此处最大交换位置指的是以到先服务FCFS原则，依据各航路航班预计到达流量控制点的时间，进行排序所产生的染色体中，不同航路的航班相对位置变化的上限。实际当中航班相对位置的变化会增加管制员的工作负荷，文献三中对MPS的取值大小选择对航班排序延误的影响和管制员工作负荷的关系做了分析，结论表明，当MPS取值大于3时，将显著的增加管制员的工作负荷。因此此处选MPS值为2。

设计一个以三个基因长度为单位的时间窗，沿着染色体从左到右移动，步进为2，每移动一次，随机变换时间窗内两个基因的位置，当时间窗移动到染色体结尾时，将该染色体记为新染色体。对以先到先服务为原则的初始排序航班进行编码，产生初始染色体。将该染色体进行若干次如上变换，将产生的种群定为初始种群。

3.3交叉算子和变异算子设计

由于传统的交叉算子和变异算子，所产生的染色体，会带来无效解，降低求解效率，因此，需要对传统的交叉算子和变异算子进行改进，结合本文中提到的基因编码方式，可将其看成一种单性遗传，并不考虑交叉操作。新染色体的产生只通过基因的变异来实现。

变异方式为对染色体中的基因以随机概率向左或向右移动小于MPS位。由于要保证子代种群平均适应度高于父代种群，因此，对父代优良的基因进行变异，比对父代较差的基因进行变异，得到优良基因的概率更大。依据这一原则，采用父代中最优的染色体进行变异，生成子代种群。

3.4适应度函数

将目标函数作为适应度函数，适应度函数公式如下：

3.5计算步骤

Step1.航班编码，初始化种群gen（t），t=1，设置相应的参数，进化代数GEN，群体大小N等。

Step2.用3.3中的适应函数计算染色体的适应度值，对其大小进行比较，选出适应度最大的染色体，

Step3.对父代最优的染色体进行选择，进行变异，产生规模同样为N的子代种群，t=t+1。

Step4.当t>GEN时，算法停止，否则回到step2。

4　仿真结果与分析

仿真时采用三条汇聚航路上共20架航班，如图2所示。延误权值化分为0.6，0.3，0.1三个级别，每条航路上的航班，及预计到达流量控制点的时间和延误权值见表1。采用MATLAB对遗传算法进行了编程。流量控制的时间间隔设置为2分钟，种群规模设置为100，进化代数设置为300。

FCFS的目标函数值为13.8，航班延误时间为37分钟，而遗传算法的目标函数值为10.2，航班延误为38分钟。结果表明，本文提出的遗传算法在保证较小延误的情况下，能有效的减少航班延误成本。

5　结语

本文所提出的多路编码遗传算法可以快速求得最优解，采用数据进行仿真，并与先到先服务的航班排序进行对比，结果表明，该算法得到的航班排序可以有效减小延误成本。在此研究的基础上，下一步将对区域中多航路点进行流量控制的情况下航路航班的排序进行研究。

［1］赵嶷飞，金长江.区域空中交通流量控制研究［J］.飞行力学，2002，20（2）：67-70.

Zhao Y F，Jin C J.An approach to area traffic flow control research ［J］.Flight Dynamics，2002，20（2）：76-70.

［2］赵嶷飞，张雯雯.区域空中交通流量控制建模研究［J］.飞行力学，2009，27（5）：86-88.

Zhao Y F，Zhang W W. Modeling area air traffic flow control ［J］. Flight Dynamics，2009，27（5）：86-88.

［3］徐肖豪，姚源.遗传算法在终端区飞机排序中的应用［J］.交通运输工程学报，2004，4（3）：121-126.

Xu X H，Yao Y. Application of genetic algorithm to aircraft sequencing in terminal area ［J］.Journal of Transportation Engineering，2004，4（3）：121-126.

［4］Delahaye Daniel，Sofiane Oussedik，Puechmorel Stephane. Airspace Congestion Smoothing by Multi-objective Genetic Algorithm ［C］.ACM Symposium on Applied Computing，2005：907-912.

［5］Aditya P. Saraf ，Gary L. Slater. Optimal Dynamic Scheduling of Aircraft Arrivals at Congested Airports ［C］. Journal of Guidance，Control，And Dynamics，2008，31（1）：53-55.

［6］Shin-Lai Tien，Christine Taylor.A Rout-Based Queuing Network Model for Air Traffic Flow Contingency Management. AIAA Aviation Technology，Integration，and Operations Conference，2011：12-14.

［7］张军，詹志辉.计算智能［M］.北京：清华大学出版社，2009.

赵嶷飞（1971—），男，湖南常德人，博士，教授，研究方向：空中交通流量管理；

王惠斌（1989—），男，山东潍坊人，硕士研究生，研究方向：交通运输规划与管理。