Accelerated windowing for the crew rostering problem with machine learning

The airline crew rostering problem (CRP) for pilots is a complex crew scheduling task assigning pairings, or sequences of flights starting and ending at the same airport, to pilots to create a monthly schedule. In this paper, we propose an innovative solution method for the CRP that uses a windowing approach. This method consists of a rolling horizon where we decompose the optimization horizon into several overlapping, time-based windows, and then optimize each one sequentially. Although windowing has been successfully used in other applications, it had never been implemented for the CRP, due to its large number of horizontal constraints involving the whole planning horizon. We find that the rolling horizon method is generally able to find good-quality solutions in a fraction of the run time of traditional methods. However, a drawback of the method is that each window is optimized independently, without information on the requirements of other windows. To overcome this issue, we provide the solver an initial solution. The solver uses that initial solution to derive reliable information for each optimization window. Initial solutions are quickly created through a hybrid machine learning (ML) and optimization method based on a sequential assignment procedure. Results show that the rolling horizon method greatly benefits from such an initial solution. This is because the initial solution provides reliable information on the following windows, allowing the solver to better optimize the current one.