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

交通运输系统工程与信息 ›› 2011, Vol. 11 ›› Issue (6): 151-156.

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

朱星辉*，朱金福，高强

南京航空航天大学民航学院, 南京 210016

收稿日期:2011-08-16 修回日期:2011-10-19 出版日期:2011-12-25 发布日期:2012-01-04
作者简介:朱星辉（1978- ），男，江西九江人，讲师，硕士生导师.
基金资助:
国家自然科学基金联合基金（61079014）; 中国民用航空局科技项目（MHRD20100842）.

Aircraft Scheduling Based on Constraint Programming

ZHU Xing-hui, ZHU Jin-fu, GAO Qiang

College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Received:2011-08-16 Revised:2011-10-19 Online:2011-12-25 Published:2012-01-04

摘要/Abstract

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

关键词: 航空运输, 动态列生成算法, 约束编程, 飞机排班, 航班串

Abstract: 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.

Key words: air transportation, dynamic column generation algorithm, constraint programming, aircraft scheduling, flight string

中图分类号:

F560

朱星辉, 朱金福, 高强. 基于约束编程的飞机排班问题研究[J]. 交通运输系统工程与信息, 2011, 11(6): 151-156.

ZHU Xing-Hui, ZHU Jin-Fu, GAO Qiang. Aircraft Scheduling Based on Constraint Programming[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(6): 151-156.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18303.shtml

http://www.tseit.org.cn/CN/Y2011/V11/I6/151

参考文献

[1] L W Clarke, E L Johnson, G L Nemhauser, et al. The aircraft rotation problem[J]. Annals of Operations Research, 1997, 69(1): 33-46.
[2] C Barnhart, N L Boland, L W Clarke, et al. Flight string models for aircraft fleeting and routing[J]. Transportation Science, 1998, 32(3):208-220.
[3] I Ioachim, J Desrosiers, F Soumis, et al. Fleet assignment and routing with schedule synchronization constraints[J]. European Journal of Operational Research,1999, 119(1): 20-26.
[4] J F Cordeau, G Stojkovi′c, F Soumis, et al. Benders decomposition for simultaneous aircraft routing and crew scheduling [J]. Transportation Science, 2001,35(4): 375-388.
[5] A Mercier, J F Cordeau, F Soumis. A computational study of benders decomposition for the integrated aircraft routing and crew scheduling problem[J]. Computers & Operation Research, 2005, 32(1): 1451-1476.
[6] A Mercier, F Soumis. An integrated aircraft routing, crew scheduling and flight retiming model[J]. Computers & Operations Research , 2007, 34(1): 2251-2265.
[7] G Mattias. The tail assignment problem[D].Goteborg: Department of Computer Science and Engineering, Chalmers University of Technology and Goteborg University, 2005.
[8] G Mattias. Accelerating column generation for aircraft scheduling using constraint propagation[J]. Computers & Operations Research. 2006,33 (1): 2918-2934.
[9] N Papadakos. Integrated airline scheduling[J].Computers & Operations Research.2009,36 (1): 176-195. 
[10] 孙宏．航空公司飞机排班问题：模型及算法研究[D]．成都：西南交通大学，2003．［SUN H．Airline tail number assignment problem:mode and algorithm[D]．Chengdu:Southwest Jiaotong University,2003.］
[11] Zhu X H, Zhu J F, Gong Z W. Weekly fleet assignment model and algorithms[J]. Journal of southwest jiaotong university(English Edition), 2007, 15(3): 231-235． 
[12 ] 肖东喜，朱金福，飞机排班中航班环的动态构建方法[J]．系统工程, 2007, 25(11): 19-25．［XIAO D X, ZHU J F. Fl ightloop’s dynamic construction method in aircraft scheduling [J]．Systems Engineering, 2007, 25(11): 19-25．］
[13] 李耀华，秦如如．基于混合遗传算法的航班串优化模型研究[J]．中国民航大学学报, 2010, 28(6): 31-34.[LI Y H，QIN R R．Study on flight string model based on mixed genetic algorithm [J]．Journal of clvil aviation university of China, 2010, 28(6): 31-34.]
[14] Lustig I J, Puget J F. Program does not equal program: constraint programming and its relationship to mathematical programming [J]. Interfaces, NovemberDecember 2001, 31(6): 29-53. 
[15] ILOG Inc.ILOG SOLVER 6.5 User’s Manual 2003.
[16] ILOG Inc.ILOG SCHEDULER 6.0 User’s Manual 2003.
[17] ILOG Inc. ILOG CPLEX 9.0 User’s Manual 2003.

[1]	张培文, 杜福民, 汪瑜. 基于链路预测的中小机场连接机制研究[J]. 交通运输系统工程与信息, 2022, 22(2): 298-304.
[2]	王红勇, 郭宇鹏. 基于航空器自主运行的空中交通复杂性建模[J]. 交通运输系统工程与信息, 2022, 22(2): 305-312.
[3]	张洪海, 张连东, 刘皞, 钟罡. 城市低空物流无人机航迹规划模型研究[J]. 交通运输系统工程与信息, 2022, 22(1): 256-264.
[4]	张魏宁, 胡明华, 杜婧涵, 尹嘉男. 基于条件生成对抗网络的扇区复杂度评估[J]. 交通运输系统工程与信息, 2021, 21(6): 226-233.
[5]	胡荣, 王德芸, 冯慧琳, 刘志昊, 张军峰. 碳达峰视角下的机场航空器碳排放预测[J]. 交通运输系统工程与信息, 2021, 21(6): 257-263.
[6]	李杰, 杨好天, 王兵, 周晓宁, 孙若飞. 民航飞机起飞推力对油耗和排放的影响分析[J]. 交通运输系统工程与信息, 2021, 21(6): 283-288.
[7]	胡荣, 冯慧琳, 刘博文, 张军峰, 王德芸. 点汇聚系统的航空器污染物减排效应与机理[J]. 交通运输系统工程与信息, 2021, 21(5): 165-173.
[8]	曹炜威，李政，冯项楠. 2000—2018年全国民航网络结构特征及演化[J]. 交通运输系统工程与信息, 2021, 21(3): 26-33.
[9]	魏保立，郭成超，邓苗毅. 基于数据驱动的机场水泥混凝土道面性能退化预测[J]. 交通运输系统工程与信息, 2021, 21(3): 247-253.
[10]	姜雨，童楚，刘振宇，胡志韬，徐成，张洪海. 基于时间富余度控制的滑行道调度优化模型[J]. 交通运输系统工程与信息, 2021, 21(1): 207-213.
[11]	张洪海，李翰，刘皞，许卫卫，邹依原. 城市区域物流无人机路径规划[J]. 交通运输系统工程与信息, 2020, 20(6): 22-29.
[12]	盛寅，陈欣，毛亿. 不确定条件下机场群系统均衡配流模型研究[J]. 交通运输系统工程与信息, 2020, 20(6): 212-218.
[13]	郭野晨风，胡明华，张颖，谢华. 改进的协同航路分配优化模型及算法研究[J]. 交通运输系统工程与信息, 2020, 20(6): 226-232.
[14]	姜雨，胡志韬，童楚，刘振宇，陈丽丽，张洪海. 面向航班延误的停机位实时指派优化模型[J]. 交通运输系统工程与信息, 2020, 20(5): 185-190.
[15]	强生杰，黄青霞. 新型客机座舱环境下的旅客登机效率研究[J]. 交通运输系统工程与信息, 2020, 20(4): 209-215.