基于大数据的航班调度优化模型与算法初探

石磊 陈伟

摘 要：为了提高服务质量和降低运营成本，所有的航空公司都在不断寻找各种方法来合理安排航线，降低航班延误。本文主要讨论如何利用大数据来更准确的预测飞机时空位置和航班到达（跑道、登机口）时间，从而来更有效的实时优化航班，使得总的延误时间与消耗燃油最小。在此过程中，我们细化航班调度涉及的目的与问题，在此基础上建立数学模型，最终通过机器学习技术求解此模型，提出合理的调度方法。

关键词：大数据；航班调度；航线实时规划；到达时间预测；机器学习

中图分类号：V247.4文献标识号：A文章编号：2095-2163（2016）02-

Exploration of big data based flight schedule optimization

SHI Lei1 ， CHEN Wei1

（1 China Travelsky Holding Company， Beijing， 100105， China）

Abstract：In order to improve the service quality and reduce the operating costs， all airlines are constantly looking for ways to optimize the routes， reducing flight delays. This article discusses the methods to use big data to more accurately predict the location of aircraft and the arrival time， and thereby to more effectively do real-time flight optimization. In this process， the paper refines the flight scheduling purposes and the issues involved， and based on the aboved， the mathematical model is built. The paper tries to solve the model by using machine learning technique to arrive in reasonable scheduling method.

Keywords： Big data； flight schedule； real-time route planning； arrival time prediction； machine learning

0 引言

随着人们生活水平的提高，选择飞机出行方式的人越来越多，使得航空运输的重要性日趋显著，从而必然导致航班数量的急剧增加。目前，不断增长的航班数量在面对有限的登机口数目，以及各类突发变化的内、外界（包括天气原因、流量控制、机械故障或公司周转）的综合作用都可能实时导致航班的延误，不仅给乘客出行带来困扰，更会使得航空公司成本直线提升。例如经常出现的由于目的地的台风天气，导致航班被迫取消，旅客滞留，从而需要赔偿并安排食宿。统计数据显示，对于一个中等规模的航空公司，如果能够使得每次航班的平均延误时间减少一分钟，则每年将可节省数亿元的成本[1-2]，航空公司成本具体表现为：燃油、赔偿以及人员费用。综上所述可知，航空公司的航班调度计划对于航空公司的基础良性运行则始终发挥着至关重要的智能支撑作用。调度计划上微小优化都可为航空公司节省大笔费用。因此各国的航空公司及研究学界都在不断探寻各种方法来优化航班调度，减少航班延误，提高服务质量。本文即针对这一课题内容展开探索论述，具体如下。

1问题描述

研究中，航班调度通常包括两个方面：

问题A，飞机航线的优化，即（根据大数据）实时调整飞机的时空位置；

问题B，根据航线的安排，准确预测航班的达到时间。

一般来说问题A，即飞机航线的优化涉及到通过给定当前位置、目的地位置、天气以及其他相关因素来制定飞行计划，从而使得所有航班的平均成本降至最低。将其进行数学抽象后可知，该问题顺于成本函数已知的一个约束极小化问题。问题A的输出，也就是通过优化技术制定的飞行计划常规状况下多是表现为一个四元组序列：（经度，纬度，高度，速度）。航线的制定不仅要考虑物理定律，同时还需要实际考虑到航空管制区以及高度授权。其中：

1）航空管制区是无论如何不能进入的；

2）很多航班只能在特定高度飞行。

问题A的最优解答，即最佳飞行计划必须含括3点：首先是出发地到目的地的路径最短；其次是最优的巡航高度，以及最优的起飞和降落计划；最后是综合考虑飞行时间与燃油，从而得到最佳飞行计划。

对于问题B，输入上和问题A基本相同，但比问题A多出的一项则是目前时刻所得到的飞行历史，输出即是预测的航班到达时间。问题B的最优解答，也就是最优预测当然是和实际的飞机到达时间最大限度地接近才可称为理想。机场得到飞机的到达时间越发准确，才能更趋现实合理地调控资源安排，包括跑道、登机口和人员。

