Two essays on airline scheduling problems under time-dependent delay uncertainty

Abstract

Flight delays are common in the airline industry, resulting in massive costs, operational inefficiencies, and poor passenger experience. Delays disrupt tightly scheduled flight plans and propagating throughout the network when buffers are inadequate. The Federal Aviation Administration reports that flight delays cost airlines billions of dollars annually in the United States. Causes include weather, congestion, crew issues and late arrivals of aircraft. Notably, over 30% of delays stem from late arrivals, underscoring the impact of delay propagation. This thesis investigates airline scheduling problems under time-dependent uncertainty in flight delays through robust optimization techniques. It focuses on two key issues: robust flight retiming and robust aircraft routing. Flight retiming involves optimizing departure and arrival times to build in buffers that can absorb propagated delays. Aircraft routing assigns flights to aircraft sequences while minimizing overall propagated delay. Both problems are tackled using robust optimization models incorporating time-dependent delay uncertainty distributions. A novel event-based framework is proposed, which decomposes flights into four distinct phases: departure, cruise, arrival and turnaround. This approach captures the time dynamics of delays more accurately than traditional leg-based models. Delays are linked to specific airport events during particular time blocks rather than entire flight legs. The framework allows the construction of innovative time-dependent uncertainty sets representing primary delays at airports conditional on the time of day. These sets capture the variability of delays caused by changing contextual factors like congestion and weather throughout the day. To address the flight retiming problem, a robust optimization model is developed to minimize worst-case propagated delays by reallocating cruise and turnaround buffers. The model employs the proposed time-dependent uncertainty sets, and solutions are obtained using an iterative cutting-plane algorithm. Experiments conducted on real airline data demonstrate a substantial reduction in propagated delays compared to the original schedules and traditional non-time-dependent robust optimization. Furthermore, the study offers insights into strategically allocating buffer time based on the time-varying delay of flight. Building upon the flight retiming model, a robust optimization formulation is presented for the aircraft routing problem. The formulation employs a event-block-based time-dependent uncertainty set, which captures spatiotemporal delay correlations. To tackle the complexity of this problem, efficient matheuristic algorithms are designed by combining column-and-row generation with route set expansion techniques. Experimental results demonstrate substantial improvements in both speed and solution quality compared to commercial solvers. Furthermore, the aircraft routing model highlights the advantages of time-dependent modeling in minimizing the worst-case, average, and volatility of propagated delays. This thesis makes important contributions by reformulating traditional airline optimization problems to handle time-varying delay uncertainties. The proposed techniques enable more reliable capacity planning, improved aircraft utilization, and enhanced customer service. Moreover, extending this research has the potential to enhance airline scheduling resilience and enhance operational efficiency. The use of an event-based modeling framework represents a critical advancement in capturing the time dynamics within delay uncertainty distributions. Our study makes a fundamental contribution to the field of aviation scheduling and other related scheduling problems, establishing the groundwork for further advancements in the industry.