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

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

CLC Number:

V355.2

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.

References

[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)

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

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Nongtian CHEN, Yucheng ZHANG, Linlin LI, Youming ZHENG. Multi-objective optimization of robustness of aircraft scheduled maintenance task scheduling duration based on improved NSGA-Ⅱ [J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(8): 232675-232675.
[2]	Jian PENG, Guanglei ZHU, Qingshun WU, Yafei LI, Shuo HE, Yuanyuan JIN, Mingliang XU. Scheduling method for carrier-based aircraft support operations based on Monte Carlo tree search [J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(6): 332444-332444.
[3]	Peizhao WANG, Ming HE, Haihua CHEN, Hongpeng WANG. Real-time task scheduling algorithm for FANET considering communication topology control [J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(6): 332636-332636.
[4]	Yujie YUAN, Jiashuai LI, Xinyi ZHAO, Yantao WANG. eVTOL scheduling schemes for dynamic demand and variable intervals [J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(1): 631907-631907.
[5]	Ye TAO, Jinhui TANG, Zhen YAN, Chen ZHOU, Chong WANG. A trajectory imputation method integrating representation transformation and pattern regression [J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(1): 332106-332106.
[6]	Weiwei CAI, Guohua WU, Hengwei LI, Qian YIN. Multi-objective scheduling optimization method for relay satellites considering user preferences [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(8): 331074-331074.
[7]	Jinlun ZHOU, Honghai ZHANG, Wenqing LI. Key technologies and deployment routes for advancing autonomous operations in civil aviation [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(22): 331998-331998.
[8]	Yizhe LUO, Hui ZHANG, Xinde YU, Zhao JIN, Shuo FENG, Yucheng SHI, Mingling XU. Hierarchical dynamic scheduling for multi-wave carrier-based aircraft ammunition support missions [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(18): 331945-331945.
[9]	Fang GUO, Wei HAN, Yujie LIU, Jie LIU, Xichao SU, Liangliang CHENG. Scheduling for maintenance and service support of carrier-based aircraft based on variable operation process [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531195-531195.
[10]	Wei CHEN, Lulu LI, Dong CHEN, Shaohui ZHANG, Yafei LI, Ke WANG, Yuanyuan JIN, Mingliang XU. Multi-aircraft cooperative decision-making methods driven by differentiated support demands for carrier-based aircraft [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531274-531274.
[11]	Xudong CHEN, Qiqi CHEN, Yizhe LUO, Jiabao WANG, Mingliang XU. Dynamic parallel scheduling of heterogeneous carrier-based aircraft deck support operations [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531329-531329.
[12]	Gang ZHONG, Junming HUA, Sen DU, Yupu LIU, Hao LIU, Honghai ZHANG. Urban low-altitude flight plan optimal scheduling based on complex network [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531479-531479.
[13]	Changxiao ZHAO, Yixuan SUN. A safe scheduling model for eVTOL avionics systems for airworthiness requirements [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531252-531252.
[14]	Fan PU, Zhijie CHEN, Yang LIU, Xin GENG, Yongwen ZHU, Kejin REN. Air traffic management technologies for digital low-altitude integrated operations [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531331-531331.
[15]	Guang LIU, Hua WANG, Youfang LIN, Shuo HE, Yafei LI, Mingliang XU. Adaptive batch matching decision method for carrier-based aircraft support operations [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(1): 330615-330615.