Conception et analyse d'un système d'optimisation de plans de vol pour les avions

L'objectif principal de cette thèse est de développer une méthode d'optimisation pour la préparation des plans de vol d'avion qui minimisent tous les coûts associés au vol. On doit calculer une trajectoire optimale pour un avion devant aller d'un aéroport de départ à un aéroport d'arrivée. La trajectoire optimale minimise la somme de tous les coûts, c'est-à-dire le coût du carburant plus le coût du temps (salaires, location de l'appareil, retards à l'arrivée, etc.). La trajectoire optimale est obtenue en considérant toutes les trajectoires possibles sur un graphe 3D (longitude, latitude et altitude) où on utilise des niveaux d'altitude espacés de 2000 pieds, et en appliquant un algorithme de plus court chemin. L'essentiel du travail de cette thèse a été de calculer correctement la consommation de carburant sur chaque arc du graphe, en s'assurant que chaque arc ait un coût minimal et soit parcouru d'une façon réaliste du point de vue du pilotage, en respectant toutes les règles de navigation. Le calcul de coût d'un arc tient compte des conditions météorologiques (température, pression, composantes du vent, etc.). L'optimisation de chaque arc se fait à partir de l'évaluation d'une vitesse optimale qui tient compte de tous les coûts. Chaque arc du graphe comporte en général plusieurs sous-phases de vol (changement d'altitude, changement de vitesse, vitesse et altitude constante pour un arc en phase de croisière). En phase de montée initiale et de descente finale, on détermine les coûts en utilisant une vitesse CAS (pour Calibrated Air Speed en anglais) constante ou un nombre de Mach constant de telle sorte que la trajectoire soit optimale. La modélisation aérodynamique utilisée est celle qui est proposée par Eurocontrol. Elle utilise les tables BADA (pour \emph{Base of Aircraft Data} en anglais). Cette modélisation se base sur l'équation de l'énergie totale. Cette équation permet de déterminer la consommation instantanée de carburant. Le calcul des coûts sur chaque arc passe par la résolution d'un système d'équations différentielles qui comptabilise systématiquement tous les coûts. Pour calculer le coût d'un arc, on doit connaître le temps nécessaire pour le parcourir, qui est généralement inconnu. Pour avoir des conditions aux frontières bien définies, on a utilisé le déplacement horizontal comme variable indépendante du système d'équations différentielles. On a considéré les composantes de la vitesse du vent dans un référentiel en trois dimensions pour calculer la vitesse instantanée de l'avion par rapport au sol. Notre modélisation du problème permet de calculer les coûts de chaque arc d'une façon réaliste et sans changement brusque de vitesse ou d'altitude. Pour tenir compte du coût du temps, on a utilisé l'indice du coût (CI pour Cost Index en anglais). Le coût d'un arc dépend de la masse de l'avion au début de cet arc, et cette masse dépend de la trajectoire qui précède. Comme on considère toutes les trajectoires possibles, il s'ensuit que le coût d'un arc doit être calculé pour chacune des trajectoires à laquelle il appartient. Pour un long trajet, le nombre d'arcs à considérer dans le graphe est grand et donc le coût d'un arc est typiquement calculé un grand nombre de fois. Le temps de calcul du coût d'un arc est donc un critère important. Notre algorithme exécute le calcul des coûts d'un million d'arcs en quelques secondes tout en ayant une grande précision. La détermination de la trajectoire optimale pourrait donc se faire en un temps très court. Pour qu'une trajectoire soit optimale, il faut que la masse de l'avion au départ soit aussi optimale. Il faut donc connaître la quantité de carburant optimale pour le trajet. Comme on connaît la masse de l'avion à l'arrivée, qui est la masse de l'avion incluant les passagers, le cargo et la masse de carburant de réserve, on détermine la trajectoire optimale en effectuant un calcul à rebours, c'est-à-dire du point d'arrivée au point de départ. Pour la détermination de la trajectoire optimale, on a utilisé une grille elliptique qui a comme foyers les points de départ et d'arrivée. L'utilisation de cette grille est essentielle pour nous permettre d'avoir un graphe dirigé et acyclique. L'algorithme du plus court chemin utilisé est le plus court chemin sur un DAG (pour Direct Acyclic Graph en anglais). Cet algorithme est facile à implémenter et nous permet d'avoir un temps d'exécution très court. Notre algorithme respecte les niveaux d'altitude et fournit une trajectoire optimale en ayant un coût optimal pour chaque arc. Les changements d'altitude se font d'une façon optimale selon la masse de l'avion et le coût du temps. Cet algorithme donne la masse, la vitesse, l'altitude et le coût total en tout point de la trajectoire ainsi que les profils optimaux de montée et de descente. Un prototype a été implémenté en langage C. On a fait des simulations des différents types d'arcs possibles ainsi que des trajectoires complètes pour illustrer le comportement de l'algorithme. On présente dans cette thèse les méthodes utilisées ainsi que les résultats obtenus.

Abstract

The main objective of this thesis is to develop an optimization method for the preparation of flight plans for aircrafts. The flight plan minimizes all costs associated with the flight. We determine an optimal path for an airplane from a departure airport to a destination airport. The optimal path minimizes the sum of all costs, i.e. the cost of fuel added to the cost of time (wages, rental of the aircraft, arrival delays, etc). The optimal trajectory is obtained by considering all possible trajectories on a 3D graph (longitude, latitude and altitude) where the altitude levels are separated by 2,000 feet, and by applying a shortest path algorithm. The main task was to accurately compute fuel consumption on each edge of the graph, making sure that each arc has a minimal cost and is covered in a realistic way from the point of view of control, i.e. in accordance with the rules of navigation. To compute the cost of an arc, we take into account weather conditions (temperature, pressure, wind components, etc). The optimization of each arc is done via the evaluation of an optimum speed that takes all costs into account. Each arc of the graph typically includes several sub-phases of the flight, e.g. altitude change, speed change, and constant speed and altitude. In the initial climb and the final descent phases, the costs are determined by considering altitude changes at constant CAS (Calibrated Air Speed) or constant Mach number. CAS and Mach number are adjusted to minimize cost. The aerodynamic model used is the one proposed by Eurocontrol, which uses the BADA (Base of Aircraft Data) tables. This model is based on the total energy equation that determines the instantaneous fuel consumption. Calculations on each arc are done by solving a system of differential equations that systematically takes all costs into account. To compute the cost of an arc, we must know the time to go through it, which is generally unknown. To have well-posed boundary conditions, we use the horizontal displacement as the independent variable of the system of differential equations. We consider the velocity components of the wind in a 3D system of coordinates to compute the instantaneous ground speed of the aircraft. To consider the cost of time, we use the cost index. The cost of an arc depends on the aircraft mass at the beginning of this arc, and this mass depends on the path. As we consider all possible paths, the cost of an arc must be computed for each trajectory to which it belongs. For a long-distance flight, the number of arcs to be considered in the graph is large and therefore the cost of an arc is typically computed many times. Our algorithm computes the costs of one million arcs in seconds while having a high accuracy. The determination of the optimal trajectory can therefore be done in a short time. To get the optimal path, the mass of the aircraft at the departure point must also be optimal. It is therefore necessary to know the optimal amount of fuel for the journey. The aircraft mass is known only at the arrival point. This mass is the mass of the aircraft including passengers, cargo and reserve fuel mass. The optimal path is determined by calculating backwards, i.e. from the arrival point to the departure point. For the determination of the optimal trajectory, we use an elliptical grid that has focal points at the departure and arrival points. The use of this grid is essential for the construction of a direct and acyclic graph. We use the Bellman-Ford algorithm on a DAG to determine the shortest path. This algorithm is easy to implement and results in short computation times. Our algorithm computes an optimal trajectory with an optimal cost for each arc. Altitude changes are done optimally with respect to the mass of the aircraft and the cost of time. Our algorithm gives the mass, speed, altitude and total cost at any point of the trajectory as well as the optimal profiles of climb and descent. A prototype has been implemented in C. We made simulations of all types of possible arcs and of several complete trajectories to illustrate the behaviour of the algorithm.