Problem definition: More than one-third of US domestic flights are operated by regional airlines. This paper focuses on optimizing medium-term schedule planning decisions for a network of regional airlines through the joint optimization of frequency planning, timetable development, fleet assignment, and some limited aspects of route planning, while capturing passengers’ travel decisions through a general attraction discrete choice model.
Methodology: Unlike previous studies that focused on flight-level decision variables, our formulation uses composite variables to model all non-stop flights between a pair of airports and their complex interdependencies, giving rise to an extended formulation with an extremely tight continuous relaxation. We develop an original solution approach based on column generation and a restricted master heuristic to generate high-quality solutions. Additionally, we propose a new acceleration technique based on dynamic programming to quickly generate promising columns. When combined with implicit dual smoothing, symmetry-breaking techniques, and subproblem aging, this acceleration approach allows us to solve large-scale real-world instances to near-optimality in less than 3 hours.
Results: Through an extensive computational analysis for some of the largest regional airline networks in the US, we demonstrate the effectiveness of our overall modeling and computational framework. Our approach can generate daily profit improvements of up to $0.4 million compared to the actual schedule of the airline.
Implications: We identify the main operational drivers of profit improvement. Furthermore, numerous sensitivity analyses confirm that our results are robust to relaxing key modeling assumptions. Ultimately, our detailed experiments show that the proposed approach provides near-optimal solutions to real-world problem instances within practically reasonable runtimes.