A Quantum Approach to the Aircraft-Assignment Problem

A promising application for quantum computing is optimisation problems, and one such problem is the tail-assignment problem. Its combinatorial nature places it in a class of problems where complexity increases so quickly as the problem scales that classical methods can no longer guarantee an efficient solution, making it a suitable candidate for quantum approaches.

The Background#

The problem is essentially to assign a set of flights to individual aircraft, creating cost-effective routes for each aircraft and an optimal overall flight schedule. This problem structure is not limited to flight scheduling but can be found across a range of different optimisation problems such as routing, staff scheduling, resource allocation, cutting stock, and so on, making a computationally effective solution highly relevant.

In the publication “Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem” by Pontus Vikstål et al. from 2020,¹ a simplified version of the problem is successfully solved using numerical simulations of the Quantum Approximate Optimization Algorithm (QAOA), a heuristic hybrid quantum-classical algorithm designed for solving combinatorial optimisation problems on near-term quantum computers.

The Problem#

To begin, a number of simplifications were made to the problem formulation to accommodate the current capability of quantum computers. These modifications include:

• Selecting a set number of routes with the classically obtained solution included, guaranteeing a correct solution exists and limiting the total number of possibilities.
• Assigning an initial flight for each aircraft, so that each route belongs to one specific aircraft.
• Disregarding the costs, consequently turning the problem into the exact-cover problem.

Despite these simplifications, the exact-cover problem is still highly relevant for the study of tail-assignment, as many airlines already treat the real-world tail-assignment problem itself as a pure feasibility problem. The scenarios chosen in the article are: 10 sets of 8 possible routes to cover 77 flights, 9 sets of 15 possible routes for 77 flights, and 10 larger, more realistic problem sets of 25 possible routes for 278 flights.

The Algorithm#

The Quantum Approximate Optimization Algorithm utilises the fact that this problem can be expressed as the problem of finding the minimum energy configuration of the kind of quantum system that can be simulated on a quantum computer. Thus, finding the ground state of a quantum system set up with the same constraints is equivalent to finding the solution to the problem.

Every possible route is represented by a qubit, and it is the output of this qubit that decides whether a route is included in the solution. First, qubits are coupled based on the overlap between their respective routes; the more overlap, the stronger the coupling. The next step of the algorithm is to translate this coupling strength into a probability of the qubit pair collapsing into the same state. To find the perfect relationship between the coupling strength and the state probability of the qubit pair, these steps are refined with classically optimised parameters, making this a hybrid quantum algorithm. These steps are iterated in a quantum-classical loop, gradually steering the quantum system towards states more likely to represent a valid solution.

With perfectly optimised parameters, a stronger coupling means a lower probability of the qubits giving the same output, meaning a higher overlap between two routes makes them less likely to both end up in the solution.

The Result#

By numerically simulating the QAOA, Vikstål et al. were able to solve the reduced tail-assignment problem with increasing success probabilities at low iteration levels and guaranteed success as iterations approach infinity. Through obtaining a success probability of 8.97% after two layers of parameter iteration on a 25-qubit system, it was mathematically shown that a success probability of 99.9% can be reached with 74 repeated measurements, demonstrating feasibility on near-term quantum devices.

Furthermore, they show that the 25-qubit system with 278 flights reaches a higher success rate than the 15-qubit system with 77 flights after the same number of iterations. This finding indicates that route connectivity, rather than raw problem size, poses the greater challenge when scaling to real-world instances.

Ultimately, this study serves as a proof of concept of how quantum algorithms can successfully tackle small-scale, real, industry-derived problems and can act as a template for companies looking to explore quantum approaches for their own combinatorial challenges.

References#

Footnotes#

1. Vikstål et al., "Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem", Physical Review Applied (2020). ↩