机场航班调度动态优化算法

田琛晟 张楚嫣 王炜祥 田启川

关键词： 机场航班; 调度方案; 冲突事件; 动态优化算法; 跑道入侵; 等待时间

中图分类号： TN964?34; TP391.9               文献标识码： A                    文章编号： 1004?373X（2019）02?0033?08

A dynamic optimization algorithm for airport flight scheduling

TIAN Chensheng1， ZHANG Chuyan1， WANG Weixiang1， TIAN Qichuan2

（1. Honors College， Northwestern Polytechnical University， Xian 710072， China;

2. School of Electrical and Information Engineering， Beijing University of Civil Engineering and Architecture， Beijing 102616， China）

Abstract： In allusion to the problems that the airport runways are limited as the aircrafts that need to take off and land increase and how to shorten the waiting time of passengers， a dynamic optimization algorithm for airport flight scheduling is proposed. The aircraft state parameter matrix model is defined. The sliding parameters of different types of aircrafts are calculated. The sequence scheduling schemes for a limited number of take?offs and landings are traversed according to the real?time flight information and time order of arranged taking?off and landing aircrafts in each airport terminal per hour. The time consumptions of scheduling schemes are compared. The dynamic scheduling optimization scheme is given on the premise of meeting the security target and taking the reduction of passengers′ waiting time as the optimization target. The runways and airport terminals are assigned to the corresponding aircrafts for take?offs and landings according to the optimization scheme， so as to increase the take?off and landing times of airport flights， improve the utilization rate of runways， and shorten the waiting time of passengers. The simulation results show that the dynamic optimization algorithm for airport flight scheduling is effective.

Keywords： airport flight; scheduling scheme; conflict event; dynamic optimization algorithm; runway incursion; waiting time

0  引  言     

近年来随着经济的高速发展，人们的生活水平大幅提高，飞机已经成为人们出行交通方式的第一选择。因此，航空市场需求有了持续的高速增长，航班流量日益增加，这给机场安全起降造成了很大的压力。受起降跑道等有限条件的限制造成飞机相撞、飞机延误情况经常出现，飞机调度问題迫切需要解决。防止飞机相撞已成为空管日常工作中的一项重要内容，每起飞机相撞事故的发生，都会造成难以估计的损失[1?2]。

许多大型机场，飞机起降次数猛增，年吞吐量达到400万人次以上。这么繁忙的机场受调度效率的影响，航班延误率在不断上升，机场使用效率降低。由于机场调度影响因素复杂，使得由此引起的诸多经济社会问题备受关注。这些问题给人们的出行带来影响，对航空公司、机场运营方造成了利益损失。

国际民用航空组织定义的“跑道入侵”指的是“在机场中发生的任何涉及错误的出现在用于飞机起飞和降落的保护区表面的飞机、车辆以及行人的事件”。据中国民用航空局网站消息，2016年10月11日，东航A320/B?2337号机执行MU5643航班任务，飞机于北京时间11：54滑出，北京时间12：03塔台指挥飞机进跑道36L，机组在执行完起飞前检查单之后进入跑道，12：04塔台指挥：跑道36L，可以起飞。机组在确认跑道无障碍的情况下，执行起飞动作，在飞机速度达到110 kn左右，机长发现一架A330准备横穿36L跑道，但此时飞机速度已经达到130 kn，机长短暂判断后决定马上起飞，幸运的是飞机正好飞越A330且后续飞行正常。该事件虽未造成事故，但是也是一起严重的A类穿越事件，一旦发生碰撞后果将不可想象。中国民航局公布的调查结果显示，通过对事发相关人员进行调查问询，调取通话录音、雷达录像，以及对涉事飞机的飞行数据记录器、驾驶舱语音记录器进行了译码，判断该事件是一起因塔台管制员指挥失误造成跑道入侵事件。

造成飞行冲突的原因是多方面的，既有主观方面的，也有客观方面的;既有飞机本身原因，也有天气、环境等外在原因。为避免大型高密度机场起降飞机发生冲突，必须制定高效的引导方案[3]，因此，机场航班调度非常重要，除去天气等客观原因，调度过程需要根据飞机的起降要求和位置，进行合理规划，才能提高机场起降效率，让飞机安全起降。

1   问题描述和分析     

1.1  问题描述

1.1.1  机场描述

