The airline industry faces many causes of disruption. To minimise financial and reputational impact, the airline must adapt its schedules. Due to the complexity of the environment, simulation is a natural modelling approach. However, the large solution space, time constraints and system constraints make the search for revised schedules difficult. This paper presents a method for the aircraft recovery problem that uses multi-fidelity modelling including a trust region simulation optimisation algorithm to mitigate the computational costs of using high-fidelity simulations with its benefits for providing good estimates of the true performance.
more »
« less
A multi-fidelity modelling approach for airline disruption management using simulation
Disruption is a serious and common problem for the airline industry. High utilisation of aircraft and airport resources mean that disruptive events can have large knock-on effects for the rest of the schedule. The airline must rearrange their schedule to reduce the impact. The focus in this paper is on the Aircraft Recovery Problem. The complexity and uncertainty involved in the industry makes this a difficult problem to solve. Many deterministic modelling approaches have been proposed, but these struggle to handle the inherent variability in the problem. This paper proposes a multi-fidelity modelling framework, enabling uncertain elements of the environment to be included within the decision making process. We combine a deterministic integer program to find initial solutions and a novel simulation optimisation procedure to improve these solutions. This allows the solutions to be evaluated whilst accounting for the uncertainty of the problem. The empirical evaluation suggests that the combination consistently finds good rescheduling options.
more »
« less
- Award ID(s):
- 1854562
- NSF-PAR ID:
- 10335100
- Date Published:
- Journal Name:
- Journal of the Operational Research Society
- ISSN:
- 0160-5682
- Page Range / eLocation ID:
- 1 to 14
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
This article aims to leverage the big data in shale gas industry for better decision making in optimal design and operations of shale gas supply chains under uncertainty. We propose a two‐stage distributionally robust optimization model, where uncertainties associated with both the upstream shale well estimated ultimate recovery and downstream market demand are simultaneously considered. In this model, decisions are classified into first‐stage design decisions, which are related to drilling schedule, pipeline installment, and processing plant construction, as well as second‐stage operational decisions associated with shale gas production, processing, transportation, and distribution. A data‐driven approach is applied to construct the ambiguity set based on principal component analysis and first‐order deviation functions. By taking advantage of affine decision rules, a tractable mixed‐integer linear programming formulation can be obtained. The applicability of the proposed modeling framework is demonstrated through a small‐scale illustrative example and a case study of Marcellus shale gas supply chain. Comparisons with alternative optimization models, including the deterministic and stochastic programming counterparts, are investigated as well. © 2018 American Institute of Chemical Engineers
AIChE J , 65: 947–963, 2019 -
Over the last two decades, robust optimization has emerged as a popular means to address decision-making problems affected by uncertainty. This includes single-stage and multi-stage problems involving real-valued and/or binary decisions and affected by exogenous (decision-independent) and/or endogenous (decision-dependent) uncertain parameters. Robust optimization techniques rely on duality theory potentially augmented with approximations to transform a (semi-)infinite optimization problem to a finite program, the robust counterpart. Whereas writing down the model for a robust optimization problem is usually a simple task, obtaining the robust counterpart requires expertise. To date, very few solutions are available that can facilitate the modeling and solution of such problems. This has been a major impediment to their being put to practical use. In this paper, we propose ROC++, an open-source C++ based platform for automatic robust optimization, applicable to a wide array of single-stage and multi-stage robust problems with both exogenous and endogenous uncertain parameters, that is easy to both use and extend. It also applies to certain classes of stochastic programs involving continuously distributed uncertain parameters and endogenous uncertainty. Our platform naturally extends existing off-the-shelf deterministic optimization platforms and offers ROPy, a Python interface in the form of a callable library, and the ROB file format for storing and sharing robust problems. We showcase the modeling power of ROC++ on several decision-making problems of practical interest. Our platform can help streamline the modeling and solution of stochastic and robust optimization problems for both researchers and practitioners. It comes with detailed documentation to facilitate its use and expansion. The latest version of ROC++ can be downloaded from https://sites.google.com/usc.edu/robust-opt-cpp/ . Summary of Contribution: The paper “ROC++: Robust Optimization in C++” proposes a new open-source C++ based platform for modeling, automatically reformulating, and solving robust optimization problems. ROC++ can address both single-stage and multi-stage problems involving exogenous and/or endogenous uncertain parameters and real- and/or binary-valued adaptive variables. The ROC++ modeling language is similar to the one provided for the deterministic case by state-of-the-art deterministic optimization solvers. ROC++ comes with detailed documentation to facilitate its use and expansion. It also offers ROPy, a Python interface in the form of a callable library. The latest version of ROC++ can be downloaded from https://sites.google.com/usc.edu/robust-opt-cpp/ . History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: This material is based upon work supported by the National Science Foundation under Grant No. 1763108. This support is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1209 ) or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at ( https://dx.doi.org/10.5281/zenodo.6360996 ).more » « less
-
Airline booking data have shown that the fraction of customers who choose the cheapest available fare class often is much greater than that predicted by the multinomial logit choice model calibrated with the data. For example, the fraction of customers who choose the cheapest available fare class is much greater than the fraction of customers who choose the next cheapest available one, even if the price difference is small. To model this spike in demand for the cheapest available fare class, a choice model called the spiked multinomial logit (spiked-MNL) model was proposed. We study a network revenue management problem under the spiked-MNL choice model. We show that efficient sets, that is, assortments that offer a Pareto-optimal tradeoff between revenue and resource use, are nested-by-revenue when the spike effect is nonnegative. We use this result to show how a deterministic approximation of the stochastic dynamic program can be solved efficiently by solving a small linear program. The solution of the small linear program is used to construct a booking limit policy, and we prove that the policy is asymptotically optimal. This is the first such result for a booking limit policy under a choice model, and our proof uses an approach that is different from those used for previous asymptotic optimality results. Finally, we evaluate different revenue management policies in numerical experiments using both synthetic and airline data.more » « less
-
more » « less
Customer cancellations and no‐shows have an important impact on the performance of an airline's revenue management system. In this study, we study airline network revenue management problems with customer cancellations and no‐shows, considering two types of demand models: independent‐demand and choice‐based‐demand models. In independent‐demand models, the booking request rates for different products are independent of the assortment of products offered by the airline (exogenous), whereas in choice‐based‐demand models they depend on the airline's assortment (endogenous). The stochastic problems of optimizing the booking policies for the two demand models are not tractable because of the high‐dimensional state space. Therefore, for each model, we use the corresponding deterministic, continuous‐time, and continuous‐state model, known as the fluid model. A booking policy based on the fluid solution can be implemented for the original stochastic, discrete model. This fluid policy is shown to be asymptotically optimal when the arrival rates become high and the seat capacities become large. In the independent‐demand setting, an optimal fluid solution can be computed by solving a convex optimization problem for which efficient algorithms exist, whereas for some choice‐based‐demand models, the fluid control problems are known to be intractable. We also develop mixed fluid policies for the independent‐demand setting, taking advantage of the real‐time booking state, to improve the performance over the fluid policy. In a factorial experiment of 20 small‐sized single‐leg problems, the revenue loss under one of the mixed fluid policies is demonstrated to be less than 1% of the optimal value for all problems.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1080/01605682.2021.1971574
