An improved variable neighbourhood search for the gate assignment problem with time windows

With the escalating volume of air traffic, the complexity of airport ground operations intensifies, particularly in bustling hubs. This study addresses the gate assignment problem with time windows (GAPTW) to optimize the scheduling of flight operations near the terminal area (including arrival, parking, and departure). Unlike conventional approaches that treat the operations with fixed start and finish times in traditional gate assignment problem (GAP), the proposed GAPTW accommodates the stochastic nature of start and finish times of operations influenced by uncertainties such as weather and maintenance and introduces the time variables. To address this novel problem, we establish a mathematical model to minimise the total cost, including the arrival and departure operation cost, the delay cost, and the tow cost. This model augments the adaptability of the airport system, bolstering resilience against uncertainties and mitigating the need for expensive reassignment. Additionally, this study proposes a novel meta-heuristic algorithm based on variable neighborhood search (VNS), i.e., improved variable neighborhood search (IVNS), tailored to tackle the challenges posed by time decisions. Compared with the VNS, the shaking procedure in IVNS is divided into small-scale and large-scale shaking, aiming to diversify exploration during the search process. Computational experiments demonstrate the superior performance of IVNS in solving both small-scale and large-scale instances. This research lays the groundwork for advancing the efficiency and resilience of airport ground operations in uncertain environments.