基于秩2矩阵近似的飞机起降多目标调度模型与算法研究

doi:10.15960/j.cnki.issn.1007-6093.2024.04.003

摘要/Abstract

摘要：

飞机起降调度问题是当前机场运营的重要问题, 调度的一个难点在于调度效率提升需要空管发出大量复杂指令, 导致空管工作量骤升, 超负荷工作易引起人员疲劳产生决策失误和安全隐患。鉴于此构建了单跑道起降调度的多目标混合整数规划模型, 既提升跑道效率又避免过度增加空管工作量。设计了基于秩2矩阵近似的蚁群算法(RMA-AC)求解, 并与CPLEX和经典M-TPLP算法进行对比。数值仿真证实三种方法都优于当前航空系统广泛使用的FCFS算法; 新算法RMA-AC在跑道效率提升方面强于CPLEX, 在控制飞机位置总偏移量方面强于M-TPLP, 实现了平衡跑道效率和空管工作量。这些对于提高机场效率, 降低航空拥堵, 实现安全调度具有积极意义。

关键词: 飞机安全调度, 多目标混合整数规划, 秩2矩阵近似, CPLEX

Abstract:

The aircraft takeoff/landing scheduling problem is an important problem for current airport operations. One difficulty in scheduling is that improving scheduling efficiency requires air traffic controller to issue more instructions, leading to a sharp increase in air traffic control workload. Overloading work may cause personnel fatigue, decision-making errors, and safety hazards. In view of this situation, a multi-objective mixed integer programming model for single runway takeoff/landing scheduling was constructed, which not only considers improving runway efficiency but also avoids excessively increasing air traffic control workload. The rank 2 matrix approximation based ant colony (RMA-AC) algorithm was designed. In comparison with the classical M-TPLP algorithm and CPLEX optimizer, numerical result validates that all the three methods have better performance than the first come first sever (FCFS) algorithm which is widely used in current aviation system. Specifically, the new algorithm RMA-AC is better than CPLEX for the runway efficiency improvement, and better than M-TPLP for the aircraft position shift control. It balances the runway efficiency and the air traffic controller workload. All these have positive effect on the airport efficiency improvement, delay reduction and safety scheduling.

Key words: aircraft safety scheduling, multi-objective mixed integer programming, rank 2 matrix approximation, CPLEX

中图分类号:

C931

徐博, 马卫民, 柯华, 张浩. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究[J]. 运筹学学报（中英文）, 2024, 28(4): 29-43.

Bo XU, Weimin MA, Hua KE, Hao ZHANG. Research on the multi-objective model and algorithm for aircraft takeoff/landing scheduling based on rank 2 matrix approximation[J]. Operations Research Transactions, 2024, 28(4): 29-43.

图/表 10

图1

表1

图2

图3

图4

表2

表3

三种方法求解文献[22]算例的结果比较"

数据			FCFS	CPLEX		M-TPLP		RMA-AC
编号	飞机类型	最早开始时间/s	起降时间/s	编号	起降时间/s	编号	起降时间/s	编号	起降时间/s
1	2	71	71	1	71	2	128	3	154
2	2	128	178	2	178	3	202	1	287
3	1	154	252	3	252	1	335	6	361
4	5	348	348	4	348	4	370	4	401
5	4	353	408	5	408	6	420	2	494
6	1	355	458	6	458	5	460	5	529
7	1	474	557	7	557	7	519	7	579
8	1	622	656	8	656	8	633	9	628
9	4	628	696	9	696	9	673	8	678
10	6	640	816	10	816	11	829	10	748
11	3	651	881	11	881	10	859	11	874
12	4	734	911	12	911	12	919	12	904
13	4	807	971	13	971	15	1 024	13	964
14	4	1 011	1 031	15	1 024	13	1 059	15	1 017
15	2	1 013	1 084	14	1 059	16	1 131	14	1 052
16	2	1 113	1 191	16	1 131	14	1 166	16	1 124
17	5	1 160	1 226	17	1 166	20	1 262	18	1 161
18	4	1 161	1 286	18	1 226	17	1 292	21	1 224
19	4	1 175	1 346	20	1 291	21	1 342	19	1 264
20	3	1 221	1 411	19	1 321	18	1 382	20	1 420
21	1	1 224	1 485	21	1 371	23	1 447	17	1 450
22	2	1 404	1 618	22	1 504	19	1 487	22	1 503
23	1	1 430	1 692	23	1 578	22	1 580	23	1 577
24	4	1 520	1 732	24	1 618	24	1 615	24	1 617
25	5	1 526	1 822	26	1 677	26	1 665	26	1 676
26	1	1 599	1 872	25	1 717	25	1 705	25	1 716
27	1	1 699	1 971	27	1 776	27	1 764	27	1 775
28	1	1 744	2 070	30	1 816	30	1 814	30	1 815
29	2	1 807	2 203	29	1 909	28	1 864	29	1 908
30	6	1 814	2 238	28	1 983	31	1 904	31	1 943
31	6	1 874	2 298	31	2 023	29	1 997	28	1 993
32	5	1 959	2 358	32	2 083	32	2 032	32	2 033
33	4	2 082	2 418	33	2 143	33	2 092	33	2 093
34	3	2 195	2 483	34	2 208	34	2 224	34	2 195
35	6	2 241	2 538	35	2 263	35	2 254	35	2 241
36	1	2 250	2 588	37	2 328	37	2 322	37	2 306
37	3	2 283	2 784	38	2 360	38	2 360	38	2 360
38	5	2 360	2 814	36	2 410	36	2 410	36	2 410
39	5	2 379	2 874	39	2 450	39	2 450	39	2 450
40	4	2 392	2 934	40	2 510	40	2 510	40	2 510
队列完成时间/s			2 934		2 510^*		2 510^*		2 510^*
位置移动总量					14^*		40		34
CPU耗时/s					1.8		20		20

