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

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.

Aircraft Scheduling Problem Based on Dynamic Column Generation Algorithms

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 multitype 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.