基于动态列生成算法的飞机排班问题研究  

Aircraft Scheduling Problem Based on Dynamic Column Generation Algorithms

作　　者：朱星辉[1] 朱金福[1] 高强[1] 

机构地区：[1]南京航空航天大学民航学院,江苏南京210016

出　　处：《数学的实践与认识》2014年第19期23-30,共8页Mathematics in Practice and Theory

基　　金：国家自然科学基金联合基金(61079014);中国民用航空局科技项目(MHRD20100842);中央高校基本科研业务费资助项目(NS2014071)

摘　　要：飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.Aircraft scheduling is an important element in air transport planning and has a crucial impact on the regular operation and overall effectiveness of Airlines. Aircraft scheduling problem is also an important issue in airline operation research and it is usually built as a large-scale integer programming problem. The model is a serious degradation NP-hard problem. The complexity of the problem is increasing greatly when considering the multi-type of aircrafts. Proceeding from the reality of airlines, this paper builds a multi- type aircraft scheduling model and proposes a dynamic column generation algorithm based on constraint programming to solve the problem effectively, that is, to fast generate flight strings by constraint programming and calculate the reduced cost of each strings, select column sets dynamically and iterate with the restriction master problem. Finally, actual data of a domestic airline＇s trunk flight network were tested to indicate the effectiveness of the model and algorithm.

关 键 词：飞机排班 动态列生成算法 约束编程 组合优化 

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