Continuous Time Formulation and Lagrangian Relaxation Algorithm for the Gate Assignment Problem

Gates are important operating facilities and resources in civil airports. It is a core task in the airport operation management to select reasonable gates for inbound and outbound flights. We present a continuous time formulation with second-order cone programming (SOCP) for the gate assignment problem which allocates flights to available gates to optimize both the transfer time of passengers and the robustness of the airport operations schedules. The problem is formulated as a mixed integer nonlinear program, and then, the quadratic objective that minimizes the walking distance of transferring passengers is linearized, and the objective that minimizes the variance of idle time at the gates is transformed to a second-order cone constraint with a linear objective function. Then, a Lagrangian relaxation algorithm is developed by exploiting the problem structure. Computational tests are carried out to illustrate the efficiency of the model and the algorithms. It is shown that the continuous time formulation is more efficient than the existing model, and the Lagrangian relaxation algorithm can obtain better solutions faster than a commercial solver.