摘要
飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响.飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.本文把飞机排班问题构建为多商品网络流模型,并应用列生成算法求解;在列生成子问题中,引入约束编程系统实现快速求解航班连线(航班串)并计算各航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性,并与航空公司实际排班进行比较研究.
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 effectively solve the problem. It fast generates flight strings by constraint programming and calculates the reduced cost of each strings, dynamically selects column sets and iterates with the restriction master problem. Finally, field data from one airline＇ s trunk flight network in China are used to test and verify the effectiveness of the model and algorithm, and the results show that the integrated model is more optimized than practical operation.
出处
《交通运输系统工程与信息》
EI
CSCD
2011年第6期151-156,共6页
Journal of Transportation Systems Engineering and Information Technology
基金
国家自然科学基金联合基金(61079014)
中国民用航空局科技项目(MHRD20100842)
关键词
航空运输
动态列生成算法
约束编程
飞机排班
航班串
air transportation
dynamic column generation algorithm
constraint programming
aircraft scheduling
flight string
