罗赟骞，陈志杰，汤锦辉，朱永文

（1.中国人民解放军95899部队，北京100085；2.国家空域技术重点实验室，北京100085；3.中国人民解放军95865部队，北京100085）

采用支持向量机回归的航班延误预测研究

罗赟骞*1,2,3，陈志杰1,2，汤锦辉1,2，朱永文1,2

（1.中国人民解放军95899部队，北京100085；2.国家空域技术重点实验室，北京100085；3.中国人民解放军95865部队，北京100085）

针对航班延误难以预测的问题，采用支持向量机回归方法建立航班到港延误预测模型.首先，采用相空间重构理论计算到港延误的延迟时间、嵌入维数和最大Lyapunov指数，发现到港延误时间序列存在混沌特性；将航班到港延误时间序列进行相空间重构，并结合执飞该航班的航空器在上游机场的离港延误构建模型的输入向量；其次，将粒子群算法、差分进化算法和遗传算法进行比较，用于选择最优的模型参数，实验表明，差分进化算法能够以较高概率获得最优的预测模型；最后，比较该模型、单一因素预测模型和相关向量机预测模型的航班延误预测性能.结果表明，该模型的预测性能明显优于另外两种模型，能够有效预测航班延误.

航空运输；航班延误预测；支持向量机回归；航班延误；相空间重构；差分进化算法

1 引 言

随着航空运输业的迅猛发展，空中交通流量日益增加、机场容量的缺乏及自然灾害等不确定因素导致航班延误日益严重，不仅影响旅客的出行，增加航空公司运营成本，还增加了空中交通管制难度.因此，对航班延误进行精确预测具有重要的现实意义，可以为航空公司和机场运行决策提供依据，减少航班延误带来的损失；可以为旅客出行提供决策依据，保障旅客的体验度.

目前国内外相关学者对预测航班延误强度和航班是否发生延误的方法进行了研究.文献[1]提出了基于贝叶斯网络的航班延误传播模型，分析航班衔接时的延误传播过程，用于预测下游机场航班的离/到港延误；文献[2]建立了多机场多航班有色—时间Petri网模型，从理论上预测单架航班从源机场起飞的各个飞机的下游机场是否出现航班延误并预测延误时间；文献[3]分析了单架航班执行多个任务时航班延误状态之间的关系，构建航班延误状态空间模型；文献[4]对连续进港航班之间的延误传递情况进行了分析，建立了延误状态空间模型；文献[5]提出一种将时间和网络延误状态作为解释变量的基于网络的空中交通延误预测模型，该模型能够较好地预测城市对之间的延误状态和延误强度，并计划对单航班延误进行预测；文献[6]采用回归分析方法识别产生延误的重要因素，使用支持向量机分类方法预测是否会发生延误，使用非参数二次回归算法预测延误强度；文献[7]提出使用数据挖掘方法对航班是否发生延误及延误强度进行预测.

综上所述，现有航班延误预测模式主要分为两类：一类是利用单架航班在上下行衔接机场之间的航班运行数据建立模型进行航班延误预测；另一类是利用所有航班长期运行历史数据建立模型进行航班延误预测，两类航班延误预测性能都不高.本文将针对在一天中执行多次任务的航空器，利用其在下游某一机场的历史航班运行数据和当天上游机场的航班运行数据，采用支持向量机回归（SVR，Support Vector Machine Regression）[8]方法建立航班延误预测模型，预测下游某一机场的航班到港延误.

2 支持向量机回归原理

假设样本为T={(x1,y1),…,(xl,yl)}，在线性条件下，SVR使用线性函数 f(x,w)=(w∙x)+b对样本进行拟合.在非线性条件下，则将样本映射到高维特征空间，在高维特征空间中建立线性模型f(x,w)=(w∙ϕ(x))+b.其中，ϕ(x)是将样本映射到高维空间的非线性变换，SVR可以表示为

式中 ‖w‖2代表与模型复杂度相关的因素；c为惩罚系数；模型采用ε不敏感损失函数；松弛变量 ξi，表示样本偏离ε不敏感区域的程度.惩罚系数c和不敏感系数ε对SVR的性能有着重要的影响.

对于式（1），通过求解模型的Lagrange对偶问题获得原问题的最优解.

式中 k(xi,xj)称为核函数，满足Mercer条件且k(xi,xj)=ϕ(xi)∙ϕ(xj).

3 执行多次任务的航空器航班延误分析

