Accelerated windowing for the crew rostering problem with machine learning

Philippe Racette ID, Frédéric Quesnel ID, Andrea Lodi ID, François Soumis ID · 2025

Read Accelerated windowing for the crew rostering problem with machine learning by Philippe Racette ID, Frédéric Quesnel ID, Andrea Lodi ID, François Soumis ID (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00160.txt.

Introduction

Philippe Racette, Frederic Quesnel, Andrea Lodi, and Francois Soumis speed up pilot rostering in a 2025 paper. Rostering assigns sequences of flights to pilots to build a monthly schedule, a hard optimization task. Their method first builds a quick starting schedule with a neural network trained by an evolutionary search, guided by optimization tools.

The starting schedule is then improved by splitting the planning period into overlapping windows, each optimized in turn. Windowing had not been used for rostering before, due to rules that span the whole month. On two large real cases, the method ran over ten times faster than the best known solver. Its schedules stayed within one percent of optimal on average.

Catalog record

CREATORPhilippe Racette ID, Frédéric Quesnel ID, Andrea Lodi ID, François Soumis ID
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00160

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accelerated windowing for the crew rostering problem with machine learning Philippe Racette ID, Frédéric Quesnel ID, Andrea Lodi ID, François Soumis ID Abstract The 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. First, using a combination of machine learning (ML) and combinatorial optimisation (CO), we quickly generate an initial solution. The solution is obtained with a sequential assignment procedure ( seqAsg ) based on a neural network trained by an evolutionary algorithm. Then, this initial solution is reoptimized using a branch-and-price algorithm that relies on a windowing scheme to quickly obtain a CRP solution. This windowing method consists of decomposing the optimization horizon into several overlapping windows, and then optimizing each one sequentially. Although windowing has been successfully used in other airline applications, it had never been implemented for the CRP, due to its large number of horizontal constraints involving the whole planning horizon. We test our approach on two large real-world instances, and show that our method is over ten times faster than the state-of-the-art branch-and-price CRP solver GENCOL while providing solutions on average less than 1% away from optimality. We show that our windowing approach greatly benefits from being initialized with good-quality ML-based solutions. This is because the initial solution provides reliable information on the following windows, allowing the solver to better optimize the current one. For this reason, this approach outperforms other naive heuristics, including stand-alone ML or windowing. Keywords: crew rostering, crew scheduling, discrete optimization, evolutionary algorithm, machine learning, reinforcement learning MSC code: 90-08 Computational methods for problems pertaining to operations research and mathematical programming 1 Introduction The crew rostering problem (CRP) is a form of crew assignment concerned with creating sets of schedules for pilots and flight attendants called rosters. Taking a set of pairings (i.e., sequences of flights and layovers starting and ending at the same airport) as input, the CRP forms schedules by assigning them to pilots over a predetermined time horizon. This is done while taking into consideration crew preferences regarding specific flights, days off and special requests made by crew members. A number of airline and collective agreement regulations must also be observed. Developing efficient methods to solve crew scheduling tasks in general is of prime importance to airline carriers, as problems such as the CRP take a long time to solve. One class of methods that has gained ground over the last few years is the use of machine learning (ML) techniques in the context of combinatorial optimization (CO) and operations research (OR) problems. In this paper, we build upon the previous work in Racette et al. [ 1 ] and develop a method that quickly generates good-quality CRP solutions. They propose a sequential assignment procedure named seqAsg , an ML-based approach that generates complete rosters to facilitate schedule planning. Although those rosters could be used to provide insight to planners, they were not of a good enough quality to be used in practice. We expand this contribution by showing that these rosters can be leveraged to obtain different near-optimal solutions produced faster than in the existing literature, and better than what would be obtained by different heuristics. To do so, we propose a windowing approach that can take ML-generated rosters as input and improve them with a branch-and-price algorithm. Windowing is a solution method that decomposes the horizon into several overlapping time windows, and sequentially optimizes each window. Although windowing was applied to great success to the crew pairing problem (CPP) such as in Saddoune, Desaulniers and Soumis [ 2 ] , it has not been attempted for the CRP. This is perhaps because the CPP has more localized horizontal constraints (each pairing lasting a few days). By contrast, the CRP has horizontal constraints spanning the whole horizon (schedule validity constraints). As the results of this paper show, windowing can cope with this difficulty well, and especially so if a good-enough initial solution is provided. This initial solution helps by providing an estimate of the horizontal contributions outside the current optimization window. The benefits of windowing lie in the fact that by only enhancing part of a solution and freezing the rest, the size of the problem treated in each window decreases considerably. However, one possible drawback of windowing is the fact that the method is no longer optimal. The question is then to determine if any loss in the CRP objective is minimal enough to justify significant gains in computational time. Given this context, we make the following contributions: • We propose a windowing approach to the CRP for pilots and prove its effectiveness in obtaining rosters within 1% of optimality. Our method is over 10 times faster than the state of the art. • We show that our windowing method greatly benefits from an initial solution, even if this solution is far from the optimum. Such a solution can be obtained using the ML-based method proposed by Racette et al. [ 1 ] . We also provide a brief discussion of the future implications of this work. In particular, we mention the application of fast ML methods to CO problems, and how this research adds support to the use of ML to enhance solving methods able to exploit even limited additional information. We now give an outline of the paper. In Section 2 , we present a literature review of the topics relevant to this paper. In Section 3 , we provide a detailed description of the CRP. In Section 4 , we lay out the details of the windowing procedure. In Section 5 , we present our experimental protocol and provide some implementation details. In Section 6 , we present the main results supporting our contributions. We conclude in Section 7 with a discussion of the work presented in this paper and of some of its implications. 2 Literature review In this section, we review the relevant literature for the work presented in this paper. We start with Section 2.1 by giving some context relevant to crew scheduling in general and the CRP more specifically. In Section 2.2 , we provide more information about column generation, a technique often used to solve the CRP, and windowing. We describe the literature regarding solving OR problems with ML algorithms in Section 2.3 . Finally, we provide the essential details related to the sequential assignment procedure we use in Section 2.4 . 2.1 Crew scheduling and the CRP Crew scheduling is a rich field that tackles many different problems. Gopalakrishnan and Johnson [ 3 ] describe the main tasks addressed by airline scheduling as a sequential process. The last two parts of the airline scheduling process are the CPP and the crew assignment problem, which includes crew bidding, crew rostering, and preferential bidding. As together these two steps make up crew scheduling, we describe them in more detail. The CPP is concerned with building pairings, i.e., sequences of flights starting and ending at the same airport base, of minimal cost while serving all flights planned in the previous

Read the complete text