-
摘要:
不正常航班恢复问题研究通常基于固定航班中转时间，忽视了实际航班中转时间的改变对航班恢复带来的影响。对此，依据全国235个机场的全部运营航班数据抽取机场-航班特征，构建了基于LightGBM的航班中转时间预测模型，预测航班的有效中转时间，数值结果显示，航班中转时间预测模型预测的均方根误差为6.783 min。构造了基于有效中转时间的不正常航班恢复模型，并针对性地设计了求解该模型的列向量生成算法，构造的模型通过取消、改变计划时间、更换飞机等方式，分别在最小化航班延误时间、取消个数、换飞机个数的目标下，解决机场流量下降、机场关闭、飞机维修等不正常条件下的航班恢复问题。通过航空公司实际运行数据测试证明，基于有效中转时间预测的不正常航班恢复技术有效，在大规模航班恢复的情况下，可以将总延误时间减少34.2%。将列向量生成算法与时空网络算法的结果进行对比，所提出的恢复方法能降低航班恢复代价。
Abstract:In previous studies, the general method for flight recovery problem used fixed flight transit time, rather than considered the result of flight transit time changes in real airports. We propose a LightGBM model to predict accurate transit time based on the airport-flight features from total 235 airports and all flights in China. The numerical results show that our model has 6.783 minutes root mean square error using real flights data. We construct an irregular flight recovery model based on effective transit time, and specifically design a column vector generation algorithm to solve this model. This algorithm can solve the problem of airport traffic flow decrease, airport closure, aircraft maintenance and other irregular conditions under the goal of minimizing flight delays, the number of cancellations, and the number of aircraft changes by canceling, changing the planned time, and replacing aircraft. Tests on actual operating data of airlines prove that the irregular flight recovery method based on transit time prediction is effective. The real case of large-scale flight delays test shows the total delay time can be reduced by 34.2%. The comparison between the spatio-temporal network algorithm and the column vector generation algorithm shows that the proposed flight recovery method also can reduce the recovery cost under the premise of the same recovery result.
-
图 1 离港航班个数与月份关系
Figure 1. Relationship between the number of departure flights and the months
图 2 2018年5月2日离港航班个数与时间关系
Figure 2. Relationship between the number of departure flights and the time on May 2, 2018
图 3 列向量生成算法解决不正常航班恢复问题的流程
Figure 3. Flowchart for solving irregular flight recovery problems by column vector generation algorithm
图 4 列向量生成算法主问题的流程
Figure 4. Flowchart of main problem using column vector generation algorithm
图 5 列向量生成算法子问题的流程
Figure 5. Flowchart of subproblem using column vector generation algorithm
图 6 列向量生成算法与时空网络模型运行时间对比
Figure 6. Comparison of operation time between column vector generation algorithm and spatio-temporal network model
表 1 数据结构特征
Table 1. Data structure characteristics
特征 类型 例值 航班号 String CA1234 日期 String 2018-05-02 出发机场 String HGH 到达机场 String SZX 飞机注册号 String B2345 机型 String 319/131 预计离港时间 String 2018-05-02 18:50 前序到达时间 String 2018-05-02 18:05 雪 String 弱雪 风 String 尘卷风 雨 String 小雨 沙 String 浮尘 雾 String 轻雾 
下载: 导出CSV
表 2 不同模型航班中转时间性能对比
Table 2. Performance comparison about different models' flight transit time
模型 RMSE/min MAE/min 训练时间/s LightGBM 6.783 5.467 66 GBDT 7.197 5.948 77
下载: 导出CSV
表 3 算例基本参数
Table 3. Basic parameters of calculation examples
算例 航班个数 飞机个数 飞机故障个数 机场个数 机场关闭个数 F50 50 19 0 24 0 F100 100 37 1 40 0 F200 200 71 0 63 1 F400 400 144 3 83 0 F800 800 305 1 143 0
下载: 导出CSV
表 4 算例成本参数
Table 4. Cost parameters of calculation examples
算例 取消成本 延误成本 换飞机成本 机场的飞机不平衡成本 F50 800 1 5 1 000 F100 500 1 5 1 000 F200 800 1 10 1 000 F400 500 1 10 1 000 F800 500 1 10 800
下载: 导出CSV
表 5 模型A的计算结果
Table 5. Calculation results of Model A
算例 取消个数 总延误时间/min 换飞机个数 飞机不平衡个数 成本 模型运算时间/s F50 0 545 2 0 555 6 F100 0 1 283 3 0 1 298 28 F200 0 2 895 10 0 2 995 66 F400 1 5 047 30 0 5 847 248 F800 0 10 358 29 0 10 648 760
下载: 导出CSV
表 6 模型B的计算结果
Table 6. Calculation results of Model B
算例 取消个数 总延误时间/min 换飞机个数 飞机不平衡个数 成本 模型运算时间/s F50 0 423 7 0 458 2 F100 0 1 061 16 0 1 141 7 F200 0 2 376 29 0 2 666 22 F400 1 4 877 30 0 5 677 90 F800 1 10 157 30 0 10 957 288
下载: 导出CSV
表 7 模型C的计算结果
Table 7. Calculation results of Model C
算例 取消个数 总延误时间/min 换飞机个数 飞机不平衡个数 成本 模型运算时间/s F50 0 362 2 0 372 6 F100 0 755 3 0 770 29 F200 0 1 941 2 0 1 961 80 F400 1 3 265 25 0 4 015 273 F800 0 6 814 19 0 7 004 870
下载: 导出CSV
表 8 模型D的计算结果
Table 8. Calculation results of Model D
算例 取消个数 总延误时间/min 换飞机个数 飞机不平衡个数 成本 模型运算时间/s F50 0 269 7 0 304 2 F100 0 629 13 0 694 7 F200 0 1 504 21 0 1 714 20 F400 1 3 163 30 0 3 963 92 F800 0 6 680 30 0 6 980 237
下载: 导出CSV
表 9 算例F800的航班中转时间分布
Table 9. Flight transit time distribution of scenario F800
固定中转时间/min 能够完成中转任务的航班比例/% 30 0 40 0.81 60 36.04 75 63.15
下载: 导出CSV
表 10 基于模型D的优化器实验结果
Table 10. Experimental results of optimizer based on Model D
算例 LP IP 最优间隔比例/% F50 304.00 304 0 F100 694.00 694 0 F200 1 714.00 1 714 0 F400 3 960.67 3 963 0.059 F800 6 980.00 6 980 0
下载: 导出CSV
-
[1] 赵秀丽, 朱金福, 郭梅. 不正常航班延误调度型及算法[J]. 系统工程理论与实践, 2008, 28(4): 2-4. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200804018.htmZHAO X L, ZHU J F, GUO M. Study on modelling and algorithm of irregular flight delay operation[J]. Systems Engineering-Theory & Practice, 2008, 28(4): 2-4(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200804018.htm [2] LIANG Z, XIAO F, QIAN X, et al. A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility[J]. Transportation Research Part B: Methodological, 2018, 113: 70-90. doi: 10.1016/j.trb.2018.05.007 [3] YU G, BARD J F, ARGUELLO M F. Optimizing aircraft routings in response to groundings and delays[J]. ⅡE Transactions, 2001, 33(10): 931-947. [4] 乐美龙, 王婷婷, 吴聪聪. 基于改进的GRASP算法的飞机优化恢复研究[J]. 江苏科技大学学报(自然科学版), 2013, 27(2): 166-170. https://www.cnki.com.cn/Article/CJFDTOTAL-HDCB201302013.htmLE M L, WANG T T, WU C C. Study on aircrafts optimal recovery based on improved GRASP algorithm[J]. Journal of Jiangsu University of Science and Technology(Natural Science Edition), 2013, 27(2): 166-170(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HDCB201302013.htm [5] KE G, MENG Q, WANG T, et al. A communication-efficient parallel algorithm for decision tree[C]//Advances in Neural Information Processing Systems, 2016: 1279-1287. [6] TEODOROVIĆ D, GUBERINIĆ S. Optimal dispatching strategy on an airline network after a schedule perturbation[J]. European Journal of Operational Research, 1984, 15(2): 178-182. doi: 10.1016/0377-2217(84)90207-8 [7] JARRAH A I, YU G, KRISHNAMURTHY N, et al. A decision support framework for airline flight cancellations and delays[J]. Transportation Science, 1993, 27(3): 266-280. doi: 10.1287/trsc.27.3.266 [8] YAN S, LIN C G. Airline scheduling for the temporary closure of airports[J]. Transportation Science, 1997, 31(1): 72-82. doi: 10.1287/trsc.31.1.72 [9] CAO J M, KANAFANI A. Real-time decision support for integration of airline flight cancellations and delays. Part I: Mathematical formulation[J]. Transportation Planning and Technology, 1997, 20(3): 183-199. doi: 10.1080/03081069708717588 [10] CAO J M, KANAFANI A. Real-time decision support for integration of airline flight cancellations and delays. Part Ⅱ: Algorithm and computational experiments[J]. Transportation Planning and Technology, 1997, 20(3): 201-217. doi: 10.1080/03081069708717589 [11] THENGVALL B G, YU G, BARD J F. Multiple fleet aircraft schedule recovery following hub closures[J]. Transportation Research Part A: Policy and Practice, 2001, 35(4): 289-308. doi: 10.1016/S0965-8564(99)00059-2 [12] THENGVALL B G, BARD J F, YU G. A bundle algorithm approach for the aircraft schedule recovery problem during hub closures[J]. Transportation Science, 2003, 37(4): 392-407. doi: 10.1287/trsc.37.4.392.23281 [13] 白凤, 朱金福, 高强. 基于列生成法的不正常航班调度[J]. 系统工程理论与实践, 2010, 30(11): 2036-2045. doi: 10.12011/1000-6788(2010)11-2036BAI F, ZHU J F, GAO Q. Disrupted airline schedules dispatching based on column generation methods[J]. Systems Engineering-Theory & Practice, 2010, 30(11): 2036-2045(in Chinese). doi: 10.12011/1000-6788(2010)11-2036 [14] 汪瑜, 孙宏. 基于航班时空网络模型的网络型机队随机规划方法[J]. 数学的实践与认识, 2018, 48(6): 58-68. https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS201806007.htmWANG Y, SUN H. A network-type fleet stochastic planning methodology based on flight time space network model[J]. Mathematics in Practice and Theory, 2018, 48(6): 58-68(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS201806007.htm [15] 田倩南, 李昆鹏, 李文莉, 等. 受扰航班恢复问题的优化方案研究[J]. 管理学报, 2018, 15(10): 1081-1088. doi: 10.3969/j.issn.1672-884x.2018.10.017TIAN Q N, LI K P, LI W L, et al. The research on optimization of disrupted flights recovery problem[J]. Chinese Journal of Management, 2018, 15(10): 1081-1088(in Chinese). doi: 10.3969/j.issn.1672-884x.2018.10.017 [16] QIANG H A O, WEI F A N. Flight recovery model based on consideration of passenger satisfaction robustness[J]. Modern Electronics Technique, 2018, 2018(18): 32. [17] 唐小卫, 高强, 朱金福. 不正常航班恢复模型的贪婪模拟退火算法研究[J]. 预测, 2010, 29(1): 66-70. https://www.cnki.com.cn/Article/CJFDTOTAL-YUCE201001010.htmTANG X W, GAO Q, ZHU J F. Research on greedy simulated annealing algorithm of irregular flight schedule recovery model[J]. Forecasting, 2010, 29(1): 66-70(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-YUCE201001010.htm [18] 吴刚, 严俊. 不正常航班恢复的一种改进的列生成算法[J]. 南京航空航天大学学报, 2014, 46(2): 329-334. https://www.cnki.com.cn/Article/CJFDTOTAL-NJHK201402024.htmWU G, YAN J. Improved column generation algorithm for disrupted airline schedules recovery[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2014, 46(2): 329-334(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NJHK201402024.htm [19] 乐美龙, 王婷婷, 吴聪聪. 多机型不正常航班恢复的时空网络模型[J]. 四川大学学报(自然科学版), 2013, 50(3): 477-483. https://www.cnki.com.cn/Article/CJFDTOTAL-SCDX201303010.htmLE M L, WANG T T, WU C C. The time-band model for recovery of multi-type aircrafts' disrupted flights[J]. Journal of Sichuan University(Natural Science Edition), 2013, 50(3): 477-483(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SCDX201303010.htm [20] FRIEDMAN J H. Greedy function approximation: A gradient boosting machine[J]. Annals of Statistics, 2001, 29(5): 1189-1232. [21] KE G, MENG Q, FINLEY T, et al. LightGBM: A highly efficient gradient boosting decision tree[J]. Advances in Neural Information Processing Systems, 2017, 30: 3146-3154. [22] 王芳杰, 王福建, 王雨晨, 等. 基于LightGBM算法的公交行程时间预测[J]. 交通运输系统工程与信息, 2019, 19(2): 116-121. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201902017.htmWANG F J, WANG F J, WANG Y C, et al. Bus travel time prediction based on light gradient boosting machine algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(2): 116-121(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201902017.htm [23] 顾桐, 许国良, 李万林, 等. 基于集成LightGBM和贝叶斯优化策略的房价智能评估模型[J]. 计算机应用, 2020, 40(9): 2762-2767. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY202009043.htmGU T, XU G L, LI W L, et al. Intelligent house price evaluation model based on ensemble LightGBM and Bayesian optimization strategy[J]. Journal of Computer Applications, 2020, 40(9): 2762-2767(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY202009043.htm [24] ZHANG L, YANG H, WANG K, et al. Measuring imported case risk of COVID-19 from inbound international flights-A case study on China[J]. Journal of Air Transport Management, 2020, 89: 101918. -
下载:
点击查看大图
计量
- 文章访问数: 277
- HTML全文浏览量: 83
- PDF下载量: 182
- 被引次数: 0