各个航空公司在某一段时间内在固定机场之间将执飞相同航班F，而执飞该航班的单架航空器在一天中将执行多次航班飞行任务.设执飞航班F的航空器在一天飞行过程中起降机场的数量为P(P≥2)，如果航空器在上游机场i发生离港航班延误di，那么航班F在下游机场 j到港时将受到波及，产生到港延误aj.

从航旅纵横获取中国某航空公司航空器于2013年12月30日至2014年6月24日在机场A→B→C之间依次执飞相同航班的160组航班延误数据为例，分析上下游航班延误之间的关系，A、B机场的离港延误和C机场的到港延误如图1所示.

图1 上下游机场的航班延误曲线Fig.1 Curve of upstream and downstream airports’delay

由图1可知机场C的某航班到港延误与执飞该航班的航空器在机场A和机场B的离港延误变化趋势较为一致，采用Matlab的Corr函数求得机场C到港延误与机场A离港延误之间的相关系数为0.806 4，机场C到港延误与机场B离港延误之间的相关系数为0.984 8，上游机场的离港延误与下游机场到港延误的相关性明显，并且离下游机场越近的上游机场的离港延误对下游机场的到港延误影响越强.因此，可用预测当天的上游机场离港延误及下游机场历史到港延误，建立基于SVR的航班延误预测模型，对当天下游机场的航班延误进行预测.

4 基于SVR的航班延误预测模型

以航班F在下游机场 j的N天历史航班延误数据序列aj(n)(n=1,…,N)和执飞该航班的航空器在上游机场i产生的N天历史离港航班延误时间序列di(n)(n=1,…,N)，建立基于SVR的航班延误预测模型，其结构如图2所示.

图2 航班延误的支持向量机回归预测模型Fig.2 Flight delay’s predicting model using SVR

如图2所示，首先将上、下游机场航班延误原始数据映射为输入样本向量，然后对输入样本向量进行数据预处理，通过支持向量机回归训练寻找模型最佳的参数，构建航班延误预测模型，最后

混沌理论中的相空间重构方法[9]将非线性序列映射到高维空间，可以有效地获取非线性序列中存在的动力学特征信息.对于给定的航班延误数据时间序列{x (n),n=1,2,…,N},采用相空间重构法，可以得到N-(m-1)τ-1个新的数据空间：[x(n-(m-1)τ),…,x(n-τ),x(n)].其中，m为航班延误时间序列的嵌入维数，τ为时间延时.输入预测样本向量对航班延误进行预测.

4.1 航班延误数据输入向量

由于航班延误受到气象、交通流量控制、航空公司和机场等多种因素的影响，航班延误具有很强的非线性特性，如何从历史数据中获取其内在信息和规律，对准确预测航班延误非常重要.

在构造航班延误数据输入向量时，将下游机场航班延误的历史数据作为预测的内在因素，采用相空间重构的方法获取内在因素的输入变量[aj(n-(m-1)τ),…,aj(n-τ),aj(n)],n∈[(m-1)τ+1, N-1]，而当天上游机场的航班离港延误作为外在因素的输入变量di(n+1)，n∈[(m-1)τ+1,N-1].最终得到SVR的输入变量向量Y(n)=[aj(n-(m-1)τ),…, aj(n-τ),aj(n),di(n+1)]，n∈[(m-1)τ+1,N-1].

利用该输入变量向量可对航班延误进行预测，可以构造映射 f:Rm→R,使得

4.2 数据预处理

研究表明对SVR的输入数据进行预处理有利于提高SVR预测的精度和速度，通常将数据归一化到[0,1]或[-1,1]的范围内，一般采用线性函数的归一化方法，也可以采用范数的规格化方法

式中 xi,yi∈R，实验表明采用范数的归一化方法优于采用线性函数的归一化方法，本文将采用范数的归一化方法.

4.3 模型参数的选择

SVR的核函数有线性核函数、多项式核函数、RBF核函数和sigmoid核函数.研究表明RBF核函数相比其它核函数不仅具有较少的参数还具有良好的性能，本文将选择RBF核函数进行延误预测.确定核函数后还需要确定惩罚系数c、不敏感系数ε，以及核函数中的系数δ.参数选择可以采用网格搜索方法或优化算法，考虑到模型在实际应用中的可行性，本文将选用优化算法进行模型参数选择.优化算法采用5-折交叉验证得到的均方差值为适应度值进行模型参数的选择，当适应度值达到预定值或者连续多次不变时，训练停止.最后，将最小适应度值对应的参数作为模型参数构建航班延误预测模型，对航班延误进行预测.

