Structured Convolutional Kernel Networks for Airline Crew Scheduling
This work addresses the airline crew scheduling problem for airlines, providing a novel method that yields significant cost savings, though it is incremental as it builds on existing convolutional kernel networks.
The authors tackled the airline crew scheduling problem by introducing structured convolutional kernel networks (Struct-CKN) to incorporate constraints into a deep learning framework, resulting in a 17% reduction in solution cost and a 97% reduction in global constraint costs for a large-scale dataset of 50,000 flights per month.
Motivated by the needs from an airline crew scheduling application, we introduce structured convolutional kernel networks (Struct-CKN), which combine CKNs from Mairal et al. (2014) in a structured prediction framework that supports constraints on the outputs. CKNs are a particular kind of convolutional neural networks that approximate a kernel feature map on training data, thus combining properties of deep learning with the non-parametric flexibility of kernel methods. Extending CKNs to structured outputs allows us to obtain useful initial solutions on a flight-connection dataset that can be further refined by an airline crew scheduling solver. More specifically, we use a flight-based network modeled as a general conditional random field capable of incorporating local constraints in the learning process. Our experiments demonstrate that this approach yields significant improvements for the large-scale crew pairing problem (50,000 flights per month) over standard approaches, reducing the solution cost by 17% (a gain of millions of dollars) and the cost of global constraints by 97%.