Airline schedule planning and operations : optimization-based approaches for delay mitigation

[摘要] We study strategic and operational measures of improving airline system performance and reducing delays for aircraft, crew and passengers. As a strategic approach, we study robust optimization models, which capture possible future operational uncertainties at the planning stage, in order to generate solutions that when implemented, are less likely to be disrupted, or incur lower costs of recovery when disrupted. We complement strategic measures with operational measures of managing delays and disruptions by integrating two areas of airline operations thus far separate - disruption management and flight planning. We study different classes of models to generate robust airline scheduling solutions. In particular, we study, two general classes of robust models: (i) extreme-value robust-optimization based and (ii) chance-constrained probability-based; and one tailored model, which uses domain knowledge to guide the solution process. We focus on the aircraft routing problem, a step of the airline scheduling process. We first show how the general models can be applied to the aircraft routing problem by incorporating domain knowledge. To overcome limitations of solution tractability and solution performance, we present budget-based extensions to the general model classes, called the Delta model and the Extended Chance-Constrained programming model. Our models enhance tractability by reducing the need to iterate and re-solve the models, and generate solutions that are consistently robust (compared to the basic models) according to our performance metrics. In addition, tailored approaches to robustness can be expressed as special cases of these generalizable models. The extended models, and insights gleaned, apply not only to the aircraft routing model but also to the broad class of large-scale, network-based, resource allocation. We show how our results generalize to resource allocation problems in other domains, by applying these models to pharmaceutical supply chain and corporate portfolio applications in collaboration with IBM;;s Zurich Research Laboratory. Through empirical studies, we show that the effectiveness of a robust approach for an application is dependent on the interaction between (i) the robust approach, (ii) the data instance and (iii) the decision-maker;;s and stakeholders;; metrics. We characterize the effectiveness of the extreme-value models and probabilistic models based on the underlying data distributions and performance metrics. We also show how knowledge of the underlying data distributions can indicate ways of tailoring model parameters to generate more robust solutions according to the specified performance metrics. As an operational approach towards managing airline delays, we integrate flight planning with disruption management. We focus on two aspects of flight planning: (i) flight speed changes; and (ii) intentional flight departure holds, or delays, with the goal of optimizing the trade-off between fuel costs and passenger delay costs. We provide an overview of the state of the practice via dialogue with multiple airlines and show how greater flexibility in disruption management is possible through integration. We present models for aircraft and passenger recovery combined with flight planning, and models for approximate aircraft and passenger recovery combined with flight planning. Our computational experiments on data provided by a European airline show that decrease in passenger disruptions on the order of 47.2%-53.3% can be obtained using our approaches. We also discuss the relative benefits of the two mechanisms studied - that of flight speed changes, and that of intentionally holding flight departures, and show significant synergies in applying these mechanisms. We also show that as more information about delays and disruptions in the system is captured in our models, further cost savings and reductions in passenger delays are obtained.

[发布机构] Massachusetts Institute of Technology