表3

图5

表4

图6

参考文献 31

1	Boeing. Commercial market outlook 2023—2042 [EB/OL]. (2024-02-01)[2024-02-01]. http://www.boeing.com/commercial/cmo/.
2	中国民航网[EB/OL]. (2024-01-31)[2024-02-01]. http://www.caacnews.com.cn/#.
3	Gudmundsson S V , Cattaneo M , Redondi R . Forecasting temporal world recovery in air transport markets in the presence of large economic shocks: The case of covid-19[J]. Journal of Air Transport Management, 2021, 91 (102007): 1- 8.
4	Bennell J A , Mesgarpour M , Potts C N . Airport runway scheduling[J]. 4OR, 2011, 9, 115- 138. doi: 10.1007/s10288-011-0172-x
5	武汉市网信办. 湖北客货"双枢纽"建设再加力天河机场三跑道拿到"准生证"[EB/OL]. (2022-04-06)[2024-02-01]. https://www.sohu.com/a/535759288_100199096.
6	Beasley J E , Krishnamoorthy M , Sharaiha Y M , et al. Scheduling aircraft landings-the static case[J]. Transportation Science, 2000, 34 (2): 180- 197. doi: 10.1287/trsc.34.2.180.12302
7	Balakrishnan H , Chandran B G . Algorithms for scheduling runway operations under constrained position shifting[J]. Operations Research, 2010, 58 (6): 1650- 1665. doi: 10.1287/opre.1100.0869
8	Ikli S , Mancel C , Mongeau M , et al. The aircraft runway scheduling problem: A survey[J]. Computers & Operations Research, 2021, 132 (1): 1- 20.
9	Brinton C R. An implicit enumeration algorithm for arrival aircraft scheduling [C]//Proceedings of the IEEE/AIAA 11th Digital Avionics Systems Conference, 1992: 268-274.
10	Prakash R , Piplani R , Desai J . An optimal data-splitting algorithm for aircraft scheduling on a single runway to maximize throughput[J]. Transportation Research Part C, 2018, 95, 570- 581. doi: 10.1016/j.trc.2018.07.031
11	Prakash R , Piplani R , Desai J . An optimal data-splitting algorithm for aircraft sequencing on two runways[J]. Transportation Research Part C, 2021, 132, 1- 15.
12	Pohl M , Kolisch R , Schiffer M . Runway scheduling during winter operations[J]. Omega, 2021, 102, 1- 16.
13	王菲, 张军峰, 葛腾腾, 等. 基于分支定界的离场航空器动态排序[J]. 南京航空航天大学学报, 2015, 47 (4): 547- 552.
14	张军峰, 王菲, 葛腾腾. 基于分支定界法的进场航空器动态排序与调度[J]. 系统仿真学报, 2016, 28 (8): 1909- 1914.
15	Hu X B , Chen W H . Receding horizon control for aircraft arrival sequencing and scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2005, 6 (1): 189- 197.
16	Randall M C. Scheduling aircraft landings using ant colony optimization [C]//Proceedings of the I-ASTED International Conference Artificial Intelligence and Soft Computing, 2002.
17	Zhan Z H , Zhang J , Li Y , et al. An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11 (2): 399- 412.
18	Wu L J, Zhan Z H, Hu X M, et al. Multi-runway aircraft arrival scheduling: A receding horizon control based ant colony system approach [C]//Proceedings of 2019 IEEE Congress on Evolutionary Computation, 2019: 538-545.
19	Bencheikh G , Boukachour J , Alaoui A E H . Improved ant colony algorithm to solve the aircraft landing problem[J]. International Journal of Computer Theory and Engineering, 2011, 3 (2): 224- 233.
20	Bencheikh G , Boukachour J , Alaoui A E H . A memetic algorithm to solve the dynamic multiple runway aircraft landing problem[J]. Journal of King Saud University Computer and Information Sciences, 2016, 28 (1): 98- 109.
21	李冠彬, 詹志辉, 张军. 蚁群算法优化到达航班排序和调度问题的研究[J]. 计算机工程与设计, 2009, 30 (17): 4047- 4052.
22	马卫民, 杨文娟, 徐博. 单跑道混合起降飞机排序问题的优化算法研究[J]. 系统工程学报, 2018, 33 (1): 125- 135.
23	温馨, 霍佳震. 基于动态优先级的多跑道混合起降航班调度问题研究[J]. 工业工程与管理, 2021, 26 (2): 1- 8.
24	Ma W , Xu B , Liu M , et al. An efficient approximation algorithm for aircraft arrival sequencing and scheduling problem[J]. Mathematical Problems in Engineering, 2014, 236756, 1- 8.
25	Faye A . Solving the aircraft landing problem with time discretization approach[J]. European Journal of Operational Research, 2015, 242, 1028- 1038.
26	Ma W , Xu B , Liu M , et al. An efficient algorithm based on sparse optimization for the aircraft departure scheduling problem[J]. Computational & Applied Mathematics, 2016, 35, 371- 387.
27	Lieder A , Stolletz R . Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 88, 167- 188.
28	Xu B . An efficient ant colony algorithm based on wake-vortex modeling method for aircraft scheduling problem[J]. Journal of Computational and Applied Mathematics, 2017, 317, 157- 170.
29	Dorigo M. Optimization, learning and natural algorithms [D]. Milano: Politecnico di Milano, 1992.
30	黄敏, 任亮, 王兴伟. 带有随机运输时间和成本的4PL路径优化问题[J]. 系统工程学报, 2019, 34 (1): 82- 101.
31	Hancerliogullari G , Rabadi G , Al-Salem A H . Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem[J]. Journal of Air Transport Management, 2013, 32 (6): 39- 48.

