Quantum annealing for rostering optimisation
Problem
At Air France KLM, more than 7,000 employees work in shifts with different contract percentages, skills, and authorisation levels. Efficiently scheduling all these employees is a complex task. Traditionally, this is solved by designing basic and personal schedules, which reduces efficiency.
Solution
Quantum annealing is used to find the global minimum in a function, supporting and improving the scheduling processes. This technique is suitable for optimisation problems such as crew scheduling. By formulating the problem as a Quadratic Unconstrained Optimisation (QUBO) problem, we found solutions using quantum annealing, hybrid annealing, and simulated annealing.
Benefit
Quantum annealers achieve nearly optimal schedules, while hybrid solvers outperform both methods. In the future, quantum annealing can generate optimal schedules (with more variables) that comply with regulations, preferences, and operational needs more efficiently than traditional methods.
This work is supported by the Dutch National Growth Fund (NGF) as part of the Quantum Delta NL programme.