以上海虹桥机场为例，上海虹桥机场示意图见图1。为了便于说明问题，将T2航站楼登机口按照登机楼所占区域划分为T2?①，T2?②，T2?③和T2?④四个登机区。T2?①登机区为T2?1～T2?21登机口;T2?②登机区为T2?22～T2?33登机口;T2?③登机区为T2?34～T2?62登机口;T2?④登机区为T2?63～T2?75登机口。假设机场的风向为由北向南，风速为20 km/h，飞机逆风起飞，逆风降落，滑行速度假设为10 kn/h，这样飞机无论是起飞还是着陆，滑跑方向都为从南向北。

1.1.2  起降航班情况描述

全天24 h的航班调度问题都可以看作每小时的航班调度问题，而且航班受许多客观因素影响，起降时刻有不确定性，因此，针对1 h内的航班情况来调度和规划路径更有实际意义。

根据虹桥机场1 h之内要起降航班的情况：有27对航班起降，并对这些航班进行了编号，如表1、表2所示。

為了便于筛选与识别，对4：15PM—5：15PM时间段进行分段标号，如表3所示。这样每5 min分一个时间段，共有13个标号，以此来研究这1 h内航班的调度问题。

1.2  问题分析

1.2.1  冲突分析

根据图1的虹桥机场示意图可知，机场分起飞跑道和降落跑道，T1航站楼在降落跑道一侧，T2航站楼在起飞跑道一侧，所以当发生飞机降落要到T2航站楼同时飞机要从T1航站楼起飞时，起降的飞机必然需要横穿跑道，就有可能发生冲撞，这类事件就是“冲突事件”。而T1航站楼降落和T2航站楼起飞没有冲突，可以同时发生，称为“安全事件”。要求同一个时刻每个跑道不能有两架飞机。也就是说，如果当前时刻有飞机在跑道上进行起降，那么其他要起飞的飞机只能在登机区等待，要降落的飞机也只能等待降落跑到无飞机时才能降落;因此，合理调度航班并规划一条路径才能节约时间提高机场效率。

根据对起飞降落航班信息进行分析可知，不同时间段的飞机起降分配或疏或密，增加了“冲突事件”发生的概率。在不改变航班次序的前提下，为了提高航班效率和安全性，就需要为起降飞机合理分配不同时间段和航站楼。这一过程可以通过遍历算法来实现优化。

1.2.2  航班状态矩阵模型

用[T1]，[T1*]分别表示T1航站楼的起降飞机数，用[T21]，[T21*]，[T22]，[T22*]，[T23]，[T23*]，[T24]，[T24*]分别表示T2航站楼的不同登机区域T2?①，T2?②，T2?③，T2?④的航班起飞和降落的数目。构造一个矩阵[M]，每行代表一个时间段，每行的数据元素分别为5个登机口的起飞航班数和降落航班数。其中：

[Mi=T1，T21，T22，T23，T24，T*1，T*21，T*22，T*23，T*24，i∈1，13]

[M=M1，M2，…，Mi，…，M13T]  （1）

以矩阵[M]的形式，分别建立3个矩阵：[A13×10]表示13个时间段不同航站楼的起降航班数;[B13×10]表示13个时间段不同航站楼的冲突航班数;[C13×10]表示13个时间段不同航站楼的安全航班数，见式（2）～式（4）。用这3个矩阵对一个小时内的航班信息进行表示，建立分析模型，便于进一步分析和调度。

通过矩阵模型的方法简化了航班信息，得到一组易于进行分析判断的数据。因为从T2航站楼起飞的航班和着陆到T1航站楼的航班之间不存在“冲突事件”发生的可能性，即T2航站楼的起飞航班和着陆到T1航站楼的航班两个事件为相互独立事件，可以同时进行。对于可能造成“冲突事件”发生的航班，即矩阵[B13×10]中所列举的航班。

因此，航班调度问题转化为对航班状态矩阵数据的分析问题，此外还需要考虑飞机穿越跑道的时间，需要进行分析并规划设计出航班滑行的路线。

2 机场航班调度算法

2.1  模型简化

为了便于说明问题，对上海虹桥机场进行了几何简化，如图2所示，对T1，T2对应航班的滑跑路线给出图示的几条路线。假设每架飞机的滑跑距离、滑跑时间相同且起降滑跑时间都等于飞机横穿跑道的时间，假定时间为90 s。

