Abstract

This article presents a new algorithm based on the Nelder-Mead simplex algorithmic method for identifying a local optimum, at least on unconstrained nonlinear mixed-integer problems. The algorithmic method, Integer Mixed Simplex Algorithm (IMSA), so called by the author, is based on a double simplex structure, which is composed of a real n -dimensional simplex structure (real simplex) and an integer n -dimensional simplex structure (integer simplex). The original Nelder-Mead operations are applied on the real simplex. Meanwhile, a novel group of operations are applied on the integer simplex. This new set of operations, together with the original Nelder-Mead operations, guarantee a new trail point at each IMSA iteration in the search of the local optimum in the integer real mixed 2n -dimensional numerical field ℝn×ℤn without the need of integer to real conversions.

Abstract

To sustain the continuously increasing air traffic demand, the future air traffic management system will rely on a so-called Trajectory Based Operations (TBO) concept that will increase air traffic capacity by reducing the controller's workload. This will be achieved by transferring tactical conflict detection and resolution tasks to the strategic planning phase. In this future air traffic management paradigm context, this thesis presents a methodology to address such strategic trajectory planning at nation-wide and continent scale. The proposed methodology aims at minimizing the global interaction between aircraft trajectories by allocating alternative departure times, alternative horizontal flight paths, and alternative flight levels to the trajectories involved in the interaction. To improve robustness of the strategic trajectory planning, uncertainty of aircraft position and aircraft arrival time to any given position on the trajectory are considered. This thesis proposes a mathematical formulation of this strategic trajectory planning problem leading to a discrete-optimization and a mixed-integer optimization problem whose objective function relies on the new concept of interaction between trajectories. A computationally efficient algorithm to compute interaction between trajectories for large-scale applications is introduced and implemented. Resolution methods based on metaheuristic and hybrid-metaheuristic algorithms have been developed to solve the above large-scale optimization problems. Finally, the overall methodology is implemented and tested with air traffic data taking into account uncertainty over the French and the European airspaces, involving more than 30,000 trajectories. Conflict-free and robust 4D trajectory planning are produced within computational time acceptable for the operation context, which shows the viability of the approach.; Afin de pouvoir satisfaire la demande sans cesse croissante du trafic aérien, le futur système de gestion du trafic aérien utilisera le concept d'opérations basées sur les trajectoires (Trajectory Based Operations), qui augmentera la capacité du trafic aérien, en réduisant la charge de travail du contrôleur. Pour ce faire, les tâches de détection et de résolution de conflits seront transférées depuis la phase tactique vers la phase stratégique de la planification. Dans le cadre de ce nouveau paradigme pour le système de gestion du trafic aérien, nous introduisons dans cette thèse une méthodologie qui permet d'aborder ce problème de planification stratégique de trajectoires d'avion à l'échelle d'un pays ou d'un continent. Le but de la méthodologie proposée est de minimiser l'interaction globale entre les trajectoires d'avion, en affectant de nouveaux créneaux de décollage, de nouvelles routes et de nouveaux niveaux de vols aux trajectoires impliquées dans l'interaction. De plus, afin d'améliorer la robustesse du plan stratégique de vols obtenu, nous prenons en compte l'incertitude de la position de l'avion et de son heure d'arrivée à un point donné de la trajectoire de l'avion. Nous proposons une formulation mathématique de ce problème de planification stratégique conduisant à un problème d'optimisation discrète et un problème d'optimisation en variables mixtes, dont la fonction objectif est basée sur le nouveau concept d'interaction. Un algorithme efficace en termes de temps de calcul pour évaluer l'interaction entre des trajectoires d'avion pour des applications de grande taille est introduit et mis en œuvre. Des méthodes de résolution basées sur des algorithmes de type métaheuristique et métaheuristique hybride ont été développées pour résoudre ces problèmes d'optimisation de grande taille. Enfin, la méthodologie globale de planification stratégique de trajectoires d'avion est mise en œuvre et testée sur des données de trafic, prenant en compte des incertitudes, pour l'espace aérien français et l'espace aérien européen, impliquant plus de 30000 vols. Des plans de vols 4D sans conflits et robustes ont pu être produits avec des temps de calcul acceptables dans un contexte opérationnel, ce qui démontre la viabilité de l'approche proposée.