5 实例分析

本文将以第3节中获取的航班延误数据为算例，应用第4节中的模型进行航班延误预测，并对结果进行分析.

5.1 航班延误时间序列相空间重构参数的选取

在重构相空间中，时间延迟τ和嵌入维数m的选取好坏对于是否能够反映系统动力学特性非常重要.本文将采用互信息法[9]计算延时，使用Cao方法[10]对m进行选取，采用小数据量方法计算Lyapunov指数[9]，以检验C机场到港航班延误的时间序列是否存在混沌现象.

由图3的互信息函数曲线可知，互信息函数曲线的第一个极小值点的延时为1天；通常取互信息曲线达到第一个极小点所对应的延时作为嵌入延迟时间，因此航班延误时间序列的延迟时间取τ= 1天.

图3 互信息函数变化曲线Fig.3 Curve of mutual information method

图4为Cao定义的变量E1(m)和E2(m)的变化曲线，E1(m)是一个由m到m+1维的变化参数，随着m的增大，E1(m)到达饱和时，m+1即为最小嵌入维数.由图4可知，E1(m)随着m的增大趋于饱和，当m=6时E1(m)变化较小，那么取m=7为航班延误时间序列的嵌入维数.E2(m)是一个区分确定性混沌信号和随机信号的变量，如果是随机信号E2(m)对任何m为1，对于混沌信号E2(m)将不会始终为1.由图4可知E2(m)在1附近上下波动，因此该延误序列为混沌时间序列.

图4 Cao方法变化曲线Fig.4 Curve of Cao method

图5中，k为离散事件演化步数，y(k)为所有邻接点对经过k步演化后的距离对数平均值.由图5可知，k为8之前曲线近似为一条直线，该直线的斜率为延误时间序列的最大Lyapunov指数，由线性最小二乘法得到该直线斜率为0.166 6，为正.则该延误时间序列具有混沌特性.

图5 最大Lyapunov指数计算曲线Fig.5 Curve of computing maximal Lyapunov exponent

利用相空间重构理论对第3节中的下游机场C的到港航班延误时间序列进行相空间重构，结合当日上游A机场同一航空器的离港延误得到153个样本，利用前145个样本进行模型的训练，后8个样本用于预测.

5.2 采用优化算法的SVR模型参数选择

本文采用Libsvm工具箱[11]实现回归预测模型，实验中用到的所有程序都在Matlab 7.12中开发，所用计算机配置为Intel(R)CPU Xeon(R) W3503@2.40GHz处理器，2GB内存，操作系统为Windows XP.

根据经验，模型选择的参数搜索区间为：c∈[0.1,1 000]，ε∈[0.001,1]，δ∈[0.001,32].使用粒子群算法（PSO）、差分进化算法（DE）和遗传算法（GA）对模型参数进行选择.所有优化算法的种群个体数NP=20，最大迭代次数为G=100，如果适应度值连续20次变化小于1则停止搜索.DE算法采用DeMat工具箱[12]实现，使用标准的DE/rand/1模式，其参数设置为：变异因子F=0.85，交叉概率CR=1.PSO算法采用PSOT工具箱[13]实现，使用线性递减惯性权重的算法，算法的参数设置为：wmax=0.9，wmin=0.4，c1=c2=2.GA算法采用Gatbx工具箱[14]实现，采用二进制编码的遗传算法的参数设置为：交叉概率=0.7，变异概率=0.1.

优化算法随机对模型的最优参数进行搜索，每次搜索结果将会不同，为了比较算法搜索的稳定性，将3种优化算法各运行50次.为了验证3种优化算法得到模型的泛化能力和预测精度，使用训练和预测时得到的均方误差（Mean Square Error,MSE）和平均相对误差（Mean Absolute Percentage Error,MAPE）对这几种算法得到的模型进行比较.MSE和MAPE的计算方法为

式中 yi和分别为某时刻的实际和预测航班延误.

三种优化算法的训练和预测时的 MSE、MAPE如图6–图9和表1所示.

图6 训练时的MSEFig.6 MSE of the model training

图7 训练时的MAPEFig.7 MAPE of the model training

图8 预测时的MSEFig.8 MSE of the model

图9 预测时的MAPEFig.9 MAPE of the model

表1 三种优化算法性能比较Table 1 Comparison of the three algorithms’s performance