问题A和问题B并非相互独立，而是相互影响，相互制约的。显然，航班的时空位置会影响飞机抵达跑道和登机口的时间；而飞机的到达时间则会关系到机场资源的使用，例如跑道以及登机口的使用冲突等，从而导致机场的拥堵，间接影响其他航线的调度计划。

本文提出了国内航班调度的优化模型，讨论如何利用大数据，包括飞行历史、天气、航空管制以及其他数据来更好地实时调整航班的飞行路线，并准确预测飞机的到达时间，从而更为有效地实施航班的安排管理，使得航空公司的总体成本（包括延误时间和燃油费用）最低。

对于相关的研究工作，由于目前还未有专用模拟器问世可用来对如此复杂问题进行建模，因此目前仍然少见关于航班调度的研究。

2航班调度问题模型

在本节中，针对航班调度模型的各个要素进行研究抽象，从而分别建立起问题A和问题B的数学模型。

2.1 各要素的量化分析处理

2）历史与当前的飞行数据FD（Flight Data），包括航班出发与到达的地点和时间、计划的航班路线与实际的航班路线等，可见细节需要提供到燃油、航空公司、飞机型号、航班号、出发机场位置、到达机场位置、预计出发时间、实际出发时间、预计到达时间、实际到达时间、到达的航站楼位置、到达的登机口位置、若干航班计划路线（一个航班由于在飞行过程中通常都会调整飞行路线，每次调整都作为一次计划的航班路线，因此多会对应若干航班计划路线）、航班飞行过程中实际的地理位置（经纬度，通常每分钟更新一次）。

3）航空管制数据CD（air traffic Control Data），包括航空管制的时间、区域等，这些数据对航班的到达时间具有重大影响。一般来说管制区是需要进行交通管制服务的区域。国内将管制区域分为A、B、C、D四类。其中，A类空域为高空管制区，高度为6600米以上高空。高空管制区由高空区域管制室负责。在高空管制区只允许IFR飞行（仪表飞行规则，Instrument flight rules）；B类为中低空管制区，高度为6600米以下的空域。B类空域接受IFR和VFR飞行（目视飞行规则，Visual Flight Rules）。但VFR飞行须经航空器驾驶员申请并经中低空区域管制室批准方可进入现实发生；C类空域为进近管制空域，通常设置在一个或几个机场附近的航路汇合处，也是中低空管制区与塔台管制区的连接部分。其高度为6000米以下、最低高度层以上，水平范围通常以机场基准点为中心半径50公里或走廊进出口以内的除机场塔台管制范围之外的空间；D类为塔台管制区，通常包括起飞航线、第一等待高度层及其以下、地球表面以上的空间和机场机动区。为了简化问题，一般在研究中假设所有管制区的形状均为凸多边形，坐标给定，且位置保持不变。航班是绝对不允许进入航空管制区的。在本文的模型中提出如下假定：一旦航班进入航空管制区，成本函数将设定为无穷大，从而强迫其绕过航空管制区。文中模型假设所有的航空管制区都为多边形且位置已知，虽然实际情形是航空管制区会按时间变化，但在模型中则假设其恒定不变。

4）湍流区位置数据TD（Turbulent zones Data）每时每刻均处于变化之中，因此必须将数据做好提前监测与储备，包括区域的坐标位置，高度的上下界。为了简化问题模型以及算法求解的复杂度，假设湍流区的数目有限，同时与航空管制区类似，一般也是假设湍流区都为凸多面体。如果飞机进入湍流区，将会导致飞机的损耗，以及燃油的消耗，此时即需对成本函数添加合适的惩罚项。和航空管制区略显差别的一点就是，湍流区会一直变化。

5）天气数据WD（Weather Data），包括历史与实际的天气数据，细节到需要遍及全国范围的若干个气象站的实时数据。对民航影响较大的天气数据主要是能见度、风速、温度等，一般来说，民航机场都装备了功能齐全的气象站，因此可以直接利用站点提供的数据。其中，风速数据是2D数据，包含实际风速和预测风速，地面风、速温、能见度等。

2.2 模型构建研究

3航班调度最优化解决方案

