Groupe d’études et de recherche en analyse des décisions

Semi-integrated approaches to airline crew scheduling

Frédéric Quesnel Department of Mathematical and Industrial Engineering, Polytechnique Montréal, Canada

Airline crew scheduling is usually divided in two steps : the crew pairing problem (CPP) and the crew rostering problems (CRP). The goal of the CPP is to find feasible pairings (sequence of flights corresponding to a few days of work for a crew member) at minimum cost. The CRP then uses these pairings in order to create feasible schedule that satisfy as many employee preferences as possible, while respecting a set additional constraints, such language qualification requirements on international flights. The main challenge with this two-phase approach is that the pairings generated by the CPP are often unsuitable for the objective of the CRP. In this talk, I present multiple CPP variants that tackle this issue by considering crew information at the pairing level. I propose algorithmic improvements that deal with the increased complexity of each of these variant, and provide some results for real-world instances.


Du café et des biscuits seront offerts au début du séminaire.
Bienvenue à tous!