Groupe d’études et de recherche en analyse des décisions

G-2015-103

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

, , et

Nous présentons un modèle déterministe pour le problème de détection et de résolution de conflits entre aéronefs. Les aspects liés à la dynamique des avions, à leurs manoeuvres ainsi que la fonction de coûts sont complètement séparés du processus de résolution. En conséquence, le formalisme mathématique présenté reste valide, et ce quelles que soient les hypothèses faites sur les avions, les manoeuvres et les coûts. Nous modélisons le problème comme une recherche de clique de cardinalité maximale et de coût minimum dans un graphe. Les sommets du graphe correspondent à des manoeuvres des aéronefs, et les arêtes connectent des manoeuvres sans conflit d'aéronefs distincts. Ce modèle est en fait une nouvelle variante du problème de recherche de clique de coût minimum, dans le sens où les coûts des sommets dépendent des sommets de la clique. Nous formulons cette nouvelle variante comme un programme linéaire à variables mixtes. Nous présentons également deux méthodes de décomposition pour le problème. La première vise à étudier l'impact du nombre de manoeuvres par aéronef sur le temps de résolution, et permet de trouver un compromis entre effort calculatoire et efficacité de la solution. La seconde vise à exploiter la structure géométrique de l'ensemble d'aéronefs considérés. Des instances ayant jusque 65 avions sur un seul niveau sont résolues en moins de deux minutes par le modèle classique, et les méthodes de décomposition permettent de résoudre des instances ayant jusque 250 avions répartis sur 20 niveaux de vol en moins de 10 secondes.

, 36 pages