基于改进列生成算法的非正常航班恢复研究  

Research on Irregular Flight Recovery Based on Improved Column Generation Algorithm

作　　者：罗凤娥[1] 张鑫 谢玲娟 LUO Feng-e;ZHANG Xin;XIE Ling-juan(Civil Aviation Flight University of China,Guanghan 618000,China;Zibo Century Talents Foreign Languages School,Zibo 255000,China)

机构地区：[1]中国民用航空飞行学院,四川广汉618000 [2]淄博世纪英才外语学校,山东淄博255000

出　　处：《航空计算技术》2024年第6期22-26,共5页Aeronautical Computing Technique

基　　金：民航局教育类项目面向共建“一带一路”国家民航专业本科教育项目资助(MHJY2023021)。

摘　　要：当对非正常航班实施运行管理时,航空公司需要实时重新安排航班和分配飞机,且采取各种恢复措施来制定航班恢复计划。为了尽可能降低恢复成本,根据非正常航班恢复问题的特征,建立了恢复措施成本最小的整数规划模型,提出了一个基于列生成算法框架的启发式算法来解决航班恢复问题。在主问题中,明确考虑了机型平衡约束和维修约束;在子问题中,应用了标号更正法对列生成算法进行改进。根据航空公司的算例研究表明,主问题给出了一个非常紧密的线性松弛,验证了模型和改进的列生成算法的有效性及求解效率。When implementing operational management for irregular flights,airlines need to reschedule flights and allocate aircraft in real time,and take various recovery measures to develop flight recovery plans.In order to reduce the recovery cost as much as possible,based on the characteristics of the abnormal flight recovery problem,an integer planning model is established to minimise the cost of recovery measures,and a heuristic algorithm based on the framework of column generation algorithm is proposed to solve the flight recovery problem.In the master problem,model balance constraints and maintenance constraints are explicitly considered;in the subproblems,the marking correction method is applied and the evaluation process of model exchange is incorporated.Based on an airline case study,the master problem gives a very tight linear relaxation,which validates the effectiveness and efficiency of the model and the improved column generation algorithm.

关 键 词：非正常航班 飞机恢复问题 列生成算法 机型交换 标号更正法 

分 类 号：V35[航空宇航科学与技术—人机与环境工程]