基于协同多任务分配的飞机排班模型与算法

电子与自动控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

基于协同多任务分配的飞机排班模型与算法

周琨, 夏洪山

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

收稿日期:2011-05-16 修回日期:2011-06-14 出版日期:2011-12-25 发布日期:2011-12-08
通讯作者: 夏洪山 E-mail:xhsca@nuaa.edu.cn
作者简介:周琨(1984-) 男,博士研究生。主要研究方向:智能运输系统建模、仿真与优化。 E-mail: nuaacaazhou@126.com
夏洪山(1952-) 男,教授,博士生导师。主要研究方向:航空运输系统智能化。 Tel: 025-84891165 E-mail: xhsca@nuaa.edu.cn
基金资助:
国家软科学研究计划(2008GXQ6B141)

Optimization Model and Algorithm for Aircraft Scheduling Problem Based on Cooperative Multi-task Assignment

ZHOU Kun, XIA Hongshan

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

Received:2011-05-16 Revised:2011-06-14 Online:2011-12-25 Published:2011-12-08

摘要/Abstract

摘要：

航空公司的航班运行一直存在安全与成本的矛盾:既要严格按规定完成飞机例行检修,优先保障运行安全,又要尽可能提高飞机日利用率,以降低运行成本。为此,研究基于协同多任务分配的飞机排班问题。分析例行检修约束,建立最优化飞机日利用率的数学模型,运用分枝定价算法进行求解。分枝定价算法引入检修节点和虚拟飞机节点的定义,将分配的航班飞行任务和例行检修任务表示为飞机路径,通过迭代求解由部分飞机路径构成的限制主问题,以及寻找飞机路径以改进目标值的定价问题,获得线性松弛问题的最优解;基于最先失败原则选择路径变量,采用路径分枝策略划分解空间,从而删除分数解、生成飞机排班计划。实验结果表明,该方法能够有效求解飞机排班问题。

关键词: 空中交通管制, 排班, 多任务分配, 分枝定价算法, 列生成, 约束满足

Abstract:

The conflict between safety and cost is an outstanding problem during flight operation, i.e., aircraft must accomplish maintenance tasks to establish a safe environment, and then the utilization of aircraft should be improved to reduce operational cost. In view of this, the aircraft scheduling problem based on cooperative multi-task assignment is studied. The approach applies branch-and-price algorithm to the cost optimization model with maintenance constraints, and mathematical model of daily utilization ratio is established. According to definitions of maintenance point and virtual aircraft point, the algorithm formulates assigned flights and maintenance tasks as routes. After several iterations of solving a restricted master problem containing a subset of routes and a pricing problem generating new routes with negative reduced cost, an optimal solution to the linear programming relaxation problem is obtained. To obtain the integer solution, a dedicated branching scheme based on fail first principle is proposed, and the branching decision is imposed on route variables. Then the aircraft scheduling is formed. Simulation results show that the proposed approach can solve the aircraft scheduling problem effectively.

Key words: air traffic control, scheduling, multi-task assignment, branch-and-price algorithm, column generation, constraint satisfaction

中图分类号:

V355.2

周琨, 夏洪山. 基于协同多任务分配的飞机排班模型与算法[J]. 航空学报, 2011, 32(12): 2293.

