  In this paper, we provide a column generation-based approach for solving the
airport flight-to-gate assignment problem, where the goal is to minimize the
on-ground portion of arrival delays by optimally assigning each scheduled
flight to a compatible gate. Specifically, we use a set covering formulation
for the master problem and decompose the pricing problem such that each gate is
the basis for an independent pricing problem to be solved for assignment
patterns with negative reduced costs. We use a combination of an approximation
algorithm based on the submodularity of the underlying set and dynamic
programming algorithms to solve the independent pricing problems. To the best
of our knowledge, this is the first use of submodularity property to
efficiently solve pricing problems and improve the performance of column
generation algorithm. We show that the dynamic programming algorithm is
pseudo-polynomial when there are integer inputs. We also design and employ a
rolling horizon method and block decomposition algorithm to solve large-sized
instances. Finally, we perform extensive computational experiments to validate
the performance of our approach.

Optimization and Control