基于约束编程的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节，对航空公司的正常运营和整体效益有着决定性影响.飞机排班通常构建为大规模整数规划问题，是航空运筹学研究的重要课题，构建的模型属于严重退化的NP Hard问题.本文把飞机排班问题构建为多商品网络流模型，并应用列生成算法求解；在列生成子问题中，引入约束编程系统实现快速求解航班连线（航班串）并计算各航班串简约成本，动态选择列集并与限制主问题进行迭代.最后，利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性，并与航空公司实际排班进行比较研究.

Aircraft Scheduling Based on Constraint Programming

Aircraft scheduling is an important step in air transport planning and has a crucial impact on the regular operation and overall effectiveness of Airlines.Aircraft scheduling problem is usually described as a large-scale integer programming problem and is also an important part in airline operation research.The model is a serious degradation NP-hard problem.This paper develops a multi-type aircraft scheduling model and proposes a dynamic column generation algorithm based on constraint programming to effecti...