A new mathematical model for gate assignment problem considering transit passengers and safety constraints: Benders decomposition approach

Subject Areas : Mathematical Optimization

Alireza Rashidi Komijan ¹ , Fatemeh Nasrollahpourniazi ²

1 - Department of Industrial Engineering, Firoozkooh Branch, Islamic Azad University, Firoozkooh, Iran
2 - Department of Industrial Engineering, Faculty of Mechanical Engineering, Universiti Teknologi Malaysia, 81310 Skudai, Johor, Malaysia

Received: 2020-12-13 Accepted : 2021-01-09 Published : 2020-12-01

Keywords: Benders decomposition, Mixed Integer Programming (MIP), Gate Assignment Problem (GAP),

Abstract :

Inappropriate gate assignment has some consequences such as flight delays, inefficient usage of resources and customer’s dissatisfaction. Airports are service sectors and provide services to their customers. Passengers and airlines are two main customers of an airport. Current research presents a novel mathematical model for gate assignment problem to minimize customers’ dissatisfaction. In other words, passengers walking time as well as flight delays are minimized in as objective function. In this model, transit and non-transit passengers and also arrival and departure flights are considered. Moreover, operational safety constraints are inserted to avoid collision of large aircraft. The proposed model is solved by Benders decomposition approach. The model is applied in San Francisco International Airport for a 24-hour horizon. The result shows that walking time of non-transit passengers, walking time of transit passengers, delay in departure flights and delay in arrivals include 74.55, 23.32, 0.96 and 1.17 percent of the objective function, respectively.

References:

[1] Guclu, O. E., & Cetek, C. (2017). Analysis of aircraft ground traffic flow and gate utilisation using a hybrid dynamic gate and taxiway assignment algorithm. The Aeronautical Journal, 121(1240), 721-745.

[2] Barnhart, C. and Talluri, K.T. (1997). Airline operations research in design and operation of civil and environmental engineering system, in C. Revelle and A. McGarity. Wiley, 435–69.

[3] Bazargan, M. (2016). Airline operations and scheduling. Routledge.

[4] Prem Kumar, V., & Bierlaire, M. (2014). Multi-objective airport gate assignment problem in planning and operations. Journal of advanced transportation, 48(7), 902-926.

[5] Bertsimas, D., & Frankovich, M. (2015). Unified optimization of traffic flows through airports. Transportation Science, 50(1), 77-93.

[6] Deng, W., Li, B., & Zhao, H. (2017). Study on an airport gate reassignment method and its application. Symmetry, 9(11), 258.

[7] Kim, S. H., & Feron, E. (2012, October). Impact of gate assignment on gate-holding departure control strategies. In 2012 IEEE/AIAA 31st Digital Avionics Systems Conference (DASC) (pp.4E3-1). IEEE.
[8] Liu, S., Chen, W. H., & Liu, J. (2016). Robust assignment of airport gates with operational safety constraints. International ournal of Automation and Computing, 13(1), 31-41.
[9] Bolat, A. (1999). Assigning arriving flights at an airport to the available gates. Journal of the Operational Research Society, 50(1), 23-34.
[10] Bolat, A. (2000). Procedures for providing robust gate assignments for arriving aircrafts. European Journal of Operational Research, 120(1), 63-80.
[11] Bolat, A. (2001). Models and a genetic algorithm for static aircraft-gate assignment problem. Journal of the Operational Research Society, 52(10), 1107-1120.
[12] Cheng, C. H., Ho, S. C., & Kwan, C. L. (2012). The use of meta-heuristics for airport gate assignment. Expert systems with applications, 39(16), 12430-12437.
[13] Dorndorf, U., Drexl, A., Nikulin, Y., & Pesch, E. (2007). Flight gate scheduling: State-of-the-art and recent developments. Omega, 35(3), 326-334.
[14] Xu, J., & Bailey, G. (2001, January). The airport gate assignment problem: mathematical model and a tabu search algorithm. In Proceedings of the 34th annual Hawaii international conference on system sciences (pp. 10-pp). IEEE
[15] Pintea, C. M., Pop, P. C., Chira, C., & Dumitrescu, D. (2008,September). A hybrid ant-based  system for gate assignment problem. In International Workshop on Hybrid Artificial Intelligence Systems (pp. 273-280). Springer, Berlin, Heidelberg.
[16] Genç, H. M., Erol, O. K., Eksin, İ., Berber, M. F., & Güleryüz, B. O. (2012). A stochastic neighborhood search approach for airport gate assignment problem. Expert Systems with Applications, 39(1), 316-327.
[17] Behrends, J. A., & Usher, J. M. (2016). Aircraft gate assignment: using a deterministic approach for integrating freight movement and aircraft taxiing. Computers & Industrial Engineering, 102, 44-57.
[18] Yu, C., Zhang, D., & Lau, H. H. (2017). A heuristic approach for solving an integrated gate reassignment and taxi scheduling problem. Journal of Air Transport Management, 62, 189-196.
[19] Deng, W., Xu, J., & Zhao, H. (2019). An improved ant colony optimization algorithm based on hybrid strategies for scheduling problem. IEEE access, 7, 20281-20292.
[20] Kim, S. H., & Feron, E. (2017). Robust Gate Assignment Against Gate Conflicts. Journal of Air Transportation, 87-94.
[21] Van Schaijk, O. R., & Visser, H. G. (2017). Robust flight-to- gate assignment using flight presence probabilities. Transportation Planning and Technology, 40(8), 928-945.
[22] Zhang, H. H., Xue, Q. W., & Jiang, Y. (2017). Multi-objective gate assignment based on robustness in hub airports. Advances in Mechanical Engineering, 9(2), 1687814016688588.
[23] Millar H. & Zhang J., (2012). A Network-Based Model for Assigning Flights to Gates at Airports Article.

