Structured Convolutional Kernel Networks for Airline Crew Scheduling

Yassine Yaakoubi, Francois Soumis, Simon Lacoste-Julien
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:11626-11636, 2021.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-yaakoubi21a, title = {Structured Convolutional Kernel Networks for Airline Crew Scheduling}, author = {Yaakoubi, Yassine and Soumis, Francois and Lacoste-Julien, Simon}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {11626--11636}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/yaakoubi21a/yaakoubi21a.pdf}, url = {https://proceedings.mlr.press/v139/yaakoubi21a.html}, abstract = {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%.} }
Endnote
%0 Conference Paper %T Structured Convolutional Kernel Networks for Airline Crew Scheduling %A Yassine Yaakoubi %A Francois Soumis %A Simon Lacoste-Julien %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-yaakoubi21a %I PMLR %P 11626--11636 %U https://proceedings.mlr.press/v139/yaakoubi21a.html %V 139 %X 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%.
APA
Yaakoubi, Y., Soumis, F. & Lacoste-Julien, S.. (2021). Structured Convolutional Kernel Networks for Airline Crew Scheduling. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:11626-11636 Available from https://proceedings.mlr.press/v139/yaakoubi21a.html.

Related Material