设定飞机起降工作为优先考虑事件，飞机穿行跑道为次要考虑事件。工作模式为优先进行“不冲突事件”航班的起降，“冲突事件”的航班按照一定的次序在起降跑道与等候跑道的交点（称之为节点）处等待。当聚集在同一条跑道上不同节点的飞机总数目大于2时，该跑道立刻停止起降工作，容許等待穿行的飞机穿过跑道。其中从降落跑道穿行起飞跑道到T2航站楼共有两个节点，从T1航站楼穿行降落跑道到起飞跑道共有三个节点。

2.2  以安全性为目标的航班调度算法

以安全性为单一目标的航班调度算法如下：

1） 按照航班信息表选取1 h内的所有航班[A13×10]，将起飞航班和降落航班分别按照时间进行排队;

2） 依据航班次序，计算[B13×10]，分析起飞航班、降落航班是否存在冲突可能，如果不存在冲突可能，那么[C13×10]的安全航班可正常安排起降，否则需要等待;

3） 发生冲突的等待航班，当聚集在同一条跑道上不同节点的飞机总数目大于2时，该跑道立刻停止起降工作，容许等待穿行的飞机穿过跑道。

按照该调度算法，对航班表1、表2所列航班进行调度，给出的调度策略如表4所示。

表4给出各个航班起降及停靠位置，是一个完整的路径规划方案。将飞机航班表中的初始时间4：15PM设为0时刻，Time1表示飞机起降任务的起始时间，Time2表示飞机起降任务的完成时间，两者的差Δt为旅客等待时间。

由表4可以看出，完成所有任务用时为3 420 s，小于要求的1 h起降时间。该调度策略能够完成这1 h内的起降任务，保证起降不发生冲突现象。但是，从调度表也发现了一些问题，那就是有的航班从准备起降到完成起降任务中间有较长的时间，旅客在飞机机舱中等待飞机起飞或降落的时间有些长，如Planedown 26和Planeup 3的等待时间分别为1 080 s和2 070 s，这容易引起旅客产生不满情绪或心里不安，降低了航班准点率及机场使用率。考虑到旅客对航班等待的忍耐程度和机场地面调控的安全，需要在保证安全性的前提下，调度时应能够给出一个旅客等待时间短的调度方案。

3  机场航班调度动态优化算法

3.1  参数修正

在前面的调度中，未进行精确的建模，统一采用固定的90 s时间进行航班调度，未考虑从各个航站楼登机区到起飞跑道的距离、不同机型需要不同的起降滑行时间和距离，因此第2节中调度算法还需要改进。

不同的飞机型号具有不同的起飞和降落滑行距离和时间，对不同的飞机型号，只有得到较准确的飞机滑行距离和时间，才能对飞机在跑道上的停留时间做出较准确的预测，才能避免冲突事件发生。

为了使规划更加准确合理，对飞机滑行时间和滑跑距离进行修正[4?5]。计算可知降落至滑行时间约为47 s，起飞滑跑时间约为38 s，准确计算了现行7种飞机起降时滑跑距离，得到如表5所示的不同机型起降距离。

在数据修正的基础上，依据中国民航局地面滑行最小安全间隔的规定，飞机在滑行道上滑行时必须满足最低尾流间隔标准，其间隔标准取决于飞机的机型。鉴于1 h内航班机型情况，考虑到优化滑行路径时是以时间为基础的，所以有必要把滑行飞机的间隔距离转换为时间间隔来控制，也可参照文献进行滑跑路径优化[6?10]。依据中国民航总局的相关规定，设定机场地面飞机滑行时间间隔为30 s，再加上修正后的起飞滑跑时间38 s，平均一架飞机从滑行、等待到升空所需时间为68 s。同理，降落跑道使用时间间隔为77 s。

3.2  等待时间

在飞机安全的基础上考虑准点率和起降率，将时间忍耐度作为一个优化的目标变量，根据动态规划对调度方案进行动态优化，使方案更加优化。文中设500 s最大旅客等待时间作为旅客最大能够忍耐的时间。

这样，飞机调度的策略就是以安全作为第一考虑要素，按照航班的排列顺序，以跑道上起飞降落的飞机作为第一安全考虑，当跑道上有飞机起降，需穿行的飞机必须等待起降飞机的起降工作。如果按照航班时刻表去调度是没办法实现航班次序优化减少等待时间的，要想缩短旅客的等待时间，需要调度调整起降顺序。

3.3  航班顺序遍历

