留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

大规模飞机排班问题研究综述

张宝成 冉博文

张宝成, 冉博文. 大规模飞机排班问题研究综述[J]. 交通信息与安全, 2024, 42(1): 1-10. doi: 10.3963/j.jssn.1674-4861.2024.01.001
引用本文: 张宝成, 冉博文. 大规模飞机排班问题研究综述[J]. 交通信息与安全, 2024, 42(1): 1-10. doi: 10.3963/j.jssn.1674-4861.2024.01.001
ZHANG Baocheng, RAN Bowen. A Review of Studies on Large-scale Aircraft Scheduling Problems[J]. Journal of Transport Information and Safety, 2024, 42(1): 1-10. doi: 10.3963/j.jssn.1674-4861.2024.01.001
Citation: ZHANG Baocheng, RAN Bowen. A Review of Studies on Large-scale Aircraft Scheduling Problems[J]. Journal of Transport Information and Safety, 2024, 42(1): 1-10. doi: 10.3963/j.jssn.1674-4861.2024.01.001

大规模飞机排班问题研究综述

doi: 10.3963/j.jssn.1674-4861.2024.01.001
基金项目: 

国家自然科学基金项目 71571182

天津市教委科研计划项目 2022KJ080

详细信息
    通讯作者:

    张宝成(1979—),博士,副教授. 研究方向:空中交通系统优化与管理. E-mail: bczhang@cauc.edu.cn

  • 中图分类号: U8

