The problem

In the airline industry, a significant share of operating costs is associated with the labor required to operate aircraft. As a result, airlines invest substantial resources into optimizing crew-related costs while complying with labor regulations, operational constraints, and union agreements. Due to the complexity of crew planning, the overall problem is typically decomposed into a sequence of subproblems, each with its own optimization challenges.

One of these subproblems is Airline Crew Pairing (ACP). In this context, a sequence of flights is called a pairing if the home base from which the first flight departs is the same as the base at which the final flight arrives, while also satisfying all operational and regulatory requirements.

The associated costs include several components, such as the number of crew workdays required to operate the schedule, hotel and accommodation costs, and robustness against irregular events such as delays or crew sickness.

The goal of the study

To examine how quantum computers can be applied to the airline crew pairing problem as part of a deeply integrated hybrid classical-quantum optimization workflow.

The result

A fully hybrid solution method was developed in which quantum and classical systems cooperate within the same optimization pipeline. While the approach shows promising long-term practical potential, the capabilities of current quantum hardware still significantly limit the size and complexity of problems that can be solved today.

Scientific summary of the work

The inputs of the problem consist of the flight schedule - a list of individual flight legs together with associated operational data such as departure and arrival times, aircraft type, and crew requirements - as well as the operational rules that must be satisfied and the costs associated with valid round trips (pairings).

The selected algorithmic approach follows a two-level generate-then-select framework. First, legal pairings are generated by assembling compatible flight legs into valid round trips. Then, a subset of these pairings is selected such that each flight leg is covered exactly once.

The second stage is formulated as a binary linear optimization problem with equality constraints, commonly known as the Set Partitioning Problem (SPP). In practical applications, numerous acceleration techniques can be applied to improve computational performance. In this work, however, the focus was on evaluating the feasibility of the approach on quantum hardware.

The SPP was solved using a hybrid constraint-generation method. The optimization process begins with all constraints relaxed and solved on a quantum device. Based on the intermediate solutions obtained, constraints are gradually reintroduced until a feasible, high-quality solution is reached.

The setup

An established SaaS company provides workforce scheduling and related workforce management solutions for local public transport operators in different cities.

The problem

The client had seen increasing attention around quantum computing for optimization problems and started asking whether they should invest in the technology - and if so, where to begin.

The work

After the initial discussions around their domain and operational requirements, it became clear that the problem they faced was different from what they originally expected. A deeper analysis of their systems led to three main conclusions:

• Quantum computers are unlikely to disrupt their core business through better scheduling optimization. Their systems operate on large volumes of data, require highly precise decisions, need to account for personnel preferences, and must react quickly to operational disruptions - all areas where current quantum approaches are a poor fit.

  Instead, we identified more practical improvements through established AI techniques such as constraint programming and embedded neural networks, which are better suited for fast and reliable decision-making in their environment.

• Their more immediate exposure was in data security. Parts of their infrastructure still relied on cryptographic protocols that are not considered secure against future quantum attacks.

  We identified the affected components and defined a migration path toward already available quantum-safe technologies.

• They did not need to establish a dedicated quantum R&D function or continuously pilot emerging technologies.

  A lightweight monitoring approach based on trusted sources and periodic reviews was sufficient to stay informed and react when necessary.

The result

The client left with a clear quantum strategy that:

• avoided millions of euros in unnecessary hiring and system renewal efforts;
• defined a practical roadmap toward quantum-safe operations; and
• identified proven ways to improve their core planning systems without pursuing the wrong technology direction.