以维修间隔利用率最优为目标的飞机派遣方法

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

摘要/Abstract

摘要：

从维修保障的视角研究飞机派遣问题。民用飞机为确保其持续适航性，均要求在规定的时间间隔内执行检修任务即定检。定检时间间隔通常按照飞行循环(flight cycles, FC)、飞行小时(flight hours, FH)或日历日(flight days, FD)进行控制，先到为准。为了均衡的对定检时间间隔进行利用，以最优化维修间隔利用率为目标建立了给定机队规模的飞机派遣模型并通过强化学习算法予以求解，使得在维修间隔到达时刻，FC和FH统一折算后的方差最小。该派遣方法计算效率高，能够充分发挥单次定检维修的最大效能，节约维修成本并增加飞机的利用率。利用某航空公司的真实航班数据进行了实验，结果表明在最多761个航班段数据中，算法能够在129.448 s找到稳定的最优解，且Gap值仅为0.122 4%。

关键词: 飞机派遣, 维修间隔, 强化学习, 维修间隔利用率, 航班段

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

中图分类号:

TP391.9

郭润夏,王一府 . 以维修间隔利用率最优为目标的飞机派遣方法[J]. 系统仿真学报, 2023, 35(9): 1985-1999.

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

图/表 17

图 1

图 2

表 1

相关符号和定义

类型	名称	含义
集合	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$ 其他

表 1

图 3

图 4

表 2

准备工作

名称	类型	名称
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]$ ，用于存储要维护飞机的相关信息。初始状态为空

表 2

图 5

图 6

表 3

图 7

图 8

表 4

图 9

图10

表 5

不同测试案例的实验结果

案例	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

表 5

图11

表 6

参考文献 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]	林俊强, 王红军, 邹湘军, 张坡, 李承恩, 周益鹏, 姚书杰. 基于DPPO的移动采摘机器人避障路径规划及仿真[J]. 系统仿真学报, 2023, 35(8): 1692-1704.
[2]	刘家义, 王刚, 付强, 郭相科, 王思远. 基于分配策略优化算法的智能防空任务分配[J]. 系统仿真学报, 2023, 35(8): 1705-1716.
[3]	杨来义, 毕敬, 苑海涛. 基于SAC算法的移动机器人智能路径规划[J]. 系统仿真学报, 2023, 35(8): 1726-1736.
[4]	丁飞, 沙宇晨, 洪莹, 蒯晓, 张登银. 智能网联汽车计算卸载与边缘缓存联合优化策略[J]. 系统仿真学报, 2023, 35(6): 1203-1214.
[5]	戴宇轩, 崔承刚. 基于深度强化学习的Boost变换器控制策略[J]. 系统仿真学报, 2023, 35(5): 1109-1119.
[6]	徐浩添, 秦龙, 曾俊杰, 胡越, 张琪. 基于深度强化学习的对手建模方法研究综述[J]. 系统仿真学报, 2023, 35(4): 671-694.
[7]	石鼎, 燕雪峰, 宫丽娜, 张静宣, 关东海, 魏明强. 强化学习驱动的海战场多智能体协同作战仿真算法[J]. 系统仿真学报, 2023, 35(4): 786-796.
[8]	史佳洁, 杨鹏, 皮雁南. 基于机器学习的地铁行人流在线优化控制研究[J]. 系统仿真学报, 2023, 35(2): 386-395.
[9]	薛乃阳, 丁丹, 贾玉童, 王志强, 刘渊. 基于DQN的异构测控资源联合调度方法[J]. 系统仿真学报, 2023, 35(2): 423-434.
[10]	赵也践, 王艳红, 张俊, 于洪霞, 田中大. 改进Q学习算法在作业车间调度问题中的应用[J]. 系统仿真学报, 2022, 34(6): 1247-1258.
[11]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[12]	倪凌佳, 黄晓霞, 李红旮, 张子博. 基于协作式深度强化学习的火灾应急疏散仿真研究[J]. 系统仿真学报, 2022, 34(6): 1353-1366.
[13]	王红微, 杨鹏. 基于深度强化学习的机场货运业务优化研究[J]. 系统仿真学报, 2022, 34(3): 651-660.
[14]	王霄汉, 张霖, 赖李媛君, 谢堃钰, 胡听春. 基于DEVS原子模型的智能体离散仿真构建方法[J]. 系统仿真学报, 2022, 34(2): 191-200.
[15]	李启锐, 彭心怡. 基于深度强化学习的云作业调度及仿真研究[J]. 系统仿真学报, 2022, 34(2): 258-268.