Optimizing Gate Assignments at Airport Terminals

The airport flight-to-gate assignment problem is solved using two methods: a linear programming relaxation of an integer program formulation and a heuristic, which indicates that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution.

Abstract

The airport flight-to-gate assignment problem is solved using two methods: (1) a linear programming relaxation of an integer program formulation and (2) a heuristic. The objective is to minimize passenger walking distances within the airport terminal area through a judicious gate assignment policy. An actual flight schedule for an average day at Toronto International Airport is used to compare existing walking distances, obtained from the original assignment, with results from the two methods. The results indicated that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution. The heuristic’s performance was near optimal; it gave an average walking distance which was only 3.9% greater than the minimum. Computation times for the heuristic are 3.4 CPU seconds per run, while the linear program consumes 386 seconds per run on an IBM 370/168. In addition, if the heuristic is solved first and its solution is used as an initial feasible basis for the LP relaxation of the IP, the total CPU used to obtain optimality is reduced to 42 seconds.