空中交通流量管理中飞机队列优化算法研究与实现

刘鑫哲

（中国民用航空华北地区空中交通管理局）

空中交通流量管理中飞机队列优化算法研究与实现

刘鑫哲

（中国民用航空华北地区空中交通管理局）

为了能够更好的实现对于快速增长的空中交通流量的管理，我们不仅仅需要对交通管制的设施进行完善，更加需要的是从交通管制的方式入手，对交通流量的管制程序来进行合理的优化，进而保证在空中交通的过程当中，能够对空中的资源进行合理的利用。

空中交通；流量管理；飞机队列优化；算法；实现

引言

随着我国经济以及社会的快速发展，我国的空中交通量开始快速的增加。空中交通量快速增加的大背景下，传统的交通管制系统已经完全没有办法满足当前庞大的空中交通流量的需求。在当前空中交通自动化管理的完善以及优化的过程当中，对于准备进行起降的飞机队列进行优化排序是非常重要的一个方向。真正有意义的飞机队列优化算法需要做到的就是对所有的需要进行排序的飞机都进行合理的计算，这样就能够在通过对总成本进行计算以及比较之后，从所有的排序当中选择最优的方法来进行。随着现在我国的交通流量的迅速的增加，导致了飞机的数量呈现了飞速的增长，进而使得这种循环排列算法进行计算的过程当中计算量开始呈现指数型的增长，大运算量使得在队列优化排序当中出现了运算问题。

1 国内外的主要算法介绍

首先我们针对国内外的主要的几种算法进行简要的阐述与分析，希望能给大家带来若干思考。

1.1 先到先服务（FCFS）算法

所谓的先到先服务的算法就是通过对飞机的到达的时间进行预计，然后根据飞机到达时间的次序来进行飞机的着陆次序的决定。采用这种方法的时候，一旦当需要着陆的飞机进入到了终端区当中的排序区域的时候，排序的系统就会根据飞机进入到终端区的时间以及飞机的具体的性能以及飞机的初始状态等来对飞机到达目标点的ETA来进行相应的计算，然后根据计算的ETA的结果终端系统就能够结合飞机链的排序情况来对飞机的计划的到达机场的时间来进行确定。如果说在确定的飞机链的间隔当中无法插入一辆新的飞机来进行着陆，那么这个时候系统就会在保证飞机着陆时间的间隔符合标准的情况之下来对这架飞机之后的飞机来进行重新的排序，也就是说需要进行延迟处理。如果说在进行延迟处理的时候后面的飞机不能够进行延迟处理，必须要准时进行降落的时候，我们就需要对这一架新到达的飞机来实行等待的策略，使得这一架飞机在末一个固定的空域当中进行等待，等可以进行降落的时候在安排进行降落。

1.2 约束位置交换（CPS）算法

约束位置交换法与前面的方法是不同的，这种方法所需要进行依据的就是所有不同的类型的飞机之间必须要保持着最小的安全间隔标准，然后我们依据这个来对飞机队列的次序进行重新的排序，在进行排序的过程当中我们需要对所有有可能的飞机的排序方式进行搜寻，通过搜寻从所有的飞机排序方式当中找到成本最小的排序方式来进行排序，这种排序方式就是我们需要的飞机的最佳的排序方式。但是这种算法的缺点就是通过这种算法确定的最佳的排序方式可能会使得原来的飞机的队列次序产生非常大的变化，这种对原飞机队列进行较大的改变的方法不仅仅会对管制员的负担造成极大的增加，而且还会与先到先服务的原则产生很大的冲突，对于航班飞机的公平性进行了降低，并且还会对实现的难度进行增加。所以说需要带约束的进行位置交换，也就是说飞机的最终的位置需要保持在最初的初始位置前后的一定范围之内的适当位置之上。

2 滑动排序窗算法设计实现

以下，我们以滑动排序窗算法的设计以及实现为例，进行探讨分析：

在机场当中的终端区的飞机流往往都是由不同飞机类型的飞机来进行组成的，并且这些飞机的前后的顺序是不同的，每一架飞机的尾流间隔也是不同的。ICAO对于无风条件之下的飞机的最小的间隔标准进行了一定的规定，这样就能够得到最小的时间间隔。

我们在对排序的问题进行考虑的时候首先需要考虑到的原则就是先到先服务原则，以及不同类型的飞机需要保持着不同的最小安全间隔标准来进行入手，我们通过对飞机的队列次序来进行重新的排列，然后对所有的有可能的飞机的排序方式来进行搜寻，这样就能够找到一种成本最小的排序方式，这种排序方式就是最佳的飞机排序方式。

要想要得到最优的序列，我们需要采用最为直观的方法来对所需要进行排序的飞机来进行循环排列。就十架飞机来说，我们在硬件PIII600CPU，128M内存的条件之下来进行运算，大约需要30s的时间来进行计算。但是随着飞机的数量的增加，计算的难度也就增加，现在的硬件情况是没有办法进行满足的。也就是说循环排列算法的瓶颈就是飞机的数量的线性增长。下面所提到的排序窗法就是通过限制全排列飞机的数目来抑制计算量的指数增长的速度。

这种排序窗算法的理论依据就是，在进行优化排序的过程当中需要对原来的飞机队列当中的所有的飞机的位置进行重新的排列，对于每一架飞机在新的队列当中的位置进行确定。我们在对新的队列进行排序的过程当中，由于某一个或者说某些的位置存在着约束交换范围的限制，所以说我们不需要对所有的可能产生的排序进行搜索，只需要对那些与所需要确定位置相关的飞机，然后对他们产生的相关的可能排序来进行搜索，得出最后的最优队列。这样通过一定的约束条件能够极大的降低计算的压力，提高运算的速度。

3 结语

综上所述，随着我国的空中交通流量的增加，传统的计算方式已经完全没有办法满足这巨大的交通流量的需求了，在本文当中笔者主要阐述了几种国内外比较常见的飞机队列优化算法，然后对飞机队列优化算法的设计以及实现进行了简要的分析，希望能给相关人员带来一定的启发。

[1]田勇.空中交通流量管理关键技术研究[D].南京航空航天大学，2009.

[2]景文超.空中交通管理流量战术控制研究[D].西南交通大学，2005.

[3]顾秋丽.空中交通管理中的排序问题研究[D].中国民航大学，2014.

[4]叶博嘉.空中交通流量管理动态网络流模型及实现算法研究[D].南京航空航天大学，2008.

V355.1

A

1004-7344（2016）02-0281-01

2015-12-22

刘鑫哲（1988-），男，汉族，北京人，管制员，本科，研究方向为交通运输。