[24] Phong, H. T., & Van Hai, N. (2016) OPTIMAL SCHEDULING OF AIRPORT’S RUNWAY OPERATIONS A CASE STUDY IN TAN SON NHAT INTERNATIONAL AIRPORT.
[25] Ornek, M. A., Ozturk, C., & Sugut, I. (2019). Model-based heuristic for counter assignment problem with operational constrains: A case study. Jo rnal of Air Transport Management, 77,
57-64.
[26] Behrends, J., & Usher, J. M. (2017). An integrated solution for the taxi and gate assignment problems. Cogent Engineering, 4(1), 1413722.
[27] Li, W., & Xu, X. (2012). Optimized assignment of airport gate configuration based on immune genetic algorithm. In Measuring echnology and Mechatronics Automation in Electrical Engineering (pp. 347-355). Springer, New York, NY.
[28] Şeker, M., & Noyan, N. (2012). Stochastic optimization models for the airport gate assignment problem. Transportation Research Part E: Logistics and Transportation Review, 48(2), 438- 459.
[29] Maharjan, B., & Matis, T. I. (2012). Multi-commodity flow network model of the flight gate assignment problem. Computers & Industrial Engineering, 63(4), 1135-1144.
[30] Aktel, A., Yagmahan, B., Özcan, T., Yenisey, M. M., & Sansarcı, E. (2017). The comparison of the metaheuristic algorithms performances on airport gate assignment problem. Transportation research procedia, 22, 469-478.
[31] Azmi, K. M., Yusof, Z. M., Satiman, S. N., Muhammad, B., Razali, S., Ibrahim, Z., & Aziz, N. A. (2016, September). Solving airport gate allocation problem using angle modulated simulated
Kalman filter. In The National Conference for Postgraduate Research (pp. 875-885).
[32] Deng, W., Sun, M., Zhao, H., Li, B., & Wang, C. (2018). Study on an airport gate assignment method based on improved ACO algorithm. Kybernetes, 47(1), 20-43.
[33] Genc, H. M., Erol, O. K., Eksin, I., & Okutan, C. C. (2016). Enhanced Order Based Single Leap Big Bang-Big Crunch Optimization Approach to Multi-Objective Gate Assignment Problem. Journal of Multiple-Valued Logic & Soft Computing, 26.
[34] Khakzar B. M. et al. (2018). A Bi-Objective Airport Gate Scheduling with Controllable Processing Times Using Harmony Search and NSGA-II Algorithms. Journal of Optimization in Industrial Engineering, 11(1), 77-90.
[35] Pternea, M., & Haghani, A. (2019). An aircraft-to-gate reassignment framework for dealing with schedule disruptions. Journal of Air Transport Management, 78, 116-132.
[36] Pternea, M., & Haghani, A. (2018). Mathematical models for flight-to-gate reassignment with passenger flows: State-of-the-art comparative analysis, formulation improvement, and a new multidimensional assignment model. Computers & Industrial Engineering, 123, 103-118.
[37] Dijk, B., Santos, B. F., & Pita, J. P. (2018). The recoverable robust stand allocation problem: a GRU airport case study. OR Spectrum, 1-25.
[38] Marinelli, M., Palmisano, G., Dell’Orco, M., & Ottomanelli, M. (2016). Optimizing Airport Gate Assignments Through a Hybrid Metaheuristic Approach. In Advanced Concepts, Methodologies and Technologies for Transportation and Logistics (pp. 389-404). Springer, Cham.
[39] Nik, A., Sadegh, M., Ansarifar, J., & Akhavizadegan, F. (2016). Benders’ decompositionalgorithm to solve bi-level bi- objective scheduling of aircrafts and gate assignment under uncertainty. Journal of Industrial and Systems Engineering, 9(3), 111-126.
[40] Stollenwerk, T., Lobe, E., & Jung, M. (2019, March). Flight gate assignment with a quantum annealer. In International Workshop on Quantum Technology and Optimization Problems (pp. 99-110). Springer, Cham.
[41] Sun, W., Cai, X., Xia, C., Sulaman, M., Mısır, M., & Fan, Z. (2017, November). Greedy Based  Pareto Local Search for Bi-objective Robust Airport Gate Assignment Problem. In Asia-Pacific Conference on Simulated Evolution and Learning (pp. 694-705). Springer, Cham.
[42] Drexl, A., & Nikulin, Y. (2008). Multicriteria airport gate assignment and Pareto simulated annealing. IIE Transactions, 40(4), 385-397.
[43] Wei, D. X., & Liu, C. Y. (2009, November). Fuzzy model and optimization for airport gate assignment problem. In 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems (Vol. 2, pp. 828-832). IEEE.
[44] Jiang, Y., Zeng, L., & Luo, Y. (2013). Multiobjective gate assignment based on passenger walking distance and fairness. Mathematical Problems in Engineering.

[45] Hu, X. B., & Di Paolo, E. (2009). An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem. In Multi-objective memetic algorithms(pp. 71-89). Springer, Berlin, Heidelberg.