Une méthode de Branch and Bound par Intervalles appliquée à la résolution en vitesse de conflits aériens

Nicolas Durand (1, 2) , Jean-Marc Alliot (1, 2)

1 DGAC - Direction Générale de l'Aviation Civile
2 IRIT-APO - Algorithmes Parallèles et Optimisation

Deux avions en croisière à la même altitude séparés de moins de 5 miles nautiques sont dits en conflit. Le rôle du contrôleur aérien est d'éviter les situations de conflits en anticipant des manoeuvres de séparation (changement de cap ou de niveau de vol de l'un des deux avions). En modifiant légèrement les vitesses des avions, on peut résoudre les conflits aériens en amont, et ce à l'insu du contrôleur qui n'est pas perturbé par ce prétraitement. Le projet ERASMUS [BDG09] qui a introduit ce concept se base actuellement sur un algorithme évolutionnaire développé dans les années 90 sur le simulateur CATS [GDA01]. Le problème de résolution de conflits est un problème très combinatoire. La littérature ne propose que deux approches efficaces pour résoudre de façon centralisée des problèmes de grande taille (plus d'une vingtaine d'avions). L'approche de [PFB02] utilise la programmation linéaire mixte, mais requiert des hypothèses fortes sur les trajectoires (vitesses constantes, manoeuvres exécutées en même temps). L'approche par algorithme évolutionnaire [DA98] est plus ancienne et permet de prendre en compte des trajectoires issues d?un simulateur de trafic. Ce résumé a pour but de présenter un algorithme de Branch and Bound par Intervalle, tel que décrit par exemple par [Han92], adapté à un problème de résolution de conflits en vitesse. Un problème "jouet" est utilisé pour tester l'algorithme. n avions sont disposés sur un cercle et se dirigent vers le centre du cercle.

Mots clés: IBBA; résolution de conflits

Domaines: Optimisation et contrôle [math.OC]

Nicolas Durand, Jean-Marc Alliot. Une méthode de Branch and Bound par Intervalles appliquée à la résolution en vitesse de conflits aériens. ROADEF 2011, 12ème congrès annuel de la Société française de Recherche Opérationnelle et d'Aide à la Décision, Mar 2011, St-Etienne, France. ⟨hal-00940896⟩