A column generation algorithm for robust gate assignment problems

Official URL: http://192.168.1.20/record=b1416926 (Table of Contents)

This study adresses the Robust Gate Assignment Problem (RGAP) for the case of both homogeneous and heterogeneous gates. Due to the increased traffic and congestion at airports, scientific approaches to operational problems have gained importance in the airline industry. Operations planning has a vital importance in this environment. One of the most important problem types for the airport management is the well known gate assignment problem (GAP). In this study, a column generation (CG) algorithm is proposed to solve GAP and the algorithm is formulated as a linear programming relaxation of the set covering problem. The pricing subproblem (PSP) for the CG approach is represented with a network structure and solved using the shortest path algorithm. Results show that for both homogeneous and heterogeneous instances, the proposed CG algorithm provides optimal LP solutions according to the idle time of variance robustness measure. Insert capability suggested by Dorndorf [1] is also investigated as a robustness measure and compared to variance of idle time. A computational study performed on data sets from Bolat [2] indicate that the two robustness measures are negatively correlated.