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

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

Abstract

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

CLC Number:

C931

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.

Figures/Tables 10

数据			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

References 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

Research on the multi-objective model and algorithm for aircraft takeoff/landing scheduling based on rank 2 matrix approximation

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 31

Related Articles 1

Recommended Articles

Metrics

Comments

			后面跟随飞机类型
			着陆飞机(Arrival)			起飞飞机(Departure)
			A1	A2	A3	D1	D2	D3
前面飞机类型	着陆飞机(Arrival)	A1	98	80	74	30	30	30
	着陆飞机(Arrival)	A2	131	107	74	35	35	35
		A3	196	133	99	40	40	40
	起飞飞机(Departure)	D1	65	53	50	60	60	60
	起飞飞机(Departure)	D2	65	53	50	90	60	60
		D3	65	53	50	120	90	60

算法	队列完成时间			平均CPU耗时	平均对FCFS改善/%	平均位置移动量
	最差解	最好解	平均值	平均CPU耗时	平均对FCFS改善/%	平均位置移动量
CPLEX	2 510	2 510	2 510	2	14.5	14
M-TPLP	2 618	2 510	2 535	10	13.6	51
RMA-AC	2 541	2 510	2 517	10	14.2	41
M-TPLP	2 607	2 510	2 547	20	13.2	48
RMA-AC	2 544	2 510	2 521	20	14.1	37
M-TPLP	2 607	2 510	2 547	60	13.2	47
RMA-AC	2 544	2 510	2 520	60	14.1	37