  Airlines today are faced with a number of large scale scheduling problems.
One such problem is the tail assignment problem, which is the task of assigning
individual aircraft to a given set of flights, minimizing the overall cost.
Each aircraft is identified by the registration number on its tail fin. In this
article, we simulate the Quantum Approximate Optimization Algorithm (QAOA)
applied to instances of this problem derived from real world data. The QAOA is
a variational hybrid quantum-classical algorithm recently introduced and likely
to run on near-term quantum devices. The instances are reduced to fit on
quantum devices with 8, 15 and 25 qubits. The reduction procedure leaves only
one feasible solution per instance, which allows us to map the tail assignment
problem onto the Exact Cover problem. We find that repeated runs of the QAOA
identify the feasible solution with close to unit probability for all
instances. Furthermore, we observe patterns in the variational parameters such
that an interpolation strategy can be employed which significantly simplifies
the classical optimization part of the QAOA. Finally, we empirically find a
relation between the connectivity of the problem graph and the single-shot
success probability of the algorithm.
