基于航班环的机组排班优化

赵晋芳; 赵乔洋; 周松; 殷奥博

doi:10.3969/j.issn.2095-1248.2023.04.006

沈阳航空航天大学学报 ›› 2023, Vol. 40 ›› Issue (4) : 40 -48. DOI: 10.3969/j.issn.2095-1248.2023.04.006

民用航空与安全工程

基于航班环的机组排班优化

赵晋芳 ^a ,
赵乔洋 ^a ,
周松 ^b ,
殷奥博 ^a

作者信息 +

Crew scheduling optimization based on flight loop

Author information +

文章历史 +

PDF (745K)

摘要

机组排班计划是航空公司运营管理计划的重要组成部分，因其NP-hard特性常面临组合爆炸而难以求解。针对这一问题，提出一种基于航班环的优化模型。在第一阶段考虑执勤时空衔接约束与执勤始发终到约束，构建了航班间的航班环模型；在第二阶段设计了结合改进的深度优先搜索算法（depth-first search，DFS）以及贪心算法完成对模型的求解。此外，提出了列生成算法下受限主问题模型（restricted master problem model，RMP），并运用该模型完成实验验证算例的求解。

Abstract

Crew scheduling is an important part of the operation management plan of an airline. Due to its NP-hard， it often faces combinational explosion and is difficult to be solved. Addressing the problem， a flight-loop-based optimization model was proposed. In phase one， considering the space-time connection constraint and the departure and arrival constraint for duty， a flight loop model between route segments was built； in phase two， the depth-first search （DFS） algorithm and greedy algorithm were incorporated to accomplish the solution of the model. In addition， a restricted master problem （RMP） model was proposed under the column generation algorithm， which was then used to solve the experimental validation examples.