Integrated Schedule Planning for Regional Airlines Using Column Generation

More than one-third of U.S. 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. Unlike previous studies that focused on flight-level decision variables, our formulation uses composite variables to model all nonstop 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 (DP) to quickly generate promising columns. When combined with implicit dual stabilization, symmetry-breaking techniques, and subproblem aging, this acceleration approach allows us to solve large-scale real-world instances to near optimality in less than three hours. Through an extensive computational analysis for some of the largest regional airline networks in the United States, 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 with the actual schedule of the airline. 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. Funding: A. Santini’s research was financed by MICIU/AEI/10.13039/501100011033 (Spain) and FSE+ (European Union) [Grant RYC2022-035269-I].