由于民航数据的敏感性，因此本文仅只对航班调度最优化进行了理论上技术方案的实现解析。目前也正在和各航空公司以及民航总局积极探讨数据的共享和使用方式，预计在不久的将来可以验证本文所提出的框架和方法的有效性。

3.1 问题A的解决方案

针对问题A，方案的总体思路是首先设计一个初始路线，其次将根据风速对航线做微观调整，最后则根据燃油以及机场的资源情况来系统确定飞机起飞、降落、巡航的速度。下面即针对解决方案的3个步骤展开深入、全面论述。

首先，在作初始路线设计时，禁飞区是完全不能闯入的，因此必须避开。在避开禁飞区的前提下，通过确定地图上两点之间的最近距离，找到初始路径。可以通过时下的众多算法来确定最短的距离，包括著名的Dijkstra算法等[3]。

其次，要根据风向和风速来调整已经得到的初始路径。一般来说，燃油消耗是和速度直接相关的。而飞机的实际速度是飞机本身的速度与风速的组合，因此合理利用风速可以在相当程度上有助于成本的降低。已有的动态规划算法可以在一定范围成功搜索到能够最为有效利用风能的路线。

最后，基于起飞、巡航、降落的燃油消耗模式的不同，还需要进一步考虑飞机的高度和速度问题，其中最为核心的就是飞机开始降落的时间点。如果飞机离目的地仍然遥远，就会爬升到最高，再开始巡航，最后降落。如果时间也较为充裕，可以适当减速，从而降低燃油消耗。因此巡航的速度以及飞机降落时间点是研究中的两个关键因素。

3.2 问题B的解决方案

对于问题B，研究采用人工智能和机器学习的方法来进行大数据时代航班到达时刻的准确预测。该方法分为两个部分：其一是从历史数据中提炼可能会对航班到达时刻有关系的特征表达；其二是对第一部分所提取特征表达进行需求分类或者预测。

在第一部分，对航班到达时刻有作用影响的，也可说是前一节中提到的能做各种利用的特征表达有如下若干种，具体包括历史的预测到达跑道（登机口）时间、真实的到达跑道（登机口）时间、预定起飞时间、实际起飞时间、平均延误时间、平均出租车等候时间、目的地机场的平均风速、最近测量的风速＼温度＼能见度值、以上数据一阶差分、到达机场的代码、目的地和始发地之间的距离、航班从出发地到目前位置的历史平均速度、出发机场以及到达机场的经纬度等。

在提取了上述的特征以后，就可以采取多阶段的方法来进行到达时刻的预测，包括利用回归模型（regression models）[4]，梯度推进机（gradient boosting machines）[5]等方法。在不同的阶段，也将使用不同的特征。例如首先可以使用线性模型对低维特征进行初始预测；为了挖掘数据中的非线性信息，还可以使用梯度推进机，或者随机森林（random forest）[6]等方法；同时，实施方案中更需要考虑稀疏特征，以及对预测结果的微调等。

4 结束语

在本文中，重点围绕大数据的航班调度问题进行了形式化的描述。而后针对这一此形式化描述，综合考虑了对航班调度能够产生影响的所有参数，从而建立了大数据时代的航班调度模型。最后则从理论上给出了该航班调度模型的最优化解决方案。

参考文献：

[1] J. Leber. A data-crunching prize to cut flight delays. 2013， MIT Technology Review. [2013-04-03]. http：//www.technologyreview.com/news/513141/a-data-crunching-prize-to-cut-flight-delays.

[2] S. Altus. Effective flight plans can help airlines economize.[2009-03-09]. http：//www.boeing.com/commercial/aeromagazine/articles/qtr_03_09/article_08_1.html.

[3] DIJSTRA E. A note on two problems in connexion with graphs[J].Numerische Mathematik， 1959， 1（4）：269–271.

[4] BOUSSON K， MACHADO P. 4d flight trajectory optimization basedon pseudo spectral methods[J]. Engineering and Technology， 2010， 4（1）： 471–477.

[5] D Merle. Flight path optimization for an airplane [D].Trondheim： Norwegian University of Science and Technology， 2011.

[6] ATKINS EM. Flight plan management with George Jetson as pilot [C] //AAAI Spring Symposium 2004. Palo Alto： AAAI， 2004：1-6.