Aircraft Assignment Method for Optimal Utilization of Maintenance Intervals

doi:10.16182/j.issn1004731x.joss.22-0546

Abstract

Abstract:

The aircraft assignment problem is studied from a maintenance assurance perspective. In order to ensure its continuous airworthiness, civil aircraft are required to perform maintenance tasks, i.e., scheduled inspections, at specified intervals. The scheduled inspection interval is usually controlled by the number of flight cycles (FC), flight hours (FH), or flight days (FD), whichever comes first. In order to make balanced use of the inspection interval, an aircraft assignment model for a given fleet size is developed to optimize the maintenance interval utilization, and it is solved by a reinforcement learning algorithm to minimize the variance of the FC and FH uniformly discounted at the time of maintenance interval arrival.The proposed method is computationally efficient and can be used to maximize the effectiveness of a single scheduled inspection and maintenance, saving maintenance costs and increasing aircraft utilization. Experiments are conducted by using authentic Chinese airline flight data. The experimental results show that the algorithm can find stable optimal solutions in the data of 761 flight legs in 129.448 seconds, and the Gap value is only 0.122 4%.

Key words: aircraft assignment, maintenance intervals, reinforcement learning, maintenance interval utilization, flight legs

CLC Number:

TP391.9

Guo Runxia, Wang Yifu. Aircraft Assignment Method for Optimal Utilization of Maintenance Intervals[J]. Journal of System Simulation, 2023, 35(9): 1985-1999.

Figures/Tables 17

Fig. 1

Fig. 2

Table 1

Relevant symbols and definitions

类型	名称	含义
集合	OFL	航班段的集合， $i, j, l ∈ O F L$
集合	MFL	在到达机场进行维护的航班段的集合, $i, j, l ∈ M F L$
集合	K	飞机的集合, $k ∈ K = 1,2, ⋯, k, ⋯$
集合	AP	飞机场的集合， $a ∈ A P$
参数	DT_i	航班段i的起飞时间
参数	AT_i	航班段i的到达时间
参数	FD_i	航班段i的累计飞行时间
参数	O_ia	$O i a = 1, 航班段 i 的起飞机场是 a 0, 其他$
参数	D_ia	$D i a = 1, 航班段 i 的到达机场是 a 0, 其他$
参数	v	一个整数，代表飞机被维护的次数
参数	T_max	每架飞机在两次连续维护之间所允许的最大累积飞行时间
参数	TF_max	每架飞机在两次连续维护之间所允许的最大飞行循环。
参数	TAT	周转时间(Turnaround time)。用于下机，行李装卸，更换登机口，飞机加油等
决策变量	$X i j k v$	一个0-1变量。 $X i j k v = 1$ 如果飞机k执飞完连续航班段i和j后不进行第v次维护操作； $X i j k v = 0$ 其他
决策变量	$Y i j k v$	一个0-1变量。 $Y i j k v = 1$ 如果飞机k执飞完连续航班段i和j后进行第v次维护操作； $Y i j k v = 0$ 其他

Table 1

Fig. 3

Fig. 4

Table 2

Prepared tools

名称	类型	名称
Q-table	DataFrame	状态价值表，行索引是列表 $w h o l e_a c t i o n$ 中的元素，列索引是列表 $w h o l e_s t a t e$ 中的元素。表内元素初始化为0
Cu-table	DataFrame	用来存储可选动作空间CU的状态值
IU	Dictionary	形如 $' k' : [' k', v, f l i g h t_t i m e, F L 1, F L 2, ⋯]$ ，其中 $f l i g h t_t i m e$ 是进行维护操作v和下一次维护操作之间的累积飞行时间。初始状态为空
NIU	Dictionary	形如 $' k' : v, ⋯$ ，这用来存储维修后可投入使用但尚未允许的飞机信息。初始状态为 $' 1' : 0,' 2' : 0, ⋯,' N' : 0$ ，其中机队规模为N
MTN	Dictionary	形如 $' k' : [c, v]$ ，用于存储要维护飞机的相关信息。初始状态为空

