Volume 42 Issue 1
Feb.  2024
Turn off MathJax
Article Contents
Article Navigation >  Journal of Transport Information and Safety  > 2024  >  42(1): 1-10
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
shu

A Review of Studies on Large-scale Aircraft Scheduling Problems

doi: 10.3963/j.jssn.1674-4861.2024.01.001

  • Air Traffic Management Institute, Civil Aviation University of China, Tianjin 300300, China

  • Received Date: 2023-06-21
    Available Online: 2024-05-31
    Abstract
  • Aircraft scheduling is a key link in flight planning, directly affecting the safety and economic efficiency of civil aviation transport. With the expansion of the aircraft fleet in China, research on large-scale aircraft scheduling problems (ASP) has become urgent. However, the fleet assignment model and aircraft scheduling models (ASMs) with different decision-making objectives (e.g., operational profitability, maintenance requirements, and robustness) cannot meet the needs since the number of constraints and the scale of the problem are often limited. By analyzing the connections and limitations of the existing ASMs, this paper summarizes the model and its solution algorithms for large-scale integrated ASP, analyzes the scope of application, advantages and disadvantages of each algorithm, and finds that: the phased scheduling model cannot guarantee the global optimal solution, while the integrated aircraft scheduling model is more practical; the exact algorithm can theoretically guarantee the optimal solution, but it is complicated, time-consuming, and difficult to decompose; the heuristic algorithm is fast and simple, but quality of the solution and the stability of the algorithm cannot guaranteed. Lastly, further research directions for large-scale integrated ASP are concluded: ① In terms of problem modelling, an integrated scheduling model can be established to optimize the route network structure and overcome the limitations of the existing models by taking into account factors such as route demand, time-balanced scheduling, and personalized crew assignments; ② In terms of problem-solving, Benders decomposition and column generation algorithms can be combined to decompose the whole problem into relatively simple main problems and sub-problems, reducing the difficulty of solving; additionally, the exact algorithms and heuristic algorithms can be combined to reduce the computational time and guarantee the accuracy of the solution, improving the solution efficiency.

     

    • FullText(HTML)
  • loading
    • References(47)
  • [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
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(5)  / Tables(2)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (412) PDF downloads(142) Cited by()
    Proportional views
    Related

    Copyright Editorial Office of Transport Information and Safety鄂ICP备05003336号-2

    Address：No. 1178，Heping Avenue, Wuchang, Wuhan, CHINA (430063)

    Tel：027-86580355 Email：jtjsj@vip.163.com

    Supported by: Beijing Renhe Information Technology Co. Ltd  

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return