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

A Review of Studies on Large-scale Aircraft Scheduling Problems

作　　者：张宝成[1] 冉博文 ZHANG Baocheng;RAN Bowen(Air Traffic Management Institute,Civil Aviation University of China,Tianjin 300300,China)

机构地区：[1]中国民航大学空中交通管理学院,天津300300

出　　处：《交通信息与安全》2024年第1期1-10,27,共11页Journal of Transport Information and Safety

基　　金：国家自然科学基金项目(71571182);天津市教委科研计划项目(2022KJ080)资助。

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

关 键 词：航空运输 飞机排班 整数规划 机型指派 Benders分解 列生成算法 

分 类 号：U8[交通运输工程]