Volume 20 Issue 2
. 
Turn off MathJax
Article Contents
Article Navigation >  Journal of Traffic and Transportation Engineering  > 2020  >  20(2): 121-130
Next Previous
YU Chao-jun, JIANG Ju, XU Hai-yan, ZHU Ping. Multi-objective optimization of flight-gate assignment based on improved genetic algorithm[J]. Journal of Traffic and Transportation Engineering, 2020, 20(2): 121-130. doi: 10.19818/j.cnki.1671-1637.2020.02.010
Citation: YU Chao-jun, JIANG Ju, XU Hai-yan, ZHU Ping. Multi-objective optimization of flight-gate assignment based on improved genetic algorithm[J]. Journal of Traffic and Transportation Engineering, 2020, 20(2): 121-130. doi: 10.19818/j.cnki.1671-1637.2020.02.010
shu

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

doi: 10.19818/j.cnki.1671-1637.2020.02.010
  • 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

Funds:

National Natural Science Foundation of China 61673209

Research Innovation Program for Graduates of Jiangsu Province KYCX19_0193

More Information
  • Author Bio:

    YUChao-jun(1994-), male, doctoralstudent, E-mail: ycjun@nuaa.edu.cn

    JIANGJu(1963-), male, professor, PhD, E-mail: jiangju@nuaa.edu.cn

  • Received Date: 2019-10-22
  • Publish Date: 2020-04-25
    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.

     

    • FullText(HTML)
  • loading
    • References(33)
  • [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]
    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). 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]
    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). doi: 10.3321/j.issn:1671-1637.2006.04.020
    [10]
    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). 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]
    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). doi: 10.3969/j.issn.1005-2615.2007.06.026
    [15]
    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). http://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.
    • Relative Articles
    • Supplements(0)
    • Cited By

Catalog

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (3845) PDF downloads(604) Cited by()
    Related

    Website copyright Journal of Traffic and Transportation Engineering Editorial Department陕ICP备05001904号-1

    Address ：Editorial Department of Journal of Traffic and Transportation Engineering, Chang'an University, Middle Section of South 2nd Ring Road, Xi'an, China（710064） Tel：029-82334388 Email：jygc@gfscw.cn

    All visit:Today's visit:

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return