通过改变航班次序来比较不同的调度方案最终得到优化的航班调度方案，采用数值模拟的方法进行方案比对[11]。调度方案遍历寻优一方面是为飞机确定无冲突的滑行路径，最优路径是从可行路径中选择，另一方面要通过航班到达其路径上节点的时间进行优化，因此，方案的优化采用前面的计算模型，来模拟航班按照不同的顺序起降，计算该方案所需要的最短时间。为了得到所用时间最短的航班调度方案，需要尽可能多地遍历不同的航班组合，以给出较优的调度方案，否则机场利用率会很低[12]。

在可以改变航班次序的情况下，该问题可以视为非线性问题的动态规划。但是，由于可能性过多，求得全局最优方案不太实际，所以选择建立有限的随机方案，求取这些随机方案的最优解，在随机方案数量有限的约束条件下，用这些随机方案的最优解代替全局最优的方案作为调度方案，基于遺传算法的调度优化也只能是较优解，而不是最优解[13]。

3.4  以安全性和等待时间为目标的航班调度算法

如表1、表2所示，当前的1 h内有27架次的起飞航班和27架次的降落航班，那么这种排列组合是一个很大的数，遍历各种可能的情况是不切合实际的，所以必须通过一定的方式来简化计算过程，尽可能地得到较优调度方案。航班信息每时每刻都在更新，航班调度属于非线性动态规划[14]。

机场航班调度动态优化算法步骤如下：

1） 按照航班信息表选取1 h内的所有航班[A13×10]，分别将起飞航班和降落航班分别按照时间进行排队;

2） 对航班顺序进行编号，并选出多组随机排列组合，作为多种航班调度方案;

3） 依据航班次序，计算[B13×10]，分析起飞航班、降落航班是否存在冲突可能，如果不存在冲突可能，那么[C13×10]的安全航班可正常安排起降，否则需要等待;

4） 发生冲突的等待航班，当聚集在同一条跑道上不同节点的飞机总数目大于2时，该跑道立刻停止起降工作，容许等待穿行的飞机穿过跑道;

5） 与已有的调度方案比较，记录不同调度方案的用时最少的多个方案和该方案的旅客等待时间;

6） 如果选出的全部航班调度方案遍历已经结束，那么转到步骤7），否则，转到步骤3）进行下一组调度方案分析;

7） 从最后得到的多个调度方案中选出等待时间最短的方案（其他方案也可以作为备选方案）。

为了获得接近最优的调度方案，用来分析的随机调度方案数量应该尽可能多一些，遍历这些不同方案就可得到接近于最优的方案，但是这样会带来计算量的增大，因此具体选择多少组随机方案可根据算法的实时性要求确定。

4  实验仿真

虹桥机场1 h之内要起降航班的情况见表1、表2。为了寻求好的调度方案，编写了产生不同排列随机调度方案的程序，实验中随机调度方案的数量限定为5 000个。经过比对，从中选取时间最短的解作为最优解和最终的航班调度表，如表6所示。

可以看出，采用文中航班动态调度算法，仅用2 495 s就完成了计划内所有航班的起飞和降落任务。同时，在54次起降任务中，该调度方案有35次航班无需等待，可以直接进行起飞或降落，最长的等待时间都在500 s之内，限制在旅客能够承受的时间范围内。

通过比较，参数优化后增加了最大忍耐时间后的调度优化策略明显更合理、更科学，提高了机场起降效率。该机场航班动态调度算法可以针对1～2 h内的航班进行调度优化，由于航班起降也受其他因素影响，航班调度没有必要一次进行24 h内航班的起降进行规划，这样根据实时的航班信息对1～2 h进行调度优化，更新航班数据后再对下一个时间段进行调度优化，实现机场起降登机的统筹安排，确保不会影响旅客的出行计划。

5  结  语  

针对日益增多的依靠航班出行、旅游人员来说，很看重飞机的安全性和航班的准点率，面对机场起降飞机增多的情况，航班的调度决定着机场的起降效率：求取不同机型飞机滑行时间和滑行距离，有助于提高调度的精细化;简化机场模型，以时间进行动态规划，保证飞机起降安全;在限定随机方案数量的情况下，借助矩阵模型进行冲突分析，对影响调度结果的参数进行精确优化，最终的调度方案极大缩短旅客等待时间。实验结果表明，本文提出并实现了基于安全性和最大忍耐时间的航班调度优化算法，实时性好，可实现机场高效服务。

注：本文通讯作者为田启川。

参考文献

