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

张宝成; 冉博文

doi:10.3963/j.jssn.1674-4861.2024.01.001

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

doi: 10.3963/j.jssn.1674-4861.2024.01.001

张宝成^,,
冉博文

中国民航大学空中交通管理学院天津 300300

基金项目:

国家自然科学基金项目 71571182

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

详细信息

通讯作者:
张宝成（1979—），博士，副教授. 研究方向：空中交通系统优化与管理. E-mail: bczhang@cauc.edu.cn

中图分类号: U8
计量
- 文章访问数: 419
- HTML全文浏览量: 221
- PDF下载量: 144
- 被引次数: 0
出版历程
- 收稿日期: 2023-06-21
- 网络出版日期: 2024-05-31

A Review of Studies on Large-scale Aircraft Scheduling Problems

ZHANG Baocheng^,,
RAN Bowen

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

摘要

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

HTML全文

图 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）	求解耗时/min
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）	求解耗时/min
崔如玉^[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

参考文献(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