Structured Convolutional Kernel Networks for Airline Crew Scheduling

Yassine Yaakoubi · Francois Soumis · Simon Lacoste-Julien


Keywords: [ Combinatorial Optimization ]

[ Abstract ]
[ Slides
[ Paper ]
[ Visit Poster at Spot B2 in Virtual World ]
Tue 20 Jul 9 p.m. PDT — 11 p.m. PDT
Spotlight presentation: Optimization 3
Tue 20 Jul 5 p.m. PDT — 6 p.m. PDT


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

Chat is not available.