[1] 孙金峰，张咫千，姚东宾.从上海虹桥机场跑道入侵事件谈飞行冲突的处理[J].科技创新与应用，2016（34）：292.

SUN Jinfeng， ZHANG Zhiqian，YAO Dongbin. Discussion on the handling of flight conflict from the runway intrusion event at Shanghai Hongqiao Airport [J]. Scientific and technological innovation and application， 2016（34）： 292.

[2] ANDERSON J D. Introduction to flight [M]. New York： McGraw?Hill Education， 2015.

[3] 汤新民，安宏锋，王翀.面向冲突避免的航空器场面滑行引导方法[J].西南交通大学学报，2011，46（6）：1032?1039.

TANG Xinmin， AN Hongfeng， WANG Chong. Conflict avoidance oriented airport surface aircraft taxiing guidance method [J]. Journal of Southwest Jiaotong University， 2011， 46（6）： 1032?1039.

[4] 黄奇，李宜峰，林可心，等.飞机起飞和着陆所需滑跑距离计算方法中参数值的试验分析[J].路基工程，2013（5）：87?89.

HUANG Qi， LI Yifeng， LIN Kexin， et al. Experimental analysis on parameters required in calculation of taxiing distance for airplane′s taking?off and landing [J]. Subgrade engineering， 2013（5）： 87?89.

[5] 董莹，安然.机场航空器地面滑行时间优化研究[J].交通运输系统工程与信息，2011，11（5）：141?146.

DONG Ying， AN Ran. Optimization of aircraft taxiing time [J]. Journal of transportation systems engineering and information technology， 2011， 11（5）： 141?146.

[6] 尤杰，韩松臣.基于多Agent的机场场面最优滑行路径算法[J].交通运输工程学报，2009，9（1）：109?112.

YOU Jie， HAN Songchen. Taxi route optimization algorithm of airport surface based on multi?Agent [J]. Journal of traffic and transportation engineering， 2009， 9（1）： 109?112.

[7] 李鋆，王春雷.機场场面飞机滑行路径优化模型[J].黑龙江科技信息，2012（1）：20?21.

LI Jun， WANG Chunlei. Optimization model of aerodrome plane gliding path [J]. Heilongjiang science and technology information， 2012（1）： 20?21.

[8] 黄邦菊，李婷.航空器场面滑行路径优化研究[J].海峡科技与产业，2016（6）：96?98.

HUANG Bangju， LI Ting. Study on the optimization of the gliding path of aircraft [J]. Technology and industry across the straits， 2016（6）： 96?98.

[9] 高国政.基于蚁群算法的航空器地面滑行研究[J].山东交通科技，2011（1）：24?27.

GAO Guozheng. Research of airport surface taxing for aircraft based on ant colony algorithm [J]. Traffic science and technology in Shandong， 2011（1）： 24?27.

[10] 李鋆.机场场面飞机滑行调度优化问题的MILP模型及算法[J].价值工程，2012，31（3）：144?146.

LI Yun. An optimization MILP model for aircrafts taxi scheduling in the airport surface and algorithm [J]. Value engineering， 2012， 31（3）： 144?146.

[11] 宋花玉，蔡良才，郑汝海.飞机起飞滑跑距离数值积分改进算法[J].交通运输工程学报，2007（2）：24?28.

SONG Huayu， CAI Liangcai， ZHENG Ruhai. Numerical value integral improvement algorithm of aircraft take?off running distance [J]. Journal of traffic and transportation engineering， 2007（2）： 24?28.

[12] 杨雪，胡玉清.机场调度算法的性能分析与研究[J].软件导刊，2009，8（6）：51?53.

YANG Xue， HU Yuqing. Analysis and research on the performance of airport schedule algorithm [J]. Software guide， 2009， 8（6）： 51?53.

[13] 刘兆明，葛宏伟，钱锋.基于遗传算法的机场调度优化算法[J].华东理工大学学报（自然科学版），2008（3）：392?398.

LIU Zhaoming， GE Hongwei， QIAN Feng. Airport scheduling optimization algorithm based on genetic algorithm [J]. Journal of East China University of Science and Technology （Natural science edition）， 2008（3）： 392?398.

[14] 吴受章.离散时间最优控制：评论动态规划[J].控制理论与应用，2013，30（9）：1165?1169.

WU Shouzhang. Discrete?time optimal control： comments on dynamic programming [J]. Control theory & applications， 2013， 30（9）： 1165?1169.