AGROCAMPUS OUEST (Institut Supérieur des Sciences Agronomiques, Agroalimentaires, Horticoles et du Paysage - 65, rue de St Brieuc - CS 84215 - 35042 Rennes cedex - France)
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 Omer
<>
Submitted on : Monday, August 22, 2016 - 12:02:37 PM
Last modification on : Tuesday, September 17, 2019 - 4:20:06 PM
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⟩
