Q-learning-driven exact and meta-heuristic algorithms for the robust gate assignment problem

Abstract

Given the growing demand for air transport, many airports have surpassed their available capacity, leading to more frequent congestion and disruptions. Consequently, airport gate assignment plans must prioritise robustness to absorb disturbances, ensuring the maintenance of a high service level. Providing robust gate assignment decisions under uncertainty is a challenging task. To address this issue, we propose a robust optimisation (RO) model for the robust gate assignment problem (RGAP) that considers uncertain idle time and includes a budget to control conservatism. The model considers two decision stages, where the first-stage decision assigns aircraft to either contact gates or the apron, while the second-stage decision designs aircraft scheduling plans based on observed aircraft idle times. Our model aims to minimise the number of aircraft assigned to the apron while reducing the deviation between aircraft idle and buffer times. By achieving this balance, we enhance service levels while addressing gate conflicts and avoiding underutilisation of gates. We develop exact and meta-heuristic algorithms to solve the RGAP: an exact Benders decomposition algorithm with a Q-learning-driven Pareto-optimal cuts generation method; and a Q-learning-driven variable neighbourhood search algorithm with the operators selected by the Q-learning method. We evaluate the computational performance of these solution approaches and find that they outperform well-known benchmark algorithms in the literature. Our research demonstrates the effectiveness of Q-learning-driven algorithms in solving the RO model for RGAP. A case study utilising real-world data from Xiamen Gaoqi International Airport highlights the effectiveness and robustness of the RO model, demonstrating its superior performance over the deterministic model under worst-case and expected scenarios.