Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem

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.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2017, 256 (3), pp.696-712. 〈10.1016/j.ejor.2016.07.008〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal-insa-rennes.archives-ouvertes.fr/hal-01353974
Contributeur : Jérémy Omer <>
Soumis le : lundi 22 août 2016 - 12:02:37
Dernière modification le : jeudi 21 juin 2018 - 01:21:50
Document(s) archivé(s) le : mercredi 23 novembre 2016 - 10:41:52

Fichier

2016_Lehouillier_ATC_EJOR_prep...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

Citation

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〉

Partager

Métriques

Consultations de la notice

358

Téléchargements de fichiers

407