ZHOU Kun, XIA Hongshan. Optimization Model and Algorithm for Aircraft Scheduling Problem Based on Cooperative Multi-task Assignment[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2011, 32(12): 2293.

参考文献

[1] Gopalan R, Talluri K T. The aircraft maintenance routing problem[J]. Operations Research, 1998, 46(2): 260-271.

[2] Talluri K T. The four-day aircraft maintenance routing problem[J]. Transportation Science, 1998, 32(1): 43-53.

[3] Clarke L, Johnson E, Nemhauser G, et al. The aircraft rotation problem[J]. Annals of Operations Research, 1997, 69(0): 33-46.

[4] Sriram C, Haghani A. An optimization model for aircraft maintenance scheduling and re-assignment[J]. Transportation Research Part A: Policy and Practice, 2003, 37(1): 29-48.

[5] 肖东喜, 朱金福. 飞机排班中航班环的动态构建方法[J]. 系统工程, 2007, 25(11): 19-25. Xiao Dongxi, Zhu Jinfu. Flight-loop's dynamic construction method in aircraft scheduling[J]. Systems Engineering, 2007, 25(11): 19-25. (in Chinese)

[6] Guay E L, Desaulniers G, Soumis F. Aircraft routing under different business process[J]. Journal of Air Transport Management, 2010, 16(5): 258-263.

[7] Grönkvist M. Accelerating column generation for aircraft scheduling using constraint propagation[J]. Computer & Operation Research, 2006, 33(10): 2918-2934.

[8] Grönkvist M. The tail assignment problem. Göteborg: Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, 2005.

[9] Gabteni S, Grönkvist M. Combining column generation and constraint programming to solve the tail assignment problem[J]. Annals of Operations Research, 2009, 171(1): 61-76.

[10] Grönkvist M. A constraint programming model for tail assigment//Régin J C, Rueher M, editors. Integration of AI and OR Techniques in Constraint Programming for Combinational Optimization Problems. Berlin: Springer-Verlag, 2004: 142-156.

[11] 孙宏. 航空公司飞机排班问题: 模型及算法研究. 成都: 西南交通大学交通运输学院, 2003. Sun Hong. Airline tail number assignment problem: model and algorithm. Chengdu: School of Traffic and Transportation, Southwest Jiaotong University, 2003. (in Chinese)

[12] Moudaini W E, Camino F M. A dynamic approach for aircraft assignment and maintenance scheduling by airlines[J]. Journal of Air Transport Management, 2000, 6(4): 233-237.

[13] Papakostas N, Papachatzakis P, Xanthakis V, et al. An approach to operational aircraft maintenance planning[J]. Decision Support Systems, 2010, 48(4): 604-612.

[14] Sarac A, Batta R, Rump C M. A branch-and-price approach for operational aircraft maintenance routing[J]. European Journal of Operational Research, 2006, 175(3): 1850-1869.

[15] Shi N. K constrained shortest path problem[J]. IEEE Transactions on Automation Science and Engineering, 2010, 7(1): 15-23.

[16] 郭冬芬, 李铁克. 基于约束满足的车间调度算法综述[J]. 计算机集成制造系统, 2007, 13(1): 117-125. Guo Dongfen, Li Tieke. Constraint-based algorithm for job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2007, 13(1): 117-125. (in Chinese)

[17] 孙吉贵, 朱兴军, 张永刚, 等. 最先失败原则的约束传播算法[J]. 小型微型计算机系统, 2008, 29(4): 678-681. Sun Jigui, Zhu Xingjun, Zhang Yonggang, et al. Fail first principle for constraint propagation[J]. Journal of Chinese Computer Systems, 2008, 29(4): 678-681. (in Chinese)

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

基于协同多任务分配的飞机排班模型与算法

Optimization Model and Algorithm for Aircraft Scheduling Problem Based on Cooperative Multi-task Assignment

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陶冶, 汤锦辉, 闫震, 周臣, 王冲. 融合表征转换与模式回归的航迹插补方法[J]. 航空学报, 2026, 47(1): 332106-332106.
[2]	周锦伦, 张洪海, 李雯清. 推进民航自主运行所需关键技术及其部署方案[J]. 航空学报, 2025, 46(22): 331998-331998.
[3]	王路桥, 王璐, 庄慧盈, 吴磊, 李青山, 田恒宇. 约束分级的飞行器任务指令序列编排方法[J]. 航空学报, 2024, 45(20): 630445-630445.
[4]	刘继新, 江灏, 董欣放, 兰思洁, 王浩哲. 基于空中交通密度的进场航班动态协同排序方法[J]. 航空学报, 2020, 41(7): 323717-323717.
[5]	卜建, 刘银鑫, 王艳军. 空中交通管制员的眼动行为与疲劳关系[J]. 航空学报, 2017, 38(S1): 721525-721525.
[6]	武喜萍, 杨红雨, 韩松臣. 基于复杂网络的空中交通特征与延误传播分析[J]. 航空学报, 2017, 38(S1): 721473-721473.
[7]	马园园, 胡明华, 张洪海, 尹嘉男, 吴凡. 多机场终端区进场航班协同排序方法[J]. 航空学报, 2015, 36(7): 2279-2290.
[8]	尹嘉男, 胡明华, 张洪海, 马园园, 吴凡. 独立离场模式下多跑道时空资源优化调度方法[J]. 航空学报, 2015, 36(5): 1574-1584.
[9]	尹嘉男, 胡明华, 张洪海, 马园园. 多跑道协同运行模式优化方法[J]. 航空学报, 2014, 35(3): 795-806.
[10]	尹嘉男, 胡明华, 彭瑛, 唐勇, 马园园. 相关进近模式下多跑道时空资源优化调度方法[J]. 航空学报, 2014, 35(11): 3064-3073.
[11]	王洪, 刘昌忠, 汪学刚, 吴宏刚. 一种多点定位的目标位置精确解算方法[J]. 航空学报, 2011, 32(7): 1269-1274.
[12]	刘方勤, 胡明华, 张颖. 基于航路耦合容量的协同多航路资源分配[J]. 航空学报, 2011, 32(4): 672-684.
[13]	白松浩, 兰洪亮, 郑娜, 夏正洪, 周臣. 基于贡献度模型方法对空中交通管制中心系统的效能评估[J]. 航空学报, 2011, 32(3): 438-447.
[14]	徐肖豪;赵鸿盛;王振宇. 尾流间隔缩减技术综述[J]. 航空学报, 2010, 31(4): 655-662.
[15]	李雄;徐肖豪;赵嶷飞;卫东选. 散点状分布危险天气区域下的航班改航路径规划[J]. 航空学报, 2009, 30(12): 2342-2347.