Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer
This incremental improvement addresses cost and efficiency in airline crew scheduling, where small savings can increase annual revenue by millions of dollars.
The paper tackles the airline crew pairing problem by using a neural network to predict flight connections with high accuracy (99.7% overall or 82.5% on harder instances), which initializes a solver to achieve a 10x speed improvement and up to 0.2% cost saving.
We present a case study of using machine learning classification algorithms to initialize a large-scale commercial solver (GENCOL) based on column generation in the context of the airline crew pairing problem, where small savings of as little as 1% translate to increasing annual revenue by dozens of millions of dollars in a large airline. Under the imitation learning framework, we focus on the problem of predicting the next connecting flight of a crew, framed as a multiclass classification problem trained from historical data, and design an adapted neural network approach that achieves high accuracy (99.7% overall or 82.5% on harder instances). We demonstrate the usefulness of our approach by using simple heuristics to combine the flight-connection predictions to form initial crew-pairing clusters that can be fed in the GENCOL solver, yielding a 10x speed improvement and up to 0.2% cost saving.