Stochastic optimization models for the airport gate assignment problem

The uncertainties inherent in the airport flight arrival and departure traffic may lead to the unavailability of gates for accommodating the scheduled flights. Mechanical failures, severe weather conditions, heavy traffic volume at the airport are some typical causes of the uncertainties in the input data. Incorporating such random disruptions is crucial in constructing effective flight-gate assignment plans. We consider the gate assignment problem in the presence of uncertainty in arrival and departure times of the flights and represent the randomness associated with these uncertain parameters by a finite set of scenarios. Using the scenario-based approach, we develop new stochastic programming models incorporating alternate robustness measures to obtain assignments that would perform well under potential random disruptions. In particular, we focus on the number of conflicting flights, the idle and buffer times as robustness measures. Minimizing the expected variance of idle times or the expected total semi-deviation of idle times from a specified buffer time value are some examples of the objectives that we incorporate in our models to appropriately distribute the idle times among gates, and by this way, to decrease the number of potential flight conflicts. The proposed stochastic optimization models are formulated as computationally expensive large-scale mixed-integer programming problems, which are hard to solve. In order to find good feasible solutions in reasonably short CPU times, we employ tabu search algorithms. We conduct an extensive computational study to analyze the proposed alternate formulations and show the effectiveness of the proposed solution methods.