由表1和图6、图7可知，PSO算法在模型训练时能够获得最小的MAPE/MSE值，但其波动较大，DE算法能够获得平均和最大MAPE/MSE的最小值，GA算法性能介于两种算法之间.以三种算法在训练时得到的平均MSE/MAPE中位数作参考，统计三种优化算法得到最优模型的概率，PSO、DE和GA算法训练时得到的MSE小于1 186.00的比例分别为26%、86%和64%，MAPE小于34.80%的比例分别为54%、86%和58%，训练模型的平均时间分别为27 s、21 s和25 s.因此，DE算法与另外两种算法相比，进行模型训练时具有较好的稳定性，能够以较高的概率和速度获得最优模型.

由表1和图8、图9可知，PSO、DE和GA算法获得模型在预测时能够分别得到最小、平均和最大MAPE/MSE值的最小值.以三种算法获得模型预测时得到的平均MSE/MAPE中位数作参考，PSO、DE和GA算法获得模型预测时的MSE小于137.96的比例分别为44%、86%和60%，MAPE小于16.01%的比例分别为50%、86%和58%.因此，DE算法与另外两种算法相比，获得模型进行预测时具有较好的稳定性，能够以较高的概率获得最优预测值.综上所述，DE算法能够以较高的概率获取最优模型，本文将采用DE算法获取模型的最优参数.

5.3 预测性能分析

图10 采用不同因素的延误预测分析Fig.10 Analysis of predicting delay using different factors

为了验证本文提出模型的优越性，将本文的模型与只采用下游机场航班到港延误历史序列而不考虑上游机场离港航班延误构建的单一因素SVR模型进行比较.单一因素SVR模型也使用DE算法选择模型参数，模型参数设置范围不变，两个模型得到的最优预测值如图10所示.由图10可知，本文模型得到MAPE最小值为15.89%，MSE为136.06，平均预测误差为9.35 min；单一因素SVR模型得到MAPE最小值为28.50%，MSE为1169.67，平均预测误差为23.89 min.因此，本文预测模型的预测精度，要优于单一因素SVR模型的预测精度，平均预测误差能够减少14.54 min.

为了进一步验证本文提出模型的有效性，将目前广泛应用的相关向量机（RVM，Relevance Vector Machine）[15]构建的预测模型与本文构建的预测模型进行比较.RVM采用SparseBayes工具箱[15]实现，RVM使用与本文相同RBF核函数，核函数的参数（δ∈[0.001,1 000]）使用DE算法进行选择，两个模型得到的最优预测值如图11所示.

图11 采用SVR和RVM的延误预测分析Fig.11 Analysis of predicting delay using SVR and RVM

由图11可知，RVM预测模型得到MAPE为18.97%，MSE为220.98，平均预测误差为10.97 min；本文提出的模型与RVM预测模型相比，MAPE能够提高3.08%，平均预测误差能够减少1.62 min.因此，本文提出的模型与RVM预测模型相比，在整体上预测误差更小，更适合航班延误预测.

6 研究结论

（1）本文构建了基于SVR的航班到港延误预测模型，并分析航班到港延误时间序列的特点，发现到港延误时间序列具有混沌特性，采用相空间重构理论对到港延误数据进行相空间重构，并结合执飞该航班的同一航空器在上游机场的离港延误，客观地确定了航班延误预测模型所需的输入样本向量.

（2）本文比较了PSO、DE和GA算法对SVR模型参数选择的性能，发现DE算法不仅能够以较高概率和较短时间获得最优模型，并且获取的模型在延误预测时具有很高的精度，可选用DE算法用于构建预测模型.

（3）本文提出的预测模型与采用单一因素的预测模型相比，能够大幅提高预测精度；与RVM构建的预测模型相比，具有更好的预测性能，能够有效地预测航班延误.

[1]李俊生,丁建立.基于贝叶斯网络的航班延误传播分析[J].航空学报,2008,29(6):1598-1604.[LI J S,DING J L.Analysis of flight delay propagation using bayesian networks[J].Acta Aeronautica et Astronautica Sinica,2008,29(6):1598-1604.]

[2]丁建立,陈坦坦,刘玉洁.有色—时间Petri网航班延误模型及波及分析[J].计算机集成制造系统, 2008,14(12):2334-2340.[DING J L,CHEN T T,LIU Y J.Colored-timed petri nets model of flight delays and propagated analysis[J].Computer Integrated Manufacturing Systems,2008,14(12):2334-2340.]

