基于多目标动态规划的多跑道进港排序研究

幸小燕

摘  要：伴随社会的全面发展，现代化的交通事业得到关注与发展，航空运输作为现代交通工具的典型代表，对促进社会的发展起着重要的作用。伴随航空运输行业的发展，航班出现晚点、延误的情况越来越多，除去气象等自然原因的影响，飞机进港排序是影响航班正常运行的关键因素。由于多跑道进港排序是一项复杂的工程，所以现阶段针对此问题没有形成长效的解决方案。文章以多跑道进港排序为研究视角，以实现多目标动态规划为出发点炸开讨论，旨在为飞机进港排序优化升级提供意见。

关键词：进港排序;多跑道调度;多目标优化

前言

飞机进港排序是提高终端机场吞吐量、减少能源消耗、减少航班延误的有效措施，在优化航班终端管理体制中发挥重要作用。面对越来越复杂、多元化的航空发展形式，国内外专家学者对优化进港排序问题的研究在逐步深入，呈现百家争鸣的状态，但是纵观其结果，主要针对但跑道，单目标进行。随着计算机技术的不断发展，飞机进港排序应该实现质的飞跃，实现多目标动态式的规划模式。因此，作者针对“基于多目标动态规划的多跑道进港排序”具有现实意义，希望通过文章的阐述，能够为航空运输事业的发展注入新鲜血液。

1 问题描述

由于各机场的具体状况不同，所以无法全面涵盖所有状况进行进港排序的设计，作者现针对特定条件下进行多目标动态规划的多跑道进港排序，现将各部分限定条件阐述如下：

1.1 飞机降落时间窗

机场终端服务区内的飞机必须满足一定的限定速度条件，那么根据飞机在机场各节点的飞行速度可以计算飞机最早的降落时间、最晚降落期限、预计降落时间等信息。现令飞机降落时间参数为ETi;飞机最早的降落时间设定为LTi;飞机最晚的降落时间表示为ETAi;飞机的预计降落时间表示为STAi;根据上述设定条件，飞机的降落时间窗即为[ETi，LTi]。

1.2 FCFS序列

FCFS序列是建立在飞机最晚降落时间的基础之上的一种具有一般性特征的系列，FCFS序列一般根据飞机的具体位置进行命名，现规定以下涉及到的FCFS系列按照终端服务区最大吞吐量产生[1]。

1.3 最大位置平偏移

最大位置偏移量是指序列进行成功优化之后产生的FCFS序列中飞机位置的变化程度，设定优化后的序列为A，最大位置偏移为k，那么会|Ai-i|≦k的结论。

1.4 降落时间间隔

同一跑道的两架不同飞机实现先后降落，中间必须间隔一定的时间，而且时间间隔必须满足特定的安全范围，现规定以下方案设计中必须满足国际航空组织对于不同类型飞机在统一跑道上实现降落的间隔时间标准。最小尾流间隔标准：重型飞机与重型飞机之间必须满足尾流为94;重型飞机与中型飞机间隔尾流为114;重型飞机与轻型飞机尾流间隔为167。

1.5 平行跑道

作者限定研究的机场类型为平行跑道模式，是指飞机降落的跑道与跑道之间处于平行的状态，而且能够达到距离较近的要求。那么可以理解为飞机在到达两条跑道需要的时间基本不会有太大差别，而且相邻跑道上降落的飞机能够保证安全的时间差。令双跑道同时运行过程中的安全时间间隔为40秒。

1.6 优化目标

飞机进港排序进行优化升级的总体目标是一致的，都是为实现吞吐量达到最大化、飞机延误时间降到最低、消耗的燃料成本尽可能减少。作者进行的设计方案规定进港飞机均可以早于最晚降落时间实现降落，用公式可以描述为：

ETi

那么此时吞吐量最大化可以表示为：

maxf1=n/（STAAn-t0）

