Abstract : In this article, we tackle the conflict resolution problem using a new variant of the minimum-weight maximum-clique model. The problem involves identifying maneuvers that maintain the required separation distance between all pairs of a set of aircraft while minimizing fuel costs. We design a graph in which the vertices correspond to a finite set of maneuvers and the edges connect conflict-free maneuvers. A maximum clique of minimal weight yields a conflict-free situation that involves all the aircraft and minimizes the costs induced. The innovation of the model is its cost structure: the costs of the vertices cannot be determined a priori, since they depend on the vertices in the clique. We formulate the problem as a mixed integer linear program. Since the modeling of the aircraft dynamics and the computation of trajectories is separated from the solution process, the model is flexible. As a consequence, our mathematical framework is valid for any hypotheses. In particular, the aircraft can perform dynamic velocity, heading, and flight-level changes. To solve instances involving a large number of aircraft spread over several flight levels, we introduce two decomposition algorithms. The first is a sequential mixed integer linear optimization procedure that iteratively refines the discretization of the maneuvers to yield a trade-off between computational time and cost. The second is a large neighborhood search heuristic that uses the first procedure as a subroutine. The best solutions for the available set of maneuvers are obtained in less than 10 seconds for instances with up to 250 aircraft randomly allocated to 20 flight levels.
https://hal-insa-rennes.archives-ouvertes.fr/hal-01353974 Contributor : Jérémy OmerConnect in order to contact the contributor Submitted on : Monday, August 22, 2016 - 12:02:37 PM Last modification on : Friday, May 20, 2022 - 9:04:48 AM Long-term archiving on: : Wednesday, November 23, 2016 - 10:41:52 AM
Thibault Lehouillier, Jérémy Omer, François Soumis, Guy Desaulniers. Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem. European Journal of Operational Research, Elsevier, 2017, 256 (3), pp.696-712. ⟨10.1016/j.ejor.2016.07.008⟩. ⟨hal-01353974⟩