Mathematical models for flight-to-gate reassignment with passenger flows: State-of-the-art comparative analysis, formulation improvement, and a new multidimensional assignment model

This study explores the mathematical programming formulation of Flight-to-Gate Reassignment with passenger connections, one of the most critical problems in airport and airline recovery operations. Motivated by the intractable increase in problem size when passenger flows are considered, combined with the need for low solution time, we perform three main tasks: (a) We compare and analyze both theoretically and experimentally the different types of state-of-art formulations, and identify the limitations of each one. (b) We improve the performance of existing models by modifying their formulations and introducing valid inequalities. (c) We propose a novel mathematical formulation that accounts for passenger connections considering the layout of the airport and the available time between connecting flights. For the purpose of our experiments, we generate a number of cases of various sizes and schedule scenarios, as well as a set based on a real European airport. We then use our results to identify the most efficient formulations under different objective functions and problem assumptions. We expect that our work can provide researchers with a valuable tool for formulating efficient models that can be embedded in mathematical programming-based heuristics.