Multi-objective optimization of flight-gate assignment based on improved genetic algorithm
Article Text (Baidu Translation)
-
摘要: 为提高现代机场的资源利用效率和乘客换乘体验, 研究了多目标航班-登机口分配问题; 在考虑航班类型约束、飞机机体类型约束和转场时间间隔约束的基础上, 以分配在固定登机口的航班数量最多、使用的固定登机口数量最少和乘客换乘紧张度最小为目标函数, 建立了航班-登机口分配的多目标非线性0-1整数规划模型, 并设计了一种改进型基因编码的遗传算法以提高求解效率; 基因个体采用两段式整数编码, 设计了该编码方式到可行解的映射流程, 同时从理论上证明该编码方式可以映射到最优解; 对两段基因编码分别设计了不同的交叉算子和变异算子, 避免产生非可行个体; 为验证算法的有效性, 基于某大规模机场的实际运营数据, 对比了改进型遗传算法与MATLAB内置遗传算法。计算结果表明: 采用改进型遗传算法使得安排在固定登机口的航班数目增大5%, 乘客换乘总紧张度减小3%, 乘客换乘平均紧张度减小32%, 占用的固定登机口数量相同, 安排在固定登机口的乘客数量增大20%, 算法运行时间减小8%, 说明改进型遗传算法性能更好, 可提高登机口的利用效率和乘客的换乘舒适度; 在改进型遗传算法的优化过程中, 航班数量目标和登机口数量目标在130次迭代时寻到最优解, 换乘紧张度目标在400次迭后基本收敛, 且最优结果对应的航班时序合理, 说明该算法的迭代收敛速度快, 优化结果合理。Abstract: In order to improve the resource utilization efficiency and passenger transfer experience of modern airports, the multi-objective flight-gate assignment problem was studied. Considering the constraints of flight type, aircraft body type and transition time interval, a multi-objective nonlinear 0-1 integer planning model of the flight-gate assignment was established by taking the maximum number of flights allocated at a fixed gate, the minimum number of used fixed gates and the minimum passenger transfer tension as the objective functions. Then a genetic algorithm based on the improved gene coding was designed to improve the solving efficiency of the model. The gene individual adopts two-stage integer coding, and the mapping process from the gene coding method to a feasible solution was designed. Meanwhile, it was theoretically proved that the gene coding method could be mapped to the optimal solution. Different crossover operators and mutation operators were designed for the two stages of gene coding to avoid infeasible individuals. In order to verify the effectiveness of the algorithm, based on the actual operation data of a large-scale airport, the improved genetic algorithm and MATLAB built-in genetic algorithm were compared. Calculation result shows that with the improved genetic algorithm, the number of flights assigned to the fixed gates increases by 5%, the total transfer tension of passenger decreases by 3%, the average transfer tension of passenger decreases by 32%, the number of used fixed gates stays the same, the passengers assigned to the fixed gates increase by 20%, and the running time of the algorithm reduces by 8%, which shows that the improved genetic algorithm has better performance and can improve the gate utilization efficiency and passenger transfer comfort. In the optimization process of the improved genetic algorithm, the number objectives of flights and gates reach the best in 130 iterations, the transfer tension basically converges after 400 iterations, and the flight schedule generated by the optimal solution is reasonable, which indicates that the algorithm has fast iterative convergence speed and reasonable optimization result.
-
表 1 飞机转场信息
Table 1. Aircraft transition information
飞机转场编号 到达日期 到达时刻 到达航班 到达类型 飞机型号 出发日期 出发时刻 出发航班 出发类型 上线机场代码 下线机场代码 178 03月19日 22:10 GN945 国际 73H 03月20日 9:40 GN0476 国内 CLL ZJI 
下载: 导出CSV
表 2 旅客信息
Table 2. Passenger information
旅客编号 乘客数 到达航班 到达日期 出发航班 出发日期 27 2 NV677 03月19日 NV6514 03月19日
下载: 导出CSV
表 4 两种遗传算法的运行结果
Table 4. Computational results of two genetic algorithms
算法 最优个体的适应度 总航班数 总紧张度 平均紧张度 占用的总登机口数 安排在固定登机口的乘客数 运行时间/s 改进型GA 1.843×104 268 1.091×103 0.404 66 2 460 518.02 MATLAB内置GA 1.753×104 255 1.608×103 0.595 66 2 051 560.57
下载: 导出CSV
-
[1] DORNDORF U, DREXL A, NIKULIN Y, et al. Flight gate scheduling: state-of-the-art and recent developments[J]. Omega, 2007, 35(3): 326-334. doi: 10.1016/j.omega.2005.07.001 [2] DAŞG S, GZARA F, STÜTZLE T. A review on airport gate assignment problems: single versus multi objective approaches[J]. Omega, 2020, 92: 1-35. [3] 王永亮, 王春凤. 基于乘客交通特性和交叉熵的机位预分配研究[J]. 交通运输系统工程与信息, 2016, 16(4): 211-216. doi: 10.3969/j.issn.1009-6744.2016.04.031WANG Yong-liang, WANG Chun-feng. Aircraft stands pre-assignment based on passenger traffic characteristics and cross entropy[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(4): 211-216. (in Chinese). doi: 10.3969/j.issn.1009-6744.2016.04.031 [4] LIU Shuo, CHEN Wen-hua, LIU Jin-ying. Robust assignment of airport gates with operational safety constraints[J]. International Journal of Automation and Computing, 2016, 13(1): 31-41. doi: 10.1007/s11633-015-0914-x [5] VAN SCHAIJKO R P, VISSER H G. Robust flight-to-gate assignment using flight presence probabilities[J]. Transportation Planning and Technology, 2017, 40(8): 928-945. doi: 10.1080/03081060.2017.1355887 [6] KIM S H, FERON E. Impact of gate assignment on departure metering[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(2): 699-709. doi: 10.1109/TITS.2013.2285499 [7] LIU Shuo, CHEN Wen-hua, LIU JI-yin. Optimizing airport gate assignment with operational safety constraints[C]//IEEE. Proceedings of the 20th International Conference on Automation and Computing: Future Automation, Computing and Manufacturing. New York: IEEE, 2014: 61-66. [8] DING H, LIM A, RODRIGUES B, et al. New heuristics for over-constrained flight to gate assignments[J]. Journal of the Operational Research Society, 2004, 55(7): 760-768. doi: 10.1057/palgrave.jors.2601736 [9] 陈欣, 陆迅, 朱金福. 机场停机位指派模型及算法[J]. 交通运输工程学报, 2006, 6(4): 88-90. doi: 10.3321/j.issn:1671-1637.2006.04.020CHEN Xin, LU Xun, ZHU Jin-fu. Model and algorithm for airport gate assignment problem[J]. Journal of Traffic and Transportation Engineering, 2006, 6(4): 88-90. (in Chinese). doi: 10.3321/j.issn:1671-1637.2006.04.020 [10] 尹嘉男, 胡明华, 赵征. 多跑道机场停机位分配仿真模型及算法[J]. 交通运输工程学报, 2010, 10(5): 71-76. doi: 10.3969/j.issn.1671-1637.2010.05.013YIN Jia-nan, HU Ming-hua, ZHAO Zheng. Simulation model and algorithm of multi-runway airport gate assignment[J]. Journal of Traffic and Transportation Engineering, 2010, 10(5): 71-76. (in Chinese). doi: 10.3969/j.issn.1671-1637.2010.05.013 [11] XU Liang, ZHANG Chao, XIAO Feng, et al. A robust approach to airport gate assignment with a solution-dependent uncertainty budget[J]. Transportation Research Part B: Methodological, 2017, 105: 458-478. doi: 10.1016/j.trb.2017.09.013 [12] GHAZOUANI H, HAMMAMI M, KORBAA O. Solving airport gate assignment problem using genetic algorithms approach[C]//IEEE. 4th International Conference on Advanced Logistics and Transport (ICALT). New York: IEEE, 2015: 175-180. [13] GENÇ H M, EROL O K, EKSIN B, et al. A stochastic neighborhood search approach for airport gate assignment problem[J]. Expert Systems with Applications, 2012, 39(1): 316-327. doi: 10.1016/j.eswa.2011.07.021 [14] 王志清, 商红岩, 宁宣熙. 机场登机口优化调度算法及实证[J]. 南京航空航天大学学报, 2007, 39(6): 819-823. doi: 10.3969/j.issn.1005-2615.2007.06.026WANG Zhi-qing, SHANG Hong-yan, NING Xuan-xi. Assignment algorithm for airport gate and its application[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2007, 39(6): 819-823. (in Chinese). doi: 10.3969/j.issn.1005-2615.2007.06.026 [15] 刘君强, 张马兰, 陈鹏超, 等. 基于协同决策的多航站楼停机位实时分配算法[J]. 南京航空航天大学学报, 2015, 47(1): 71-76. https://www.cnki.com.cn/Article/CJFDTOTAL-NJHK201501010.htmLIU Jun-qiang, ZHANG Ma-lan, CHEN Peng-chao, et al. Real-time gate assignment algorithm of multi-terminal based on collaborative decision-making mechanism[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2015, 47(1): 71-76. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NJHK201501010.htm [16] PTERNEA M, HAGHANI A. Mathematical models for flight-to-gate reassignment with passenger flows: state-of-the-art comparative analysis, formulation improvement, and a new multidimensional assignment model[J]. Computers and Industrial Engineering, 2018, 123: 103-118. doi: 10.1016/j.cie.2018.05.038 [17] CHENG C H, HO S C, KWAN C L. The use of meta-heuristics for airport gate assignment[J]. Expert Systems with Applications, 2012, 39(16): 12430-12437. doi: 10.1016/j.eswa.2012.04.071 [18] DENG Wu, SUN Meng, ZHAO Hui-min, et al. Study on an airport gate assignment method based on improved ACO algorithm[J]. Kybernetes, 2018, 47(1): 20-43. doi: 10.1108/K-08-2017-0279 [19] PTERNEA M, HAGHANI A. An aircraft-to-gate reassignment framework for dealing with schedule disruptions[J]. Journal of Air Transport Management, 2019, 78: 116-132. doi: 10.1016/j.jairtraman.2019.01.005 [20] NARCISO M E, PIERA M A. Robust gate assignment procedures from an airport management perspective[J]. Omega, 2015, 50: 82-95. doi: 10.1016/j.omega.2014.06.003 [21] YAN Shang-yao, HUO Cheun-ming. Optimization of multiple objective gate assignments[J]. Transportation Research Part A: Policy and Practice, 2001, 35(5): 413-432. doi: 10.1016/S0965-8564(99)00065-8 [22] WEI Dong-xuan, LIU Chang-you. Fuzzy model and optimization for airport gate assignment problem[C]//IEEE. 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems. New York: IEEE, 2009: 828-832. [23] DENG Wu, ZHAO Hui-min, YANG Xin-hua, et al. Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment[J]. Applied Soft Computing, 2017, 59: 288-302. doi: 10.1016/j.asoc.2017.06.004 [24] DAŞ G S. New multi objective models for the gate assignment problem[J]. Computers and Industrial Engineering, 2017, 109: 347-356. doi: 10.1016/j.cie.2017.04.042 [25] BENLIC U, BURKE E K, WOODWARD J R. Breakout local search for the multi-objective gate allocation problem[J]. Computers and Operations Research, 2017, 78: 80-93. doi: 10.1016/j.cor.2016.08.010 [26] BEHRENDS J A, USHER J M. Aircraft gate assignment: using a deterministic approach for integrating freight movement and aircraft taxiing[J]. Computers and Industrial Engineering, 2016, 102: 44-57. [27] YU Chu-hang, ZHANG Dong, LAU H Y K. An adaptive large neighborhood search heuristic for solving a robust gate assignment problem[J]. Expert Systems with Applications, 2017, 84: 143-154. [28] DORNDORF U, JAEHN F, PESCH E. Flight gate assignment and recovery strategies with stochastic arrival and departure times[J]. OR Spectrum, 2017, 39: 65-93. [29] ZHANG Dong, KLABJAN D. Optimization for gate re-assignment[J]. Transportation Research Part B: Methodological, 2017, 95: 260-284. [30] DELL'ORCO M, MARINELLI M, ALTIERI M G. Solving the gate assignment problem through the fuzzy bee colony optimization[J]. Transportation Research Part C: Emerging Technologies, 2017, 80: 424-438. [31] MAHARJAN B, MATIS T I. Multi-commodity flow network model of the flight gate assignment problem[J]. Computers and Industrial Engineering, 2012, 63(4): 1135-1144. [32] GUÉPET J, ACUNA-AGOST R, BRIANT O, et al. Exact and heuristic approaches to the airport stand allocation problem[J]. European Journal of Operational Research, 2015, 246(2): 597-608. [33] YU Chu-hang, ZHANG Dong, LAU H Y K. MIP-based heuristics for solving robust gate assignment problems[J]. Computers and Industrial Engineering, 2016, 93: 171-191. -
点击查看大图
图(9) / 表(4)
计量
- 文章访问数: 1690
- HTML全文浏览量: 463
- PDF下载量: 519
- 被引次数: 0
