Multi-Objective Airport Gate Assignment Problem

In this paper, we consider the gate assignment for a large airline at its hub airport. It is considered to be a highly complex problem with the possibility of application in both planning as well as operations mode. There are various considerations that are involved while assigning gates to incoming and outgoing turns at an airport. Different gates have restrictions, such as adjacency, LIFO and push time, which is known in advance from the structure of the airport. When optimizing the assignment costs, we consider different and often conflicting objectives such as maximization of gate rest time between two turns, minimization of the cost of towing an aircraft with a long turn and minimization of overall costs that includes penalization for not assigning preferred gates to certain turns. One of the major contributions of this paper is gate assignment in the planning mode to assign airport gates dynamically to scheduled flights based on daily origin and destination passenger flow data ensuring that the number of passenger misconnects at the hub airport is minimized. We formulate these problems as mixed 0-1 integer program with a linear objective function and constraints. Due to the complexity in the problem size and formulation, we have resorted to relaxation for certain instances when a reasonable solution is not obtained within the time limit. In order to compare the performance of standard MIP, a set partitioning formulation is proposed. The advantage of attempting this alternate formulation is the capability to compare the performance of a normal MIP solution with a column generation algorithm. Implementation is done using OPL and computational results for actual data sets are presented.