ACTA AERONAUTICAET ASTRONAUTICA SINICA >
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
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.
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 -2302 . DOI: CNKI:11-1929/V.20110815.1716.003
[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