A Stochastic Programming Approach to the Airline Crew Scheduling Problem

By Joyce W. Yen, John R. Birge. 2006

209 citations recorded by the source corpus.

Traditional methods model the billion-dollar airline crew scheduling problem as deterministic and do not explicitly include information on potential disruptions. Instead of modeling the crew scheduling problem as deterministic, we consider a stochastic crew scheduling model and devise a solution methodology for integrating disruptions in the evaluation of crew schedules. The goal is to use that information to find robust solutions that better withstand disruptions. Such an approach is important because we can proactively consider the effects of certain scheduling decisions. By identifying more robust schedules, cascading delay effects are minimized. In this paper we describe our stochastic integer programming model for the airline crew scheduling problem and develop a branching algorithm to identify expensive flight connections and find alternative solutions. The branching algorithm uses the structure of the problem to branch simultaneously on multiple variables without invalidating the optimality of the algorithm. We present computational results demonstrating the effectiveness of our branching algorithm.

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering, Management Science and Operations Research, Mathematical Optimization, Economics & Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

1. Simon Lacoste-Julien
2. François Soumis
3. Yassine Yaakoubi

In Industrial and Manufacturing Engineering

1. Simon Lacoste-Julien
2. Yassine Yaakoubi
3. François Soumis

In Management Science and Operations Research

1. Simon Lacoste-Julien
2. Yassine Yaakoubi
3. François Soumis

In Mathematical Optimization

1. Simon Lacoste-Julien
2. Yassine Yaakoubi
3. François Soumis

In Economics & Operations Research

1. Simon Lacoste-Julien
2. François Soumis
3. Yassine Yaakoubi

Citations in the corpus

• Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, methodology): “The methodology to solve CPPs depends on the size of the airline’s network, rules, collective agreements, and cost structure (Yen & Birge, 2006).”
• Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer (2019, methodology): “The methodology for solving the problem depends on the size of the airline’s network structure , rules, collective agreements, and cost structure (Yen and Birge, 2006).”
• Planning for Robust Airline Operations: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions (2006, background): “Yen and Birge (2001) develop a two-stage stochastic integer programming model to minimize total expected crew costs.”
• Machine Learning in Airline Crew Pairing to Construct Initial Clusters for Dynamic Constraint Aggregation (2020, methodology): “The methodology for solving the problem depends on the size of the airline’s network structure, rules, collective agreements, and cost structure [20].”