Finding a robust assignment of flights to gates at Amsterdam Airport Schiphol

摘要

In this paper we investigate the gate assignment problem as it appears at Amsterdam Airport Schiphol (AAS). Currently, the gate planners spend many hours on adjusting the automatically generated planning during the day of operation to make it proof against small deviations from the schedule. To alleviate this problem, we aim at finding a robust solution, given the planned arrivals and departures for the next day. We present a completely new integer linear programming formulation that is based on so-called gate plans. Each gate plan consists of a subset of the flights that can be assigned to a single gate of the corresponding type; gates with identical characteristics are aggregated in gate types. The gate assignment problem then boils down to selecting the best subset of gate plans such that each flight belongs to one selected gate plan, and such that the number of selected gate plans for a certain type of gate is equal to the number of gates of this type. In the first phase, we solve the LP-relaxation through column generation, and we describe specific features to find a very good solution to the ILP quickly. This solution is then handed to the planners at AAS in order to assign gate plans to physical gates. This consists of a number of relatively small problems that can be solved by hand and in which additional operational constraints can be incorporated. We also present the possibility of directly assigning flights to physical gates using the column generation formulation, where we then take into account other criteria as well. Computational results with real-life data provided by AAS are promising and indicate that the algorithm is able to solve real-life instances within rather small running times.