(An) optimization algorithm for a robust airport gate assignment problem

Abstract

This thesis considers Airport Gate Assignment Problem (AGAP) which is finding an effective gate schedule while satisfying passengers walking distance, space restriction and ground time conditions. The objective of this problem is finding a robust solution which is quite insensitive to variation in flight schedule. Even though the idle time between two consecutive flights is assumed to be uncertain, a solution can be accomplished by the robust combinatorial optimization. We formulate this problem as an integer linear program (ILP) using variables corresponding to flight series which can be assigned to a certain gate. To solve the problem, we develop a branch and price algorithm where an efficient branching rule is adopted. Furthermore, we stabilize the column generation to accelerate a convergence. The pricing problem is solved easily by composing networks for each gate separately. To test the performance of the algorithm, we have tested the algorithm with real flights and gates data provided by Incheon International Airport. Computational results are reported.