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

Fingerprint

Robust Optimization
Aircraft
Routing
Data-driven
Paradigm
Scheduling
Routing Problem
Modeling
Model
Uncertainty
Tractability
Stochastic Optimization
Extreme Values
Integer programming
Domain Knowledge
Constrained Optimization
Integer Programming
Demonstrate
Robust optimization
Lessons learned

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

Cite this

Robust optimization : Lessons learned from aircraft routing. / Marla, Lavanya; Vaze, Vikrant; Barnhart, Cynthia.

In: Computers and Operations Research, Vol. 98, 10.2018, p. 165-184.

Research output: Contribution to journalArticle

Marla, Lavanya ; Vaze, Vikrant ; Barnhart, Cynthia. / Robust optimization : Lessons learned from aircraft routing. In: Computers and Operations Research. 2018 ; Vol. 98. pp. 165-184.
@article{90e7f34bfbb2437093df5fbcef6298aa,
title = "Robust optimization: Lessons learned from aircraft routing",
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.",
keywords = "Aircraft routing, Chance-constrained programming, Robust airline scheduling, Robust optimization",
author = "Lavanya Marla and Vikrant Vaze and Cynthia Barnhart",
year = "2018",
month = "10",
doi = "10.1016/j.cor.2018.04.011",
language = "English (US)",
volume = "98",
pages = "165--184",
journal = "Surveys in Operations Research and Management Science",
issn = "0305-0548",
publisher = "Elsevier Limited",

}

TY - JOUR

T1 - Robust optimization

T2 - Lessons learned from aircraft routing

AU - Marla, Lavanya

AU - Vaze, Vikrant

AU - Barnhart, Cynthia

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

KW - Aircraft routing

KW - Chance-constrained programming

KW - Robust airline scheduling

KW - Robust optimization

UR - http://www.scopus.com/inward/record.url?scp=85048545721&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048545721&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2018.04.011

DO - 10.1016/j.cor.2018.04.011

M3 - Article

AN - SCOPUS:85048545721

VL - 98

SP - 165

EP - 184

JO - Surveys in Operations Research and Management Science

JF - Surveys in Operations Research and Management Science

SN - 0305-0548

ER -