arXiv:1711.04889 · IEEE Transactions on Intelligent Transportation Systems
Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
Tobias Stollenwerk, Bryan O’Gorman, Davide Venturelli, Salvatore Mandrà, Olga K. Rodionova, Hokkwan Ng, Banavar Sridhar, Eleanor Gilbert Rieffel, Rupak Biswas
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.