Quantum in the airline industry

The problem

In the airline industry, a significant share of operating costs is associated with the labour required to operate aircraft. As a result, airlines invest substantial resources into optimizing crew-related costs while complying with labour 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 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 are the flight schedule, that is, a list of individual flight legs with their operational data (departure and arrival times, aircraft type, and crew requirements), together with 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.