Stochastic airport gate assignment problem

Official URL: http://192.168.1.20/record=b1305902

The uncertainties inherent in the airport flight arrival and departure traffic may lead to the unavailability of gates when needed to accommodate 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 flight-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 confficting flights, the buffer and idle times as robustness measures. Minimizing the expected variance of idle times or the expected semi-deviation of idle times from a 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 confficts. 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 computational effectiveness of the proposed solution methods.