Table 2

Fig. 5

Fig. 6

Table 3

Fig. 7

Fig. 8

Table 4

Fig. 9

Fig. 10

Table 5

Experimental results of different test cases

案例	m_best	$m ¯$	$t ¯ / s$	Gap%	有无维修
1	0.408 974	0.409 744	11.688 5	0.188 1	No
2	1.115 38	1.123 72	16.043 5	0.747 1	No
3	1.719 23	1.721 15	28.477 3	0.111 9	No
4	2.693 59	2.695 77	44.708 2	0.080 9	No
5	0.967 949	0.968 333	59.201 5	0.039 7	No
6	4.150 00	4.155 08	129.448	0.122 4	Yes

Table 5

Fig. 11

Table 6

References 26

1	Temucin T, Tuzkaya G, Vayvay O. Aircraft Maintenance Routing Problem-a Literature Survey[J]. Promet-Traffic & Transportation, 2021, 33(4): 491-503.
2	Jamili A. A Robust Mathematical Model and Heuristic Algorithms for Integrated Aircraft Routing and Scheduling, with Consideration of Fleet Assignment Problem[J]. Journal of Air Transport Management, 2017, 58: 21-30.
3	Eltoukhy A E E, Wang Z X, Chan F T S, et al. Robust Aircraft Maintenance Routing Problem Using a Turn-around Time Reduction Approach[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 50(12): 4919-4932.
4	Bulbul K G, Kasimbeyli R. Augmented Lagrangian Based Hybrid Subgradient Method for Solving Aircraft Maintenance Routing Problem[J]. Computers & Operations Research, 2021, 132: 105294.
5	Başdere Mehmet, Bilge Ümit. Operational Aircraft Maintenance Routing Problem with Remaining Time Consideration[J]. European Journal of Operational Research, 2014, 235(1): 315-328.
6	Yan Chiwei, Kung J. Robust Aircraft Routing[J]. Transportation Science, 2018, 52(1): 118-133.
7	Maher S J, Desaulniers G, Soumis François. The Daily Tail Assignment Problem Under Operational Uncertainty Using Look-ahead Maintenance Constraints[J]. European Journal of Operational Research, 2018, 264(2): 534-547.
8	Eltoukhy A E E, Wang Z X, Chan F T S, et al. Data Analytics in Managing Aircraft Routing and Maintenance Staffing with Price Competition by a Stackelberg-Nash Game Model[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 122: 143-168.
9	Eltoukhy A E E, Chan F T S, Chung S H, et al. A Model with a Solution Algorithm for the Operational Aircraft Maintenance Routing Problem[J]. Computers & Industrial Engineering, 2018, 120: 346-359.
10	Özkır Vildan, Mahmud Sami Özgür. Two-phase Heuristic Algorithm for Integrated Airline Fleet Assignment and Routing Problem[J]. Energies, 2021, 14(11): 3327.
11	Chen C H, Chou F I, Chou J H. Multiobjective Evolutionary Scheduling and Rescheduling of Integrated Aircraft Routing and Crew Pairing Problems[J]. IEEE Access, 2020, 8: 35018-35030.
12	Liang Zhe, Chaovalitwongse W A, Huang H C, et al. On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem[J]. Transportation Science, 2011, 45(1): 109-120.
13	李耀华, 王磊. 基于改进遗传算法的飞机排班优化方法研究[J]. 系统仿真学报, 2016, 28(3): 620-626.
	Li Yaohua, Wang Lei. Study on Aircraft Scheduling Optimization Based on Improved Genetic Algorithm[J]. Journal of System Simulation, 2016, 28(3): 620-626.
14	Al-Thani N A, Ben Ahmed M, Haouari M. A Model and Optimization-based Heuristic for the Operational Aircraft Maintenance Routing Problem[J]. Transportation Research Part C-Emerging Technologies, 2016, 72: 29-44.
15	Cui Ruyu, Dong Xingye, Lin Youfang. Models for Aircraft Maintenance Routing Problem with Consideration of Remaining Time and Robustness[J]. Computers & Industrial Engineering, 2019, 137: 106045.
16	Eltoukhy A E E, Chan F T S, Chung S H, et al. Heuristic Approaches for Operational Aircraft Maintenance Routing Problem with Maximum Flying Hours and Man-power Availability Considerations[J]. Industrial Management & Data Systems, 2017, 117(10): 2142-2170.
17	Ruan J H, Wang Z X, Chan F T S, et al. A Reinforcement Learning-based Algorithm for the Aircraft Maintenance Routing Problem[J]. Expert Systems with Applications, 2021, 169: 114399.
18	Drakaki M, Tzionas P. Manufacturing Scheduling Using Colored Petri Nets and Reinforcement Learning[J]. Applied Sciences, 2017, 7(2): 136.
19	Wang Haoxiang, Sarker B R, Li Jing, et al. Adaptive Scheduling for Assembly Job Shop with Uncertain Assembly Times Based on Dual Q-learning[J]. International Journal of Production Research, 2021, 59(19): 5867-5883.
20	Chen Ronghua, Yang Bo, Li Shi, et al. A Self-learning Genetic Algorithm Based on Reinforcement Learning for Flexible Job-shop Scheduling Problem[J]. Computers & Industrial Engineering, 2020, 149: 106778.
21	Zhou Tong, Tang Dunbing, Zhu Haihua, et al. Reinforcement Learning with Composite Rewards for Production Scheduling in a Smart Factory[J]. IEEE Access, 2021, 9: 752-766.
22	Guo W, Atasoy B, Negenborn R R. Global Synchromodal Shipment Matching Problem with Dynamic and Stochastic Travel Times: a Reinforcement Learning Approach[J/OL]. Annals of Operations Research, 2022. (2022-01-21) [2022-03-15]. .
23	Zhang Ke, He Fang, Zhang Zhengchao, et al. Multi-vehicle Routing Problems with Soft Time Windows: A Multi-agent Reinforcement Learning Approach[J]. Transportation Research Part C: Emerging Technologies, 2020, 121: 102861.
24	Eda Köksal Ahmed, Li Zengxiang, Veeravalli B, et al. Reinforcement Learning-enabled Genetic Algorithm for School Bus Scheduling[J]. Journal of Intelligent Transportation Systems, 2022, 26(3): 269-283.
25	He Shengxue, He Jianjia, Liang Shidong, et al. A Dynamic Holding Approach to Stabilizing a Bus Line Based on the Q-learning Algorithm with Multistage Look-ahead[J]. Transportation Science, 2022, 56(1): 31-51.
26	Šemrov D, Marsetič R, Žura M, et al. Reinforcement Learning Approach for Train Rescheduling on a Single-track Railway[J]. Transportation Research Part B: Methodological, 2016, 86: 250-267.

航班段	飞机编号
航班段	1	2	3	4	5	6	…
1	35.615 770	74.899 057	22.182 434	56.255 023	30.230 163	20.566 729	…
2	23.066 095	40.096 695	14.022 655	24.676 447	14.022 655	40.003 080	…
3	25.138 153	0	35.558 799	23.353 293	19.880 945	22.608 453	…
4	0	25.842 968	18.171 796	36.765 886	18.595 400	33.518 226	…
5	0	26.769 401	7.962 807	13.026 680	6.016 170	6.892 842	…
6	19.287 721	17.136 571	4.150 836	6.983 535	0	4.057 789	…
7	13.914 893	8.576 375	3.251 386	8.346 326	11.842 005	18.997 614	…
8	4.131 718	15.623 605	0	7.608 969	9.590 552	9.538 389	…
…	…	…	…	…	…	…	…

案例	Q-learning-based		Gurobi
案例	m_best	t/s	M_g-best	t/s
1	0.408 974	10.282 5	0.408 974	9.753 39
2	1.115 38	15.121 4	1.115 38	65.755 9
3	1.719 23	27.912 1	1.719 23	652.556
4	2.693 59	42.611 5	2.693 59	2 400.00
5	0.967 949	58.856 4	0.967 949	5 000.00
6	4.150 00	128.125	4.186 45	8 000.00

[1]	Junqiang Lin, Hongjun Wang, Xiangjun Zou, Po Zhang, Chengen Li, Yipeng Zhou, Shujie Yao. Obstacle Avoidance Path Planning and Simulation of Mobile Picking Robot Based on DPPO [J]. Journal of System Simulation, 2023, 35(8): 1692-1704.
[2]	Jiayi Liu, Gang Wang, Qiang Fu, Xiangke Guo, Siyuan Wang. Intelligent Air Defense Task Assignment Based on Assignment Strategy Optimization Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1705-1716.
[3]	Laiyi Yang, Jing Bi, Haitao Yuan. Intelligent Path Planning for Mobile Robots Based on SAC Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1726-1736.
[4]	Fei Ding, Yuchen Sha, Ying Hong, Xiao Kuai, Dengyin Zhang. Joint Optimization Strategy of Computing Offloading and Edge Caching for Intelligent Connected Vehicles [J]. Journal of System Simulation, 2023, 35(6): 1203-1214.
[5]	Yuxuan Dai, Chenggang Cui. Deep Reinforcement Learning-Based Control Strategy for Boost Converter [J]. Journal of System Simulation, 2023, 35(5): 1109-1119.
[6]	Haotian Xu, Long Qin, Junjie Zeng, Yue Hu, Qi Zhang. Research Progress of Opponent Modeling Based on Deep Reinforcement Learning [J]. Journal of System Simulation, 2023, 35(4): 671-694.
[7]	Ding Shi, Xuefeng Yan, Lina Gong, Jingxuan Zhang, Donghai Guan, Mingqiang Wei. Multi-agent Cooperative Combat Simulation in Naval Battlefield with Reinforcement Learning [J]. Journal of System Simulation, 2023, 35(4): 786-796.
[8]	Zhiqiang Li, Yuanlong Li, Laixiang Yin, Xiangping Ma. Research on Unmanned Swarm Combat System Adaptive Evolution Model Simulation [J]. Journal of System Simulation, 2023, 35(4): 878-886.
[9]	Jiajie Shi, Peng Yang, Yannan Pi. Machine Learning-based Simulation Research of On-line Subway Pedestrian Flow Control [J]. Journal of System Simulation, 2023, 35(2): 386-395.
[10]	Naiyang Xue, Dan Ding, Yutong Jia, Zhiqiang Wang, Yuan Liu. DQN-based Joint Scheduling Method of Heterogeneous TT&C Resources [J]. Journal of System Simulation, 2023, 35(2): 423-434.
[11]	Yejian Zhao, Yanhong Wang, Jun Zhang, Hongxia Yu, Zhongda Tian. Application of Improved Q Learning Algorithm in Job Shop Scheduling Problem [J]. Journal of System Simulation, 2022, 34(6): 1247-1258.
[12]	Sen Zhang, Mengyan Zhang, Jingping Shao, Jiexin Pu. Multi-UAVs 3D Path Planning Method Based on Random Strategy Search [J]. Journal of System Simulation, 2022, 34(6): 1286-1295.
[13]	Lingjia Ni, Xiaoxia Huang, Hongga Li, Zibo Zhang. Research on Fire Emergency Evacuation Simulation Based on Cooperative Deep Reinforcement Learning [J]. Journal of System Simulation, 2022, 34(6): 1353-1366.
[14]	Hongwei Wang, Peng Yang. Research on Optimization of Airport Cargo Business Based on Deep Reinforcement Learning [J]. Journal of System Simulation, 2022, 34(3): 651-660.
[15]	Xiaohan Wang, Lin Zhang, Yuanjun Laili, Kunyu Xie, Tingchun Hu. Constructing the Agent Discrete Simulation Based on DEVS Atomic Model [J]. Journal of System Simulation, 2022, 34(2): 191-200.