Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management

TLDR

The study maps strategic conflict‑resolution problems in air traffic management to quadratic unconstrained binary optimization formulations. Using a conflict‑graph representation, the authors decompose wind‑optimal trajectory problems into discretized subproblems that can be encoded on D‑Wave quantum annealers and benchmark their hardness against classical solvers. Preliminary experiments show that the hardest subproblems executable on current D‑Wave devices reach optimal solutions with 99 % probability in under one second of annealing time.

Abstract

We present the mapping of a class of simplified air traffic management problems (strategic conflict resolution) to quadratic unconstrained Boolean optimization problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where the nodes of the graph represent flights and the edges represent a potential conflict between flights. The representation allows a natural decomposition of a real-world instance related to wind-optimal trajectories over the Atlantic Ocean into smaller subproblems that can be discretized and are amenable to be programmed in quantum annealers. In this paper, we tested the new programming techniques, and we benchmark the hardness of the instances using both classical solvers and the D-Wave 2X and D-Wave 2000Q quantum chip. The preliminary results show that for reasonable modeling choices, the most challenging subproblems which are programmable in the current devices are solved to optimality with 99% of probability within a second of annealing time.