基于协同多任务分配的飞机排班模型与算法
收稿日期: 2011-05-16
修回日期: 2011-06-14
网络出版日期: 2011-12-08
基金资助
国家软科学研究计划(2008GXQ6B141)
Optimization Model and Algorithm for Aircraft Scheduling Problem Based on Cooperative Multi-task Assignment
Received date: 2011-05-16
Revised date: 2011-06-14
Online published: 2011-12-08
航空公司的航班运行一直存在安全与成本的矛盾:既要严格按规定完成飞机例行检修,优先保障运行安全,又要尽可能提高飞机日利用率,以降低运行成本。为此,研究基于协同多任务分配的飞机排班问题。分析例行检修约束,建立最优化飞机日利用率的数学模型,运用分枝定价算法进行求解。分枝定价算法引入检修节点和虚拟飞机节点的定义,将分配的航班飞行任务和例行检修任务表示为飞机路径,通过迭代求解由部分飞机路径构成的限制主问题,以及寻找飞机路径以改进目标值的定价问题,获得线性松弛问题的最优解;基于最先失败原则选择路径变量,采用路径分枝策略划分解空间,从而删除分数解、生成飞机排班计划。实验结果表明,该方法能够有效求解飞机排班问题。
周琨 , 夏洪山 . 基于协同多任务分配的飞机排班模型与算法[J]. 航空学报, 2011 , 32(12) : 2293 -2302 . DOI: CNKI:11-1929/V.20110815.1716.003
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.
[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)
/
| 〈 |
|
〉 |
CJA