Robust optimization: Lessons learned from aircraft routing

Lavanya Marla, Vikrant Vaze, Cynthia Barnhart

Research output: Contribution to journalArticle

Abstract

Building robust airline scheduling models involves constructing schedules and routes with reduced levels of flight delays as well as fewer passenger and crew disruptions. In this paper, we study different classes of models to achieve robust airline scheduling solutions, with a focus on the aircraft routing problem. In particular, we compare one domain-specific approach and two general paradigms of robust models, namely, (i) an extreme-value based or robust optimization-based approach, and (ii) a chance-constrained or stochastic optimization-based approach. Our modeling and solution approach demonstrates the creation of data-driven uncertainty sets for aircraft routing using domain-specific knowledge and develops a completely data-driven simulation-based validation and testing approach. We first demonstrate that additional modeling, capturing domain knowledge, is required to adapt these general robust modeling paradigms to the aircraft routing problem, in order to meaningfully add robustness features specific to aircraft routing. However, we show that these models in their naive forms, still face issues of tractability and solution quality for the large-scale networks which are representative of real-world airline scheduling problems. Therefore, we develop and present advanced models that address these shortcomings. Our advanced models can be applied to aircraft routing in multiple ways, through varied descriptions of the uncertainty sets; and moreover, are generally applicable to linear and binary integer programming problems. Through our detailed computational results, we compare the performance of solutions arising from these different robust modeling paradigms and discuss the underlying reasons for their performance differences from a data-driven perspective.

Original languageEnglish (US)
Pages (from-to)165-184
Number of pages20
JournalComputers and Operations Research
Volume98
DOIs
StatePublished - Oct 2018

Keywords

  • Aircraft routing
  • Chance-constrained programming
  • Robust airline scheduling
  • Robust optimization

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Robust optimization: Lessons learned from aircraft routing'. Together they form a unique fingerprint.

  • Cite this