The Problem
At Air France KLM over 7,000 employees work in shifts with different contract percentages, skill and authorization levels, etc. Efficiently scheduling all these employees becomes a complex combinatorial task. To solve it classically, Air France KLM simplifies the problem by designing both base rosters and personal rosters, reducing its efficiency.
Designing personal rosters directly would make the company adjustable in to a world in which it is extremely difficult to plan for a future that is constantly changing and while this task is classically intractable, quantum computing heuristics have shown potential to handle combinatorial problems effectively.
The Quantum Solution
e solution employs quantum annealing, a technique used to find the global minimum in a given function, revolutionizing rostering processes. This approach is particularly suited for solving optimization problems, which are common in complex scheduling tasks like crew rostering. By formulating Air France KLM’s rostering problem as a Quadratic Unconstrained Optimization (QUBO) problem, we found solutions by using quantum annealing, classical-quantum hybrid annealing and simulated annealing.
Simulated Annealing (SA) versus Hybrid Quantum solvers (HQPU). On the x-axis the number of days for which rosters were scheduled and on the y-axis the amount of constraints violated and the closeness of the found solution.
The Benefits
The fully quantum annealers already achieve close to the optimal schedule, while the hybrid solvers outperform both the quantum annealers and the simulated annealers. By utilizing quantum annealing, the solver could in future generate optimal rosters that conform to regulations, preferences, and operational needs, far more efficiently than traditional methods.
This work is supported by the Dutch National Growth Fund (NGF), as part of the Quantum Delta NL programme