A Review of Studies on Large-scale Aircraft Scheduling Problems

  • 摘要: 飞机排班是航班计划的关键环节,直接影响民航运输的安全和经济效益。随着中国机队规模的稳步扩张,大规模飞机排班问题的研究愈发迫切;然而,早期基于连接网络或时空网络的机型指派模型及侧重运营收益、维修需求或鲁棒性的飞机排班问题模型,在问题规模、约束条件数量等方面往往受限,不能满足大规模飞机排班需求。本文在分析各类排班问题关联性和局限性的基础上,归纳了大规模一体化飞机排班问题的模型及其求解算法,分析了各算法的适用范围、优势和不足,并发现:分阶段排班模型无法保证全局最优解,一体化飞机排班模型更具有实际意义;精确算法理论上可保证求得最优解,但运算复杂、耗时长、模型分解难度大;启发式算法计算速度快,步骤简单,但无法保证求解的质量和算法的稳定性。在此基础上,进一步提出了未来大规模一体化飞机排班问题的研究方向:①问题建模方面,可在优化航线网络结构的同时,综合考虑航线需求、时间均衡调度和个性化机组指派等因素,建立一体化飞机排班集成模型,以解决现有模型的局限性;②问题求解方面,可以将Benders分解和列生成算法相结合,将整个问题分解为相对简单的主问题和子问题的组合,减少求解难度;也可将精确算法和启发式算法相结合,在保证求解精度的前提下尽量减少运算耗时,提高求解效率。

     

  • 图  1  2013—2022年中国飞机数量

    Figure  1.  Number of aircraft in China from 2013 to 2022

    图  2  2013—2023年民航旅客运输量

    Figure  2.  Civil aviation passenger traffic from 2013 to 2023

    图  3  连接网络示意图

    Figure  3.  Diagram of the connection network

    图  4  时空网络示意图

    Figure  4.  Diagram of space-time network

    图  5  算法流程

    Figure  5.  Flow of the algorithm

    表  1  国外2013—2023年主要文献

    Table  1.   Main foreign literature in 2013—2023

    作者 年份 机队类型/种 飞机数量/架 航班数量/个 算法选择 电脑性能 求解耗时/min
    CPU(GHz) 内存(GB)
    Sherali等[32] 2013 8 118 592 Benders分解 Intel 2.99 2.5 618
    Liang等[17] 2013 8 110 1 700 潜水启发式算法 Intel i7 M 2.80 8 240
    Shao等[23] 2017 5 192 676 Benders分解 Intel Xeon 2.4 24 594.8
    Vahid等[27] 2019 3 94 1 854 Benders分解 & 列生成 Intel Core i7 3.4 8 155.3
    Yan等[30] 2022 7 186 815 子网络分解 Microsoft Azure 64 111.8
    Şafak等[9] 2017 6 119 400 二阶锥规划内点算法 Intel Xeon E5 2.67 8 55.4
    Khanmirza等[31] 2020 3 753 9 697 主从并行遗传算法 Intel Core i7 3.4 16 216
    Unal等[33] 2021 24 170 1 290 XPressMP求解器 16core i-7 128 1 650
    Xu等[34] 2021 3 51 1 607 变邻域搜索算法 Intel i7 U 2.5 8 56.4
    Wei等[35] 2020 4 59 1 766 分支定价法 未给出 128 未给出
    Ahmed等[21] 2022 5 192 676 邻近搜索算法 Intel Core i7 3.2 16 233.2
    Shabanpour等[36] 2023 3 18 347 GAMS求解器 未给出 16 1.5
    Glomb等[37] 2023 4 23 300 Benders分解 Intel Xeon E3 3.7 32 59.9
    下载: 导出CSV

    表  2  国内2013—2023年主要文献

    Table  2.   Main domestic literature in 2013—2023

    作者 年份 机队类型/种 飞机数量/架 航班数量/个 算法选择 电脑性能 求解耗时/min
    GPU(GHz) 内存(GB)
    崔如玉[20] 2018 1 8 354 变邻域搜索算法 Intel i5 1.7 8 6.5
    李耀华等[38] 2017 2 15 154 遗传算法 未给出 未给出 未给出
    王磊[39] 2016 3 30 61 遗传算法 未给出 未给出 未给出
    朱星辉等[19] 2015 5 48 252 列生成&分支定界法 PM4 2.93 2 未给出
    张春晓等[40] 2015 6 20 20 分支定界法 未给出 未给出 未给出
    刘婧[41] 2016 1 10 70 专家规则启发式算法 未给出 未给出 未给出
    张开华[42] 2018 1 11 44 BP神经网络 未给出 未给出 未给出
    范永俊等[43] 2017 1 12 68 分支定界法 2.99 10 0.1
    向杜兵[44] 2020 1 未给出 118 列生成算法 2.10 8 4.3
    张萌[45] 2021 未给出 220 900 改进遗传算法 AMD R5 8 未给出
    李鹏飞[46] 2023 3 未给出 43 BP神经网络 未给出 未给出 未给出
    下载: 导出CSV
  • [1] HORST S. Statista(2021)EBIT margin of airlines worldwide 2010-2021[EB/OL]. (2021-08)[2023-06-10]. https://www.statis-ta.com/statistics/225856/ebitmargin-of-commercial-airlines-worldwide/.
    [2] ABARA J. Applying integer linear programming to the fleet assignment problem[J]. Interfaces, 1989, 19(4): 20-28. doi: 10.1287/inte.19.4.20
    [3] BERGE M E, HOPPERSTAD C A. Demand driven dispatch: a method for dynamic aircraft capacity assignment, models and algorithms[J]. Operations Research, 1993, 41(1): 153-168. doi: 10.1287/opre.41.1.153
    [4] HANE C A, BARNHART C, JOHNSON E L, et al. The fleet assignment problem: solving a large-scale integer program[J]. Mathematical Programming, 1995, 70(1): 211-232.
    [5] KNIKER T. Itinerary-based airline fleet assignment[D]. Cambridge: Massachusetts Institute of Technology, 1998.
    [6] BARNHART C, KNIKER T S, LOHATEPANONT M. Itinerary-based airline fleet assignment[J]. Transportation Science, 2002, 36(2): 199-217. doi: 10.1287/trsc.36.2.199.566
    [7] 朱星辉, 朱金福, 巩在武. 中国航空公司机型指派模型及算法研究[J]. 工业技术经济, 2007, 26(4): 3-7. https://www.cnki.com.cn/Article/CJFDTOTAL-GHZJ200704021.htm

    ZHU X H, ZHU J F, GONG Z W. Research on aircraft type assignment model and algorithm of China's airlines[J]. Journal of Industrial Technological Economics, 2007, 26(4): 3-7. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GHZJ200704021.htm
    [8] 乐美龙, 黄文秀. 基于时空网络的航班机型分配问题研究[J]. 交通运输系统工程与信息, 2014, 14(1): 81-87. doi: 10.3969/j.issn.1009-6744.2014.01.014

    LE M L, HUANG W X. Airline fleet assignment model based on time-space network[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(1): 81-87. (in Chinese) doi: 10.3969/j.issn.1009-6744.2014.01.014
    [9] ŞAFAK Ö, GUREL S, AKTURK M S. Integrated aircraft-path assignment and robust schedule design with cruise speed control[J]. Computers & Operations Research, 2017, 84: 127-145.
    [10] LIU M, DING Y, SUN L, et al. Green airline-fleet assignment with uncertain passenger demand and fuel price[J]. Sustainability, 2023, 15(2): 020899.
    [11] CLARKE L W, HANE C A, JOHNSON E L, et al. Maintenance and crew considerations in fleet assignment[J]. Transportation Science, 1996, 30(3): 249-260. doi: 10.1287/trsc.30.3.249
    [12] BARNHART C, KNIKER T S, LOHATEPANONT M. Itinerary-based airline fleet assignment[J]. Transportation Science, 2002, 36(2): 199-217. doi: 10.1287/trsc.36.2.199.566
    [13] BELANGER N, DESAULNIERS G, SOUMIS F, et al. Weekly airline fleet assignment with homogeneity[J]. Transportation Research Part B: Methodological, 2006, 40(4): 306-318. doi: 10.1016/j.trb.2005.03.004
    [14] 肖东喜, 朱金福. 飞机排班中航班环的动态构建方法[J]. 系统工程, 2007, 25(11): 19-25. https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200711005.htm

    XIAO D X, ZHU J F. Research on flight-loop's dynamic construction method in aircraft routing problem[J]. Systems Engineering, 2007, 25(11): 19-25. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200711005.htm
    [15] TANG C H, YAN S, CHEN Y H, An integrated model and solution algorithms for passenger, cargo, and combi flight scheduling[J]. Transportation Research Part E: Logistics and Transportation Review, 2008, 44(6): 1004-1024. doi: 10.1016/j.tre.2008.02.002
    [16] 魏星. 飞机排班一体化优化模型与算法研究[D]. 南京: 南京航空航天大学, 2012.

    WEI X. Research of integrated aircraft scheduling optimization model and algorithm[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2012. (in Chinese)
    [17] LIANG Z, CHAOVALITWONGSE W A. A network-based model for the integrated weekly aircraft maintenance routing and fleet assignment problem[J]. Transportation Science, 2013, 47(4): 493-507. doi: 10.1287/trsc.1120.0434
    [18] 朱星辉, 朱金福, 高强. 基于航班纯度的鲁棒性机型指派问题研究[J]. 预测, 2011, 30(1): 71-74. https://www.cnki.com.cn/Article/CJFDTOTAL-YUCE201101013.htm

    ZHU X H, ZHU J F, GAO Q. The research on robust fleet assignment problem based on flight purity[J]. Forecasting, 2011, 30(1): 71-74. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YUCE201101013.htm
    [19] 朱星辉, 吴薇薇, 戚彦龙. 基于延误传播的飞机排班一体化鲁棒优化模型[J]. 西南交通大学学报, 2015, 50(2): 375-381. doi: 10.3969/j.issn.0258-2724.2015.02.026

    ZHU X H, WU W W, QI Y L. Robust optimization model for integrated aircraft scheduling based on delay propagation[J]. Journal of Southwest JiaoTong University, 2015, 50(2): 375-381. (in Chinese) doi: 10.3969/j.issn.0258-2724.2015.02.026
    [20] 崔如玉. 飞机排班问题模型及算法研究[D]. 北京: 北京交通大学, 2018.

    CUI R Y. Research on models of aircraft scheduling problem and its algorithmic[D]. Beijing: Beijing Jiaotong University, 2018. (in Chinese)
    [21] AHMED M B, HRYHORYEVA M, HVATTUM L M, et al. A matheuristic for the robust integrated airline fleet assignment, aircraft routing, and crew pairing problem[J]. Computers & Operations Research, 2022, 137: 105551.
    [22] CORDEAU J F, SOUMIS F, DESROSIERS J. A Benders decomposition approach for the locomotive and car assignment problem[J]. Transportation Science, 2000, 34(2): 133-149. doi: 10.1287/trsc.34.2.133.12308
    [23] SHAO S, SHERALI H D, HAOUARI M. A novel model and decomposition approach for the integrated airline fleet assignment, aircraft routing, and crew pairing problem[J]. Transportation Science, 2017, 51(1): 233-249. doi: 10.1287/trsc.2015.0623
    [24] IOACHIM I, DESROSIERS J, SOUMIS F, et al. Fleet assignment and routing with schedule synchronization constraints[J]. European Journal of Operational Research, 1999, 119(1): 75-90. doi: 10.1016/S0377-2217(98)00343-9
    [25] 高强, 朱星辉, 李云, 等. 飞机排班一体化模型与算法研究[J]. 武汉理工大学学报(交通科学与工程版), 2012, 36(1): 153-157. https://www.cnki.com.cn/Article/CJFDTOTAL-JTKJ201201037.htm

    GAO Q, ZHU X H, LI Y, et al. Research on aircraft scheduling integration model and algorithm[J]. Journal of Wuhan University of Technology(Transportation Science & Engineering), 2012, 36(1): 153-157. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JTKJ201201037.htm
    [26] 徐进. 航空公司航班计划的优化方法研究[D]. 南京: 南京航空航天大学, 2015.

    XU J. Research on airline schedule design and optimization[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2015. (in Chinese)
    [27] ZEIGHAMI V, SOUMIS F. Combining Benders' decomposition and column generation for integrated crew pairing and personalized crew assignment problems[J]. Transportation Science, 2019, 53(5): 1479-1499. doi: 10.1287/trsc.2019.0892
    [28] 王铖恺, 范晓宇, 徐捷, 等. 结合Benders分解和列生成的发热门诊排班数学建模和优化算法[J]. 系统管理学报, 2023, 32(3): 476-487. https://www.cnki.com.cn/Article/CJFDTOTAL-XTGL202303004.htm

    WANG C K, FAN X Y, XU J, et al. Mathematical modeling and optimization algorithm for fever clinics Scheduling combining benders decomposition and column generation[J]. Journal of Systems & Management, 2023, 32(3): 476-487. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTGL202303004.htm
    [29] KENAN N, JEBALI A, DIABAT A. An integrated flight scheduling and fleet assignment problem under uncertainty[J]. Computers & Operations Research, 2018, 100: 333-342. doi: 10.3969/j.issn.1001-3695.2018.02.003
    [30] YAN C, BARNHART C, VAZE V. Choice-based airline schedule design and fleet assignment: a decomposition approach[J]. Transportation Science, 2022, 56(6): 1410-1431. doi: 10.1287/trsc.2022.1141
    [31] KHANMIRZA E, NAZARAHARI M, HAGHBEIGI M. A heuristic approach for optimal integrated airline schedule design and fleet assignment with demand recapture[J]. Applied Soft Computing, 2020, 96: 106681.
    [32] SHERALI H D, BAE K H, HAOUARI M. An integrated approach for airline flight selection and timing, fleet assignment, and aircraft routing[J]. Transportation Science, 2013, 47(4): 455-476.
    [33] UNAL Y Z, SEVKLI M, UYSAL O, et al. A new approach to fleet assignment and aircraft routing problems[J]. Transportation Research Procedia, 2021, 59: 67-75.
    [34] XU Y, WANDELT S, SUN X. Airline integrated robust scheduling with a variable neighborhood search based heuristic[J]. Transportation Research Part B: Methodological, 2021, 149: 181-203.
    [35] WEI K, VAZE V, JACQUILLAT A. Airline timetable development and fleet assignment incorporating passenger choice[J]. Transportation Science, 2020, 54(1): 139-163.
    [36] SHABANPOUR A, BASHIRI M, TAVAKKOLI-MOGHADDAM R, et al. Integrated linear integer model of a fleet allocation and aircraft routing problem with operational constraints[J]. International Journal of Engineering, 2023, 36 (4): 669-681.
    [37] GLOMB L, LIERS F, RÖSEL F. Optimizing integrated aircraft assignment and turnaround handling[J]. European Journal of Operational Research, 2023, 310(3): 1051-1071.
    [38] 李耀华, 谭娜. 基于遗传算法的飞机一体化排班优化方法[J]. 控制工程, 2017, 24(2): 435-440. https://www.cnki.com.cn/Article/CJFDTOTAL-JZDF201702035.htm

    LI Y H, TAN N. Optimization method of aircraft integrated planning based on genetic algorithm[J]. Control Engineering of China, 2017, 24(2): 435-440. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JZDF201702035.htm
    [39] 王磊. 基于遗传算法的飞机排班优化方法研究[D]. 天津: 中国民航大学, 2016.

    WANG L. Study on aircraft scheduling optimization based on genetic algorithm[D]. Tianjin: Civil Aviation University of China, 2016. (in Chinese)
    [40] 张春晓, 石晓磊, 臧其银. 不确定需求下的两阶段机型指派模型[J]. 中国民航大学学报, 2015, 33(4): 10-15. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGMH201504003.htm

    ZHANG C X, SHI X L, ZANG Q Y. Two-stage fleet assignment model with uncertain demand[J]. Journal Of Civil Aviation University Of China, 2015, 33(4): 10-15. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGMH201504003.htm
    [41] 刘婧, 贾宝惠. 基于启发式算法的飞机指派优化模型及算法[J]. 系统仿真技术, 2016, 12(2): 79-82, 94. https://www.cnki.com.cn/Article/CJFDTOTAL-XTFJ201602001.htm

    LIU J, JIA B H. Study on optimization model and algorithm of flight assignment based on heuristic algorithm[J]. System Simulation Technology, 2016, 12(2): 79-82, 94. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTFJ201602001.htm
    [42] 张开华. 需求驱动下机型指派问题研究[D]. 南京: 南京航空航天大学, 2018.

    ZHANG K H. Research on demand driven fleet assignment[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2018. (in Chinese)
    [43] 范永俊, 吴东华. 基于分支定界法的飞机均衡排班计划求解[J]. 统计与决策, 2017, 10(20): 60-63. https://www.cnki.com.cn/Article/CJFDTOTAL-TJJC201720015.htm

    FAN Y J, WU D H. Aircraft balanced scheduling plan solution based on branch-and-bound approach[J]. Statistics & Decision, 2017, 10(20): 60-63. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-TJJC201720015.htm
    [44] 向杜兵. 航空机组排班计划一体化优化研究[D]. 北京: 北京交通大学, 2021.

    XIANG D B. Research on integrated optimization of airline crew scheduling[D]. Beijing: Beijing Jiaotong University, 2021. (in Chinese)
    [45] 张萌. 基于遗传算法的飞机排班调度方法研究[D]. 大连: 大连海事大学, 2021.

    ZHANG M. Research on aircraft scheduling method based on genetic algorithm[D]. Dalian: Dalian Maritime University, 2021. (in Chinese)
    [46] 李鹏飞. 基于航班延误的飞机排班优化[D]. 广汉: 中国民用航空飞行学院, 2023.

    LI P F. Flight scheduling optimization based on flight delay[D]. Guanghan: Civil Aviation Flight University of China, 2023. (in Chinese)
    [47] 袁雪丽, 杨菊花, 任金荟. 随机运输时间下集装箱海铁联运箱流径路优化方法[J]. 交通信息与安全, 2022, 40(6): 106-117. doi: 10.3963/j.jssn.1674-4861.2022.06.011

    YUAN X L, YANG J H, REN J H. A path optimization method for sea-rail intermodal container transport under random transit time[J]. Journal of Transport Information and Safety, 2022, 40(6): 106-117. doi: 10.3963/j.jssn.1674-4861.2022.06.011
  • 加载中
图(5) / 表(2)
计量
  • 文章访问数:  335
  • HTML全文浏览量:  156
  • PDF下载量:  140
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-06-21
  • 网络出版日期:  2024-05-31

目录

    /

    返回文章
    返回