Optimal Reassignment of Flights to Gates Focusing on Transfer Passengers

Abstract

This dissertation focuses on the optimal flight-to-gate assignment in cases of schedule disruptions with a focus on transfer passengers. Disruptions result from increased passenger demand, combined with tight scheduling and limited infrastructure capacity. The critical role of gate assignment, combined with the scarcity of models and algorithms to handle passenger connections, is the main motivation for this study. Our first task is to develop a generalizable multidimensional assignment model that considers the location of gates and the required connection time to assess the success of passenger transfers. The results demonstrate that considering gate location is critical for assessing of the success of a connection, since transfer passengers contribute significantly to total cost. We then explore the mathematical programming formulation of the problem. First, we compare different state-of-art mathematical formulations, and identify their underlying assumptions. Then, we strengthen our time-index formulation by introducing valid inequalities. Afterwards, we express the cost of passenger connections using an aggregating formulation, which outperforms the quadratic formulation and is consistently more efficient than network flow formulations when the cost of successful connections is considered. In the last part of the dissertation, we embed the formulation in an MIP-based metaheuristic framework using Variable Neighborhood Search with Local Branching (VNS-LB). We explore the key notion of a solution neighborhood in the context of gate assignment, given that transfer passengers are our main consideration. Our implementation produces near-optimal results in a low amount of time and responds reasonably to sensitivity analysis in operating parameters and external conditions. Furthermore, VNS-LB is shown to outperform the Local Branching heuristic in terms of solution quality. Finally, we propose a set of extensions to the algorithm which are shown to improve the quality of the final solution, as well as the progress of the optimization procedure as a whole. This dissertation aspires to develop a versatile tool that can be adapted to the objectives and priorities of practitioners, and to provide researchers with an insight of how the features of a solution are reflected in the mathematical formulation. Every idea relying on these principles should be a promising path for future research.