-
摘要:
为解决因突发事件产生的航空公司航班中断问题，对中断的离港航班进行恢复，构建最小化航空公司总延误成本和最小化乘客总延误时间的双目标优化模型，设计基于支配强度的自适应非支配排序遗传算法(ANSGA2-DS)。提出3种改进操作：快速支配排序方法、新的拥挤距离和自适应精英保留策略。通过福州长乐国际机场某航空公司的运行数据对所提算法进行验证，实验结果表明：与传统的先规划先服务方法相比，所提算法得到的解有大幅优化；与
ε 约束法相比，所提算法的求解时间总体上低于ε 约束法，且求解结果接近ε 约束法所得最优结果；与NSGA2、MOEAD等多目标优化算法相比，所提算法表现出更优的性能，能够有效且高效地解决问题,为航空公司达成优化的解决方案提供基础。Abstract:To solve the problem of airline flight disruption caused by emergencies, this paper recovers the disrupted departure flight. A bi-objective optimization model for minimizing airline delay cost and passenger delay time is constructed. An adaptive non-dominated sorting genetic algorithm-Ⅱ based on dominant strengths (ANSGA2-DS) is designed. The novel crowding distance, the adaptive elitist retention technique, and the quick dominant sorting approach are the three enhanced operations that are given. The proposed algorithm is verified by the operation data of an airline in Fuzhou Changle International Airport. The experimental results reveal that, compared with the traditional first scheduling first serve method, the algorithm proposed in this paper can reduce the costs greatly. In contrast to the
ε -constraint approach, theε -constrained approach requires a longer solution time, and the resulting solution results are similar to those of theε -constrained approach. Compared with the NSAG2 algorithm and the MOEAD algorithm, the algorithm proposed in this paper shows better performance. The proposed algorithm can solve the problem effectively and efficiently, and provide a basis for airlines to reach an optimized solution. -
图 3 ANSGA2-DS、NSGA2和MOEAD在3种场景中解的分布
Figure 3. Distribution of solutions of ANSGA2-DS, NSGA2 and MOEAD in three scenarios
图 4 不同算法中每个航班延误成本的比较
Figure 4. Comparison of each flight delay cost in different algorithms
图 5 不同算法中每个航班延误时间的比较
Figure 5. Comparison of each flight delay time in different algorithms
表 1 3种场景的信息
Table 1. Information of three scenarios
场景 航班数 中断持续时间/min 可分配的时隙数量 A 8 193 8 B 14 215 14 C 25 289 25 
下载: 导出CSV
表 2 场景A的信息
Table 2. Information of scenario A
航班号 原始离港时间 分配的时隙时间 乘客人数 1 11:10 11:45 134 2 11:25 12:20 330 3 11:47 12:16 182 4 11:59 12:55 149 5 12:05 13:55 222 6 12:28 13:58 379 7 12:55 14:00 112 8 12:59 14:23 310
下载: 导出CSV
表 3 场景B的信息
Table 3. Information of scenario B
航班号 原始离港时间 分配的时隙时间 乘客人数 1 13:30 14:06 248 2 13:40 14:17 330 3 13:45 14:49 332 4 13:55 14:53 207 5 13:59 14:58 225 6 14:20 14:59 218 7 14:29 15:08 150 8 14:29 15:20 137 9 14:40 15:32 167 10 14:48 15:36 129 11 14:50 15:47 83 12 14:51 15:57 283 13 14:54 16:05 180 14 15:37 17:05 332
下载: 导出CSV
表 4 场景C的信息
Table 4. Information of scenario C
航班号 原始离港时间 分配的时隙时间 乘客人数 1 16:20 16:50 134 2 16:25 16:58 109 3 16:34 17:37 317 4 16:40 17:55 339 5 17:48 18:32 129 6 17:55 19:58 285 7 18:23 20:05 300 8 18:40 20:11 225 9 18:49 20:15 134 10 19:15 20:22 78 11 19:45 20:25 109 12 19:48 20:30 285 13 19:59 20:32 167 14 19:59 20:46 225 15 20:13 20:51 233 16 20:27 21:55 86 17 20:30 22:00 137 18 20:38 22:04 135 19 20:40 22:32 285 20 20:56 22:41 112 21 21:00 22:50 317 22 21:09 22:59 285 23 21:15 23:00 202 24 21:25 23:05 134 25 22:30 23:09 129
下载: 导出CSV
表 5 不同参数组合结果
Table 5. Results of different parameter combination values
实验编号 组合参数 求解时间/s 解的数量 Z1/美元 Z2/min 平均间距/% Np ${p_{\text{m}}}$ ${p_{\text{c}}}$ 1 40 0.1 0.8 92.73 6 252519.67 265044 4.85 2 40 0.2 0.3 64.71 5 253105.21 270816 7.36 3 40 0.3 0.5 76.58 4 252137.38 265281 4.80 4 80 0.1 0.3 158.69 8 253409.55 275075 6.52 5 80 0.2 0.5 182.62 7 253223.97 264024 4.73 6 80 0.3 0.8 220.19 7 252830.51 262543 3.99 7 120 0.1 0.5 248.54 6 253572.43 267058 5.49 8 120 0.2 0.8 328.45 8 252246.05 263460 4.12 9 120 0.3 0.3 236.78 8 252798.59 280937 8.47
下载: 导出CSV
表 6 FSFS、ECA和ANSGA2-DS的计算结果
Table 6. Computational results of FSFS, ECA and ANSGA2-DS
场景 Z1/美元 Z2/min 求解时间/s Pareto 解个数 最大
公平
价格/%ANSGA2-DS
与 ECA的
平均间距/%FSFS ECA ANSGA2-DS FSFS ECA ANSGA2-DS FSFS ECA ANSGA2-DS FSFS ECA ANSGA2-DS A 282825.07 134789.56 135268.1 212552 149608 149832 14.57 23.42 7 14.23 4.88 B 389964.38 251490.85 253142.78 301887 243765 259467 345.91 40.73 6 5.61 4.71 C 739695.86 524925.70 531868.435 638448 416997 436982 9316.28 149.95 4 4.36 6.26
下载: 导出CSV
表 7 ANSGA2-DS、NSGA2和MOEAD的最优值、最大公平价格与反向世代距离的比较
Table 7. Comparison of the optimal value, the maximum price of fairness and IGD among ANSGA2-DS, NSGA2 and MOEAD
场景 Z1/美元 Z2/min 最大公平价格/% 反向世代距离/105 ANSGA2-DS NSGA2 MOEAD ANSGA2-DS NSGA2 MOEAD ANSGA2-DS NSGA2 MOEAD ANSGA2-DS NSGA2 MOEAD A 135268.1 136414.04 138989.7 149832 154586 157940 14.23 19.38 23.71 1.18 1.36 1.58 B 253142.78 254551.42 255670.78 259467 262036 265789 5.61 7.05 8.33 2.83 2.91 2.98 C 531868.44 536551.42 540642.78 436982 442036 457467 4.36 5.82 7.12 6.48 6.70 7.42
下载: 导出CSV
-
[1] 何坚, 果红艳, 姚远, 等. 基于有效中转时间预测的不正常航班恢复技术[J]. 北京航空航天大学学报, 2022, 48(3): 384-393.HE J, GUO H Y, YAO Y, et al. Irregular flight recovery technique based on accurate transit time prediction[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(3): 384-393(in Chinese). [2] MANYEM P. Disruption recovery at airports: Ground holding, curfew restrictions and an approximation algorithm[J]. Journal of the Operations Research Society of China, 2021, 9(4): 819-852. doi: 10.1007/s40305-020-00338-1 [3] SU Y, XIE K X, WANG H J, et al. Airline disruption management: A review of models and solution methods[J]. Engineering, 2021, 7(4): 435-447. doi: 10.1016/j.eng.2020.08.021 [4] MANYEM P. Disruption recovery at airports: Integer programming formulations and polynomial time algorithms[J]. Discrete Applied Mathematics, 2018, 242: 102-117. doi: 10.1016/j.dam.2017.11.010 [5] EVLER J, ASADI E, PREIS H, et al. Airline ground operations: Optimal schedule recovery with uncertain arrival times[J]. Journal of Air Transport Management, 2021, 92: 102021. doi: 10.1016/j.jairtraman.2021.102021 [6] LEE J, MARLA L, JACQUILLAT A. Dynamic disruption management in airline networks under airport operating uncertainty[J]. Transportation Science, 2020, 54(4): 973-997. doi: 10.1287/trsc.2020.0983 [7] MCCARTY L A, COHN A E M. Preemptive rerouting of airline passengers under uncertain delays[J]. Computers & Operations Research, 2018, 90: 1-11. [8] XU Y, PRATS X. Linear holding for airspace flow programs: A case study on delay absorption and recovery[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(3): 1042-1051. doi: 10.1109/TITS.2018.2842918 [9] LIU T K, CHEN C H, CHOU J H. Optimization of short-haul aircraft schedule recovery problems using a hybrid multiobjective genetic algorithm[J]. Expert Systems with Applications, 2010, 37(3): 2307-2315. doi: 10.1016/j.eswa.2009.07.068 [10] JI C L, GAO M G, ZHANG X, et al. A novel rescheduling algorithm for the airline recovery with flight priorities and airport capacity constraints[J]. Asia-Pacific Journal of Operational Research, 2021, 38(5): 328-340. [11] HU Y Z, LIAO H, ZHANG S, et al. Multiple objective solution approaches for aircraft rerouting under the disruption of multi-aircraft[J]. Expert Systems with Applications, 2017, 83: 283-299. [12] SHAO Q, SHAO M X, BIN Y P, et al. Flight recovery method of regional multiairport based on risk control model[J]. Mathematical Problems in Engineering, 2020, 2020: 7105381. [13] 田文, 杨帆, 尹嘉男, 等. 航路时空资源分配的多目标优化方法[J]. 交通运输工程学报, 2020, 20(6): 218-226.TIAN W, YANG F, YIN J N, et al. Multi-objective optimization method of air route space-time resources allocation[J]. Journal of Traffic and Transportation Engineering, 2020, 20(6): 218-226(in Chinese). [14] SANTOS B F, WORMER M M E C, ACHOLA T A O, et al. Airline delay management problem with airport capacity constraints and priority decisions[J]. Journal of Air Transport Management, 2017, 63: 34-44. [15] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017 [16] 赖文星, 邓忠民. 基于支配强度的NSGA2改进算法[J]. 计算机科学, 2018, 45(6): 187-192.LAI W X, DENG Z M. Improved NSGA2 algorithm based on dominant strength[J]. Computer Science, 2018, 45(6): 187-192(in Chinese). [17] 蔡卓森, 戴凌全, 刘海波, 等. 基于支配强度的NSGA-Ⅱ改进算法在水库多目标优化调度中的应用[J]. 武汉大学学报(工学版), 2021, 54(11): 999-1007.CAI Z S, DAI L Q, LIU H B, et al. Application of improved NSGA-Ⅱ algorithm based on dominance strength in multi-objective operation of cascade reservoirs[J]. Engineering Journal of Wuhan University, 2021, 54(11): 999-1007(in Chinese). [18] ZOGRAFOS K G, JIANG Y. A bi-objective efficiency-fairness model for scheduling slots at congested airports[J]. Transportation Research Part C:Emerging Technologies, 2019, 102: 336-350. doi: 10.1016/j.trc.2019.01.023 [19] FIGUEIREDO E M N, LUDERMIR T B, BASTOS-FILHO C J A. Many objective particle swarm optimization[J]. Information Sciences, 2016, 374: 115-134. doi: 10.1016/j.ins.2016.09.026 [20] MONTGOMERY D C. Design and analysis of experiments[M]. New York: John Wiley & Sons, 2020. [21] BACH L, HASLE G, WØHLK S. A lower bound for the node, edge, and arc routing problem[J]. Computers & Operations Research, 2013, 40(4): 943-952. [22] ZHANG Q F, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. -
下载:
点击查看大图
计量
- 文章访问数: 443
- HTML全文浏览量: 100
- PDF下载量: 28
- 被引次数: 0
