Optimisation du trafic aérien via des méthodes mixtes (discretes-continus) – ATOMIC

Des approches mathématiques issues de l'optimisation nonlinéaire mixte en nombres entiers seront développées. L'optimisation sera effectuée selon deux stratégies spécifiques. Des méthodes déterministes de type séparation et évaluation (Branch-and-Bound) et leurs variantes spatiale et par intervalles seront principalement prises en considération. Pour faire face à la difficulté du problème, d'autres stratégies seront également explorées, où la garantie d'optimalité est abandonnée au profit de plus d'efficacité en temps de calcul. Plus précisément, nous allons étudier l'hybridation de techniques de programmation mathématique et de (méta)-heuristiques.

Le résultat attendu du projet est la disponibilité d'outils automatiques capables d'intégrer le travail des controleurs du trafic aérien. Ces outils seront basés sur des nouveaux modèles mathématiques issus de l'optimisation mixte en nombres entiers et sur de nouvelles méthodes et algorithmes d'optimisation efficaces.

A partir des résultats obtenus pour les applications considérées, nous chercherons à identifier des classes plus générales des problèmes auxquelles les techniques développées peuvent être appliquées.

Des publications scientifiques, communes ou individuelles, seront réalisées.
Les avancées attendues seront proposées dans des revues internationales du domaine et presentées a des conférences internationales.

La programmation nonlinéaire mixte en nombres entiers (MINLP pour Mixed-Integer Nonlinear Programming) traite des problèmes d'optimisation le plus généraux, impliquant à la fois les variables continues et discrètes et des contraintes non linéaires. Ce sont parmi les problèmes d'optimisation les plus difficiles, résultant dans d'innombrables applications dans des divers domaines. Alors que la recherche sur l'optimisation linéaire en variables mixtes est assez avancée, MINLP est considéré comme un domaine émergent qui est susceptible de croître dans les années à venir. Etant les modèles MINLP en général très difficile à résoudre, il est necessaire exploiter leurs propriétés et développer des techniques de résolution spécifiques visant à réduire l'effort de calcul. Le projet ATOMIC est dans le cadre de ce thème de recherche, avec le but de contribuer à l'avancement sur la modélisation des problèmes réelles intéressants et sur le développement des méthodes efficaces pour leur solution. De nombreux problèmes qui se posent dans la gestion du trafic aérien (ATM pour Air Trafic Management) constituent des sujets de recherche intéressants en particulier pour la recherche opérationnelle et l'optimisation et conduisent naturellement à des modèles MINLP. Le trafic aérien participe au dynamisme économique et social de notre société, et sa gestion efficace a évidemment un impact important sur la vie sociale, économique, environnementale et industrielle. Dans ce cadre, des problèmes ATM doivent être abordés de toute urgence afin d'assurer un niveau plus élevé d'automatisation dans l'ATM et par conséquent plus d'efficacité et de sécurité. Les problèmes qui nous intéressent concernent les conflits aériens, qui surviennent lorsque deux avions sont trop proches l'un de l'autre sur leur trajectoire. La modélisation fondée sur la programmation non linéaire mixte en nombres entiers semble être le candidat naturel pour les problèmes abordés en ATM. En effet le besoin de modéliser des choix logiques suggère la présence de variables mixtes (continues-entières) en même temps que des contraintes non linéaires proviennent de la modélisation des conditions de séparation. Actuellement, les algorithmes de résolution sont principalement fondés sur des approches évolutionnaires. Bien que ces méthodes soient efficaces en termes de temps de calcul, l'optimalité globale et même la réalisabilité d'une solution n'est pas garantie. Les progrès récents en programmation linéaire et non linéaire mixte en nombres entiers ouvrent des nouvelles perspectives qui faisaient défaut dans les précédentes recherches sur la déconfliction et peuvent avoir un impact important pour sa résolution efficace. L'objectif du présent projet est donc d'exploiter pleinement l'optimisation mixte en nombres entiers afin de proposer des nouvelles modélisations et de nouvelles résolutions efficaces. L'optimisation sera effectuée selon deux stratégies spécifiques. Des méthodes déterministes de type séparation et évaluation (BB, pour Branch-and-Bound) et leurs variantes spatiale et par intervalles seront principalement prises en considération, en explorant les stratégies qui peuvent avoir un impact sur l'efficacité de l'algorithme. Pour faire face à la difficulté du problème, d'autres stratégies seront également explorées, où la garantie d'optimalité est abandonné en échange de l'efficacité du temps de calcul. Plus précisément, nous allons étudier l'hybridation des techniques de programmation mathématique et de (méta)-heuristiques, dans le contexte des "matheuristiques". A partir des résultats obtenus pour l'application considérée, nous chercherons à identifier des classes plus générales des problèmes MINLP à lequelles les techniques développées peuvent être appliquées.
Les résultats attendus du projet sont de nouveaux modèles mathématiques issus de la MINLP et de nouvelles méthodes d'optimisation efficaces, ainsi qu'une bibliothèque logicielle implémentant les algorithmes proposés.