Most airline companies use a sequential procedure in their complex operations planning process, which includes schedule planning, fleet assignment, aircraft routing, and crew scheduling. Each problem is modeled and solved independently. This procedure reduces considerably the complexity of the process, but since the solution of one problem does not take into account the affect sub- sequent problems. It results in overall suboptimal solutions that may be far from optimality. Moreover, finding feasible solutions may become difficult or impossible because flexibility is reduced by previously made decisions. Proceeding from the reality of airlines, a multi-type aircraft scheduling model is build and proposed 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 calculated the reduced cost of each strings, selected column sets dynamically and iterate with the restriction master problem. Finally, actual data of a domestic airline' s trunk flight network are tested to indicate the effectiveness of the model and algorithm, and the results show integrated model is further optimization than practical operation and sequential procedure.%通常航班计划都是分阶段完成的,即航班时刻表→机型指派→飞机排班→机组排班,每一个问题都相对独立的建模并求解.通常无法得到全局最优解甚或无解,对后续问题求解造成很大困难.为了克服这种困难及改善航班计划的次优性,将机型指派、飞机路线问题综合考虑,建立多机型的一体化飞机排班多商品网络流模型.为实现模型的有效求解,提出了基于约束编程的动态列生成算法；即用约束编程快速求解航班连线(航班串)并计算各航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性,并与航空公司实际排班和分阶段优化情况进行比较研究.
展开▼
