|Table of Contents|

Multi-objective optimization of flight-gate assignment based on improved genetic algorithm(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2020年02期
Page:
121-130
Research Field:
交通运输规划与管理
Publishing date:

Info

Title:
Multi-objective optimization of flight-gate assignment based on improved genetic algorithm
Author(s):
YU Chao-jun1;  JIANG Ju1;  XU Hai-yan2;  ZHU Ping1
(1. College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, Jiangsu, China; 2. College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, Jiangsu, China)
Keywords:
traffic planning;  large scale optimization problem;  flight-gate assignment;  genetic algorithm;  genetic code;  multi-objective optimization
PACS:
V351.1
DOI:
10.19818/j.cnki.1671-1637.2020.02.010
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. 4 tabs, 9 figs, 33 refs.

References:

[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.
[2] DAG 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.
WANG 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)
[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.
[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.
[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.
[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.
[9] 陈 欣,陆 迅,朱金福.机场停机位指派模型及算法[J].交通运输工程学报,2006,6(4):88-90.
CHEN 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)
[10] 尹嘉男,胡明华,赵 征.多跑道机场停机位分配仿真模型及算法[J].交通运输工程学报,2010,10(5):71-76.
YIN 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)
[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.
[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.
[14] 王志清,商红岩,宁宣熙.机场登机口优化调度算法及实证[J].南京航空航天大学学报,2007,39(6):819-823.
WANG 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)
[15] 刘君强,张马兰,陈鹏超,等.基于协同决策的多航站楼停机位实时分配算法[J].南京航空航天大学学报,2015,47(1):71-76.
LIU 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)
[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.
[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.
[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.
[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.
[20] NARCISO M E, PIERA M A. Robust gate assignment
procedures from an airport management perspective[J]. Omega, 2015, 50: 82-95.
[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.
[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.
[24] DAG S. New multi objective models for the gate assignment problem[J]. Computers and Industrial Engineering, 2017, 109: 347-356.
[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.
[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.

Memo

Memo:
-
Last Update: 2020-05-22