[3]陈海燕,王建东,徐涛.基于延误波及的航班延误状态空间模型[J].信息与控制,2012,41(2):251-255.[CHEN H Y,WANG J D,XU T.A flight delay state-space model based on delay propagation[J]. Information and Control,2012,41(2):251-255.]

[4]陈海燕,王建东,徐涛.动态数据驱动的航班预测研究[J].武汉理工大学学报（交通科学与工程版）,2012,36(3):463-466.[CHEN H Y,WANG J D, XU T.Research on the dynamic data-driven prediction for flight delay[J].Journal of Wuhan University of Technology (Transportation Science&Engineering), 2012,36(3):463-466.]

[5]Juan J R,Hamsa B.Characterization and prediction of air traffic delays[J].Transportation Research Part C: Emerging Technologies,2014,44(3):231-241.

[6]Ra J Bandyopadhyay,R Guerrero.Predicting airline delays[EB/OL].(2012-9-1)[2014-7-7].http://cs229. stanford. edu/proj2012/BandyopadhyayGuerrero-PredictingFlightDelays.pdf.

[7]Tim Stefanski.Predicting flight delays through data mining[EB/OL].(2009-1-1)[2014-7-7].http://cspeople.bu.edu/dgs/courses/cs105/hall_of_fame/timoteo. htm l.

[8]邓乃扬,田英杰.数据挖掘中的新方法——支持向量机[M].北京:科学出版社,2004.[DENG N Y, TIAN Y J.New method in data mining-Support Vector Machine[M].Beijing:Science Press,2004.]

[9]吕金虎,陆君安,陈士华.混沌时间序列分析及其应用[M].武汉:武汉大学出版社,2002.[LU J H,LU J A,CHEN S H.Chaotic time series analysis and its application[M].Wuhan:Wuhan University Press,2002.]

[10]CAO L Y.Practical method for determining the minium embedding dimension of a scalar time series[J].Physica D,1997,100(5):43-50.

[11]Chih Chung Chang,Chih Jen Lin.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):1-27.

[12]Kenneth Price,Rainer Storn.Differential evolution(DE) for continuous function optimization[EB/OL].(2005-12-13)[2014-7-7].http://www1.icsi.berkeley.edu/～storn/ code.html.

[13]Brian Birge.Particle swarm optimization toolbox[EB/ OL].(2006-3-20)[2014-7-7].http://www.mathworks. com/matlabcentral/fileexchange/7506-particle-swarmoptimization-toolbox.

[14]Hartmut Pohlheim.Genetic algorithm toolbox for MATLAB[EB/OL].(2006-1-10)[2014-7-7].http:// www.acse.dept.shef.ac.uk/cgi-bin/gatbx-download.

[15]Mike Tipping.Sparse Bayesian models and the RVM[EB/ OL].(2009-3-13)[2014-7-7].http://www.miketipping. com/index.htm.

Flight Delay Prediction Using Support Vector Machine Regression

LUO Yun-qian1,2,3，CHEN Zhi-jie1,2，TANG Jin-hui1,2，ZHU Yong-wen1,2
(1.The army 95899 of PLA,Beijing 100085,China;2.National Key Laboratory ofAirspace Technology,Beijing 100085,China; 3.The army 95865 of PLA,Beijing 100085,China)

To solve the problem that the flight delay is difficult to predict,the support vector machine regression method is used to establish the flight arrival delay prediction model.First,the phase space reconstruction theory is used to calculate the flight arrival delay’s the delay time,embedded dimension and maximum Lyapunov exponent,and the chaotic characteristics of the flight arrival delay time sequence is found.The phase space of the flight arrival delay time sequence is reconstructed and combined with the departure delay of the upstream airport’s flight using the same aircraft to build the input variable vector of the prediction model.Second,for selecting the optimal model parameters,the particle swarm algorithm, differential evolution algorithm and genetic algorithm are compared,the experiment shows that differential evolution algorithm can get the optimal prediction model with a higher probability.Last,the prediction performance of the model,the single factor prediction model and the relevance vector machine prediction model are compared.The results show that the prediction performance of the model is much better than the other two,the model can effectively predict flight delays.

air transportation;flight delay prediction;support vector machine regression;flight delay; phase space reconstruction;differential evolution algorithm

1009-6744（2015）01-0143-07

：U8

：A

2014-07-10

：2014-08-26录用日期：2014-10-09

国家重大科技专项（2013ZX03001028）；国家科技支撑计划（2011BAH24B10）.

罗赟骞（1981-），男，四川名山人，工程师，博士. ＊

：immortalluo@163.com