上述公式中，STAAn表示最晚实现降落的飞机降落时间;t0表示规定的调度时间，如果t0的值是0，那么实现吞吐量最大的方式是保证最后降落飞机的降落时间最小化[2]。

降落消耗最小化的公式：

Minf2=c（STA）

上述公式中，ci（STAi）表示第i各飞机实现降落过程中的多余消耗部分;额外消耗部分会根据不同类型的飞机发生变化，现规定ci（STAi）=|STAi-ETAi|。

1.7 结果权重

在进行多目标动态规划进港排序优化的过程中，根据优化目标往往能够产生多个Pareto个优化结论。作者现设定结果权重为：首先要求对Pareto曲线上的多个节点进行统一化的处理;然后抽取Pareto曲线上凸出优化点;最后以抽取的凸点与其相邻的两个凸点进行连线并取其平均值。

1.8 离港排序

在进行飞机进港排序设计的同时，需要对机场离港飞机进行有效考虑，文章中将离港飞机的花费与进港飞机的花费按照同一时段同一跑道状况下相同予以考虑。

2 优化策略

2.1 CPS动态规划算法

动态规划算法主要由两类方式实现：一是深度优先搜索，主要是通过对每条路径进行不同的规划，然后因公剪枝等手法寻求最优解决途径的搜索方式;而是宽度有限搜索方式，是指按照不同路径的具体特征进行逐步深入式的搜索方式。在进港排序优化设计中，由于不尽相同的路径之间存在一定的交叉节点，所以，深度有限搜索在运用过程中将产生诸多重复性的工作。因此，规划方法的选择上应该运用宽度有限搜索的方式[3]。

2.2 优化CPS动态规划算法

为达到多跑道动态的进港排序，递推过程中的各个层级结点上飞机数量应该降到最低限度，能够达到掌握有效信息的目的视为成功。在进行进港排序的过程中，已经实现降落的飞机和具体跑道上最后需要降落的飞机类型是其关键因素，所以应该在飞机节点后面标注没条跑道最后一架飞机的类型信息。针对飞机的飞机的降落时间信息，应该在以往r维矩阵进行有效有效的优化和升级，将以往的r维时间矩阵进行离散化处理，让其功能更加全面，进而有效的提高运算的速度和准确率。

2.3 贪心策略

在进行算法优化的过程中，需要融入一定的贪心操作。在优化的CPS动态规划算法中，递推矩阵已经实现了三元组化，有利于进行三元组的选择工作，为贪心操作提供了可能性。融入贪心策略的总体指导思想是将每一个f|m||s||type1||type2|下设的某个三元组进行分析和优化，产生一种侧重于未排序飞机的最优化状态。如果通过一定的运算程序已经判定了一个或者一类三元组属于等同状态，那么可以将其进行处理之后进行删除，有效的节约解空间，提高运算效率[4]。

3 结束语

实现多目标动态规划的多跑道进港排序是航空运输业长足发展需求，是提高航空和运输效率的要求，是继续推动现代化建设有序进行的要求。希望通过文章的阐述，能够引发相关部门航空工作者针对优化飞机进港排序的共同关注，变革传统观念，优化算法，整合国际范围内的高级技术成果，全面优化升级飞机进港排序，促进航空运输事业的稳固发展，使航空运输业为社会发展贡献更多的力量。

参考文献

[1]张启钱，胡明华，张洪海.基于RHC-GA的多跑道進离场航班多目标动态优化模型[J].交通运输工程学报，2015，10（2）：70-78.

[2]冯翔，杨红雨.进港飞机调度多目标优化问题的改进NSGA-II算法[J].电子科技大学学报，2014，9（1）：66-70.

[3]梁曼，马兰，邹飞.基于混合动态规划算法的进场航班排序[J].广西师范大学学报（自然科学版），2014，5（1）：44-50.

[4]李丹程，曹斌，钟华刚，等.改进GA-PSO算法在多跑道航班着陆调度中的应用[J].小型微型计算机系统，2014，11（9）：2110-2115.