飞机数量	FCFS	CPLEX			M-TPLP			RMA-AC
飞机数量	队列完成时间/s	对FCFS改善/%	平均位置移动量	CPU耗时/s	对FCFS改善/%	平均位置移动量	CPU耗时/s	对FCFS改善/%	平均位置移动量	CPU耗时/s
40	3 111	6.37^*	15.6^*	15	3.52	69.6	30	5.10	65.2	30
80	5 895	1.36	10.4	30	3.64	271.2	30	4.53	104.4	30
120	9 138	0.94	6.8	30	4.44	574.0	30	5.21	238.4	30
160	11 754	1.33	8.4	30	3.43	956.8	30	3.97	250.4	30
200	14 903	0.64	7.6	30	4.24	1 440.0	30	3.44	840.8	30
240	17 234	0.41	5.6	30	1.85	932.0	30	1.53	534.0	30
280	20 494	0.54	3.6	30	3.13	1 176.8	30	2.94	566.8	30
320	23 467	0.37	5.6	30	3.43	1 308.4	30	2.10	632.0	30
360	26 320	0.16	1.6	30	2.88	1 312.8	30	1.89	1 196.0	30
400	29 181	0.24	1.6	30	2.83	814.8	30	0.42	832.8	30
440	31 850	0.17	0.8	30	2.36	1 132.8	30	1.08	389.2	30
480	34 887	0.13	1.6	30	2.67	1 684.0	30	1.46	1 288.8	30
520	38 105	0.31	2.8	30	3.20	1 699.6	30	1.40	1 272.0	30
560	40 559	0.05	0.4	30	2.19	2 260.0	30	0.41	1 266.8	30
600	43 430	0.25	0.4	30	2.49	3 059.6	30	0.59	900.0	30
640	46 587	0.12	1.2	30	2.67	2 210.0	30	0.12	2	30
680	49 128	0.16	0.4	30	1.80	1 852.8	30	0.78	243.2	30
720	51 843	0.04	0.4	30	1.88	2 032.8	30	0.39	838.8	30
760	54 641	0.12	0.8	30	1.77	1 974.4	30	0.12	3.2	30
800	57 245	0.08	0.4	30	0.98	2 482.0	30	0.08	1.6	30