-
摘要:
航班着陆调度问题已被证明是NP难问题，综合考虑多种实际情况，建立了时间窗约束的航班着陆优化模型，定义了紧致子序列概念，论述了其性质及左移、分割和合并的条件。在此基础上，提出一种基于紧致子序列的算法(CSA)求解固定顺序下航班着陆调度问题。按照航班的最优着陆时间排序，运用CSA计算出该顺序下各航班着陆时间；采用循环线性交换和循环线性插空策略微调该固定顺序，不断迭代逼近模型的最优解；采用OR-Library数据集进行验证。实验结果表明，CSA结合启发式微调策略求解结果明显优于位移决策算法DALP和仿生算法(BA)，与CPLEX、混合粒子群优化-局部搜索算法RH-HPSO-LS、细胞自动机优化(CAO)算法相近，在时间效率上明显优于对比算法；在小规模数据集上，计算精度与速度优势更加明显。CSA是一种确定性算法，不依赖于先验参数，具有更高的鲁棒性，保证了启发式微调策略不断逼近最优解。
Abstract:The aircraft landing scheduling problem has been proven to be an NP-hard problem. A multi-aircraft optimization model with time window constraints is established for the fixed aircraft scheduling sequence considering more practical situations. The concept of compact subsequence, its properties, left shift, division and merging conditions are discussed. A compact subsequence algorithm (CSA) for fixed-order aircraft landing problems is proposed. Sort by the optimal landing time of the aircraft and calculate the landing time of each aircraft in this order using CSA. Adjust the fixed order using the circular linear exchange and cyclic linear interpolation strategies. Then, compute iteratively to get an approximation of the model’s ideal solution. The OR-Library dataset is used for verification. Comparable to the CPLEX, RH-HPSO-LS, and cellular automation-based optimization (CAO), the results demonstrate that CSA, when paired with a heuristic fine-tuning method, can yield much superior outcomes than DALP and bionomic algorithm (BA). The algorithm also shows better advantages in time efficiency. It is extremely obvious that the advantages of computing precision and speed on small-scale datasets. CSA is a deterministic method that does not depend on prior parameters and has higher robustness, it can ensure that the heuristic fine-tuning strategy approaches the optimal solution continuously.
-
图 4 航班着陆时间初始值确定流程
Figure 4. Flow diagram for determining initial value of aircraft landing time
表 1 不同类型航班最小时间间隔
Table 1. Minimum time interval between different types of aircrafts
s 航班类型 后续航班 轻型 中型 重型 轻型 82 69 60 中型 131 69 60 重型 196 157 96 
下载: 导出CSV
表 2 数据集各组航班数量
Table 2. Various aircraft sizes in each group of dataset
组别 航班数量 Airland1 10 Airland2 15 Airland3 20 Airland4 20 Airland5 20 Airland6 30 Airland7 44 Airland8 50 Airland9 100 Airland10 150 Airland11 200 Airland12 250 Airland13 500
下载: 导出CSV
表 3 实验数据属性
Table 3. Attribute of experimental data
属性 类型 示例 航班在管制雷达出现的时间/s 整型 1 最早着陆时间/s 整型 601 最优着陆时间/s 整型 908 最晚着陆时间/s 整型 2401 相对于最优时间提前着陆的单位代价 浮点型 1.45 相对于最优时间延后着陆的单位代价 浮点型 1.10 与其他航班的尾流时间间隔/s 列表 [90,90,···,113]
下载: 导出CSV
表 4 初始序列确定实验结果
Table 4. Experiment results for initial sequence determining
组别 BKV 总代价 FCFS SBT 1 700 1280 700 2 1480 1790 1500 3 820 1790 1730 4 2520 4890 2520 5 3100 6470 5420 6 24442 24442 24442 7 1550 1550 1550 8 1 950 18870 2510 9 5611 18937.16 8019.42 10 12329 27660 20806.94 11 12418 35532.91 18513.27 12 16209 46471.72 22937.88 13 44832 99776.58 49207.07
下载: 导出CSV
表 5 策略组合对比结果
Table 5. Comparative results of strategy combinations
组别 BKV 总代价 EBF EFB BFE BEF FEB FBE 1 700 700 700 700 700 700 700 2 1480 1480 1480 1480 1480 1480 1480 3 820 820 820 820 820 820 820 4 2520 2520 2520 2520 2520 2520 2520 5 3100 3100 3100 3100 3100 3100 3100 6 24442 24442 24442 24442 24442 24442 24442 7 1550 1550 1550 1550 1550 1550 1550 8 1950 1920 1920 1920 1920 1920 1920 9 5611 5750 5750.2 5618.9 5640.2 5618.6 5651.3 10 12329 12741.6 12627.5 13868.2 13865.9 12539.7 12590.1 11 12418 12418.3 12513.1 12447.4 12433.9 12544.7 12487.4 12 16209 16601.3 16742.4 16334.4 16527.6 16428.3 16714.2 13 44832 37536.4 37668.4 37730.1 37719.9 37625.7 37623.8 注：EBF、EFB、BFE、BEF、FEB、FBE策略组合的平均差值分别为−490.9、−471.3、−417.7、−403.2、−513.2、−489.4。
下载: 导出CSV
表 6 整体调度结果对比
Table 6. Comparison of overall scheduling results
组别 BKV 总代价 CPLEX DALP BA RH-HPSO-LS CAO CSA CSA+EBF CSA+FEB 1 700 700 740 700 700 700 700 700 700 2 1480 1480 1870 1480 1480 1480 1500 1480 1480 3 820 820 1440 820 820 820 1730 820 820 4 2520 2520 2670 2520 2520 2520 2520 2520 2520 5 3100 3100 6130 3100 3100 3100 5420 3100 3100 6 24442 24442 24442 24442 24442 24442 24442 24442 24442 7 1550 1550 3974 1550 1550 1550 1550 1550 1550 8 1950 1950 2915 2655 1950 1995 2510 1920 1920 9 5611 5611.7 7800.9 6425.9 5611.7 5611 8019.42 5750 5618.6 10 12329 12292.2 17726.1 16508.9 12292.2 12457 20806.9 12741.6 12539.7 11 12418 12418.3 14152.4 14488.4 12418.3 12439 18513.3 12418.3 12544.7 12 16209 16122.2 25049.2 20032.0 16122.2 16262 22937.8 16601.3 16428.3 13 44832 37848.9 58392.6 45294.1 37064.1 38573 49207.0 37536.4 37625.7 组别 运行时间/s CPLEX DALP BA RH-HPSO-LS CAO CSA CSA+EBF CSA+FEB 1 0.8 0.1 60 0.01 0.0025 0.001 0.001 0.001 2 0.8 0.5 90 0.03 0.0034 0.002 0.031 0.052 3 1.3 0.5 99 0.07 0.0042 0.005 0.004 0.005 4 2.3 0.9 95 0.10 0.0043 0.006 0.006 0.006 5 3.7 1.3 100 0.13 0.1945 0.006 0.007 0.006 6 0.7 0.6 274 0.22 0.0521 0.006 0.006 0.006 7 1.2 1.5 79 1.0 0.0857 0.015 0.015 0.015 8 2.2 3.1 287 0.76 1.711 0.021 0.375 0.622 9 932.2 5.7 554 5.8 6.272 0.065 3.260 2.301 10 3600 13.5 925 18.8 29.314 0.011 15.123 8.362 11 3600 22.6 1417 15.6 31.717 0.027 11.17 15.771 12 3600 43.2 2011 35.1 47.328 0.029 23.69 24.344 13 3600 249.5 5852 115.1 267.125 0.064 114.05 128.76
下载: 导出CSV
表 7 平均结果对比
Table 7. Comparison of average results
算法 总代价平均差值 平均运行时间/s CPLEX −546.6 1180.4 DALP 3026.2 26.4 BA 927.3 911 RH-HPSO-LS −607.0 14.8 CAO −462.5 29.5 CSA 2453.5 0.02 CSA+EBF −490.9 12.9 CSA+FEB −513.2 13.9
下载: 导出CSV
-
[1] 民航局运行监控中心. 图解2021年民航航班运行情况[EB/OL]. (2022-01-12) [2022-04-21]. https://m.thepaper.cn/baijiahao_16254749.Operation Monitoring Center of Civil Aviation Administration. Illustrating the operation of civil aviation flights in 2021[EB/OL]. (2022-01-12) [2022-04-21]. https://m.thepaper.cn/baijiahao_16254749 (in Chinese). [2] CIRIUM. The on-time performance review 2021[EB/OL]. (2021-12-31) [2022-04-21]. https://www.cirium.com/studios/on-time-performance. [3] 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 [4] BEASLEY J E, KRISHNAMOORTHY M, SHARAIHA Y M, et al. Displacement problem and dynamically scheduling aircraft landings[J]. Journal of the Operational Research Society, 2004, 55(1): 54-64. doi: 10.1057/palgrave.jors.2601650 [5] PINOL H, BEASLEY J E. Scatter search and bionomic algorithms for the aircraft landing problem[J]. European Journal of Operational Research, 2006, 171(2): 439-462. doi: 10.1016/j.ejor.2004.09.040 [6] HU X B, CHEN W H. Genetic algorithm based on receding horizon control for arrival sequencing and scheduling[J]. Engineering Applications of Artificial Intelligence, 2005, 18(5): 633-642. doi: 10.1016/j.engappai.2004.11.012 [7] HU X B, CHEN W H. Receding horizon control for aircraft arrival sequencing and scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2005, 6(2): 189-197. doi: 10.1109/TITS.2005.848365 [8] 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. doi: 10.1109/TITS.2010.2044793 [9] YU S P, CAO X B, ZHANG J. A real-time schedule method for aircraft landing scheduling problem based on cellular automation[J]. Applied Soft Computing, 2011, 11(4): 3485-3493. doi: 10.1016/j.asoc.2011.01.022 [10] VADLAMANI S, HOSSEINI S. A novel heuristic approach for solving aircraft landing problem with single runway[J]. Journal of Air Transport Management, 2014, 40: 144-148. doi: 10.1016/j.jairtraman.2014.06.009 [11] 王满超. 动态飞机着陆调度及其经验粒子群算法研究[D]. 天津: 中国民航大学, 2015: 4-5.WANG M C. Research on experiential particle swarm optimization for dynamic aircraft landing scheduling[D]. Tianjin: Civil Aviation University of China, 2015: 4-5(in Chinese). [12] SABAR N R, KENDALL G. An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem[J]. Omega, 2015, 56: 88-98. [13] GIRISH B S. An efficient hybrid particle swarm optimization algorithm in a rolling horizon framework for the aircraft landing problem[J]. Applied Soft Computing, 2016, 44: 200-221. doi: 10.1016/j.asoc.2016.04.011 [14] BENNELL J A, MESGARPOUR M, POTTS C N. Dynamic scheduling of aircraft landings[J]. European Journal of Operational Research, 2017, 258(1): 315-327. doi: 10.1016/j.ejor.2016.08.015 [15] JI X P, CAO X B, DU W B, et al. An evolutionary approach for dynamic single-runway arrival sequencing and scheduling problem[J]. Soft Computing, 2017, 21(23): 7021-7037. doi: 10.1007/s00500-016-2241-8 [16] FAYE A. A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes[J]. European Journal of Operational Research, 2018, 270(3): 1148-1157. doi: 10.1016/j.ejor.2018.04.021 [17] AHMED M, ALAM S, BARLOW M. A cooperative co-evolutionary optimisation model for best-fit aircraft sequence and feasible runway configuration in a multi-runway airport[J]. Aerospace, 2018, 5(3): 85. doi: 10.3390/aerospace5030085 [18] IKLI S, MANCEL C, MONGEAU M, et al. An optimistic planning approach for the aircraft landing problem[C]//Proceedings of the ENRI International Workshop on ATM/CNS. Berlin: Springer, 2021: 173-188. [19] 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 [20] 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. doi: 10.1016/j.cam.2016.11.043 [21] DEAR R G, SHERIF Y S. An algorithm for computer assisted sequencing and scheduling of terminal area operations[J]. Transportation Research Part A: General, 1991, 25(2-3): 129-139. doi: 10.1016/0191-2607(91)90132-A -
下载:
点击查看大图
计量
- 文章访问数: 95
- HTML全文浏览量: 75
- PDF下载量: 2
- 被引次数: 0
