隐枚举算法在飞机着陆调度中的应用

隐枚举算法在飞机着陆调度中的应用

王科

民航湖南空管分局湖南长沙410137

摘要：近年来，随着我国经济的高速增长，空中交通流量显著增加，原有的空中交通管制系统已经不能满足日益增长的交通量需求。仅仅通过空中交通管制设施的改善己经不能作为提高空中交通流量的主要手段，而可以从设计对飞机队列进行优化排序的算法来简化管制员的工作。本文主要研究基于MPS的隐枚举算法在终端区飞机等待排序队列中的应用，为空管自动化提供了较好的途径。

关键词：空中交通管制；着陆调度问题；隐枚举算法

1MPS算法分析与实现

1.1飞机着陆调度问题定义

目前的实际空管程序中对到达交通流的调度普遍采用先到先服务(FCFS)策略,它完全取决于管制员的经验。基于FCFS上的优化调度包括两个方面的内容:在飞机的性能范围内指定每架飞机的计划着陆时间(ScheduleTimeArrival,STA)和每架飞机的着陆顺序。

适应于现实应用的飞机着陆调度问题可定义如下:

从算法上来看，飞机着陆调度问题实际上是众所周知的旅行推销员问题(TSP)的一个实例。TSP问题属于NP-Complete类，没有多项式算法。然而，更为重要的方面在于，现实空管多方面的复杂约束，导致常规优化算法很难应用于实时的空管自动化环境。

我们所讨论的排序问题，主要是在考虑先到先服务(FCFS)原则的基础上，从不同类型飞机必须保持不同的“最小安全间隔标准”(为了简化模型，最小安全间隔只考虑尾流间隔)入手，通过对飞机队列次序的重新排列，对所有可能的飞机排序方式进行搜寻，找到一种成本(指队列中每两架飞机之间所需时间间隔的总和或以等待时间为参数的每架飞机的等待成本的总和)最小的排队次序，即是该组飞机的最佳排序方案。

1.2基于MPS的隐枚举算法

MPS=l限定约束可以使从原集合E到优化集合S的映射解空间得以极大的减小。设原集合E有n个元素，图4-1表示了从E到S的映射递归过程。设从E到S映射的解空间为。若选定S中的第一个元素为E中的第l个元素，则S中的第2个元素可以是E中的2或3，得到B中所示的。若选定S中的第1个元素为E中的第2个元素，则S中的第2个元素只能是E中的1，得到C中所示的。

对于MPS=2或更高的情况，可以证明，和MPS=l的2种子赋值图相比，它有6种子赋值图形式。研究表明，它对容量的提升有限，但更重要的是，它将导致管制员工作负荷显著增加，因此本文不加以讨论。

隐枚举算法属于深度优先算法，它通过搜索解空间，将不满足各种约束和目标函数的分支去掉，从而得到最优解。对于飞机着陆调度问题，可以采用特别的约束条件，使解空间的搜索范围得以极大的减小，这些约束包括:

（1）最大位移MPS=l约束。优化序列与FCFS序列相比，每架飞机前后移动的位置不能超过规定的最大位移值。这是使计算量得以极大减小的关键限制条件(从阶乘到指数)。

（2）位置冻结限制。位置冻结是指相对于FCFS序列而一言，优化序列中被冻结的飞机位置不变，约束的满足不是在序列形成后，而是在形成中得以判定。

2带移动排序窗的MPS算法与实现

在上节讨论的基础上，只考虑（1)（2)约束时，计算量随问题规模呈指数增加。这在交通流量超过40架/小时后，调度算法加上其他处理时间将不能达到实时性要求。解决这一问题的方法是采用移动排序窗的优化技术，这实际上是一种局部优化的方法。这一方法在排序队列中先建立一个移动排序窗的模型，同时定义窗内飞机数目为m和移动步长为n，对排序窗内的飞机通过上述算法进行优化，然后以步长n遍历整个序列，得以优化求解。这种情况下，计算量主要取决于移动排序窗内的优化算法，整个队列的计算量随问题规模呈线性增加。计算速度大大提升。而且另外重要的一点是，这种方法更加适合实际动态环境，当调度区有新的飞机加入时，则触发一次优化调度算法，整个队列后部长度为排序窗尺寸的那些飞机被优化，而队列前部接近着陆部分的飞机将保持前次调度结果，使得调度结果易于为管制员所接受和实现。

2.1约束条件

d．设每架飞机的最大加速量为90秒，即各机最早的STA不超过其ETA90秒。

2.2算法模型

进行排序之前，在排序队列中先要建立一个移动排序窗的模型，同时定义窗内飞机数目为m和移动步长为n。采用算法只对窗内的飞机进行排序，好象它们就是所有需要排序的飞机。一旦窗内这部分飞机排序完成，窗体就以某一步长向后移动。排序过程如下:

第一步:定义初始队列(以ETA顺序排列)的前m架飞机为初始窗，并对其进行排序，优化后序列的前n架飞机就被分离出排序窗，并分别作为最终队列的第1至n架飞机。

第二步，排序窗以n架飞机的步长向后移动，使其右边界到达初始队列的第m+n架飞机，加上刚才未被分离出窗体的m-n架飞机，重新构成新窗内的m架飞机。

第三步，对它们再次进行排序，特别需要注意的是，此时必须考虑窗内飞机与前面已经固定为最终队列的n架飞机的最后一架的相关处理。窗内飞机排序完成后，又会有n架排在最前的飞机，被分离出窗体，作为最终优化队列的第n+l至2n架飞机。

第四步，重复第二步的排序过程，窗体后移，组成新窗。

第五步，重复第三步的排序过程，对窗内飞机进行排序，将排序结果的前n架分离出排序窗，加入最终队列。

第四步和第五步的这个过程一直循环进行到窗体右界移动到初始队列的最后一架为止。

最后，对“末尾窗”中的m架飞机进行排序，再把排序结果加到前面几步分离出的飞机己排好序列的最后面。全部排序过程便告结束。

3算法总结

1．隐枚举算法在解空间的搜索中实时进行约束和目标函数的判断，因此能满足现实复杂空管条件下的各种限制约束以及多种目标函数，这正是本算法有别于其他算法的主要所在。

2．此算法得出的结果更易于管制员的接受。

3．由于算法通过对解空间进行深度优先搜索，枚举可能的排列，因此在这一过程中可加入任意约束，同时，由于算法的设计特性，部分约束还可减小空间搜索范围(如位置锁定约束)。使得算法对实现复杂约束的适应性好。

4．计算快速，能满足动态的ATC自动化环境所需的实时性要求。