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.