L’algorithme de Dijkstra pour optimiser les trajectoires de vol

Problématique

Du dioxyde de carbone (CO2) et d’autres particules polluantes telles que du dioxyde d’azote (NOx), des hydrocarbures et de l’eau sont rejetés dans l’atmosphère lors de la combustion de carburants fossiles dans les moteurs d’avion [1]. Des études prévoient une augmentation du nombre d’avions au cours des prochaines années, ce qui entraînera une augmentation des émissions [2]. L’industrie aéronautique est donc à la recherche de solutions pour réduire ses émissions dans l’atmosphère. Des améliorations technologiques telles que des matériaux plus légers, des avions au nouveau profil aérodynamique et des carburants de rechange sont mises au point pour les générations futures d’appareils [3,4].

Le cycle de vie d’un avion est toutefois assez long (normalement plus de 20 ans). Il est donc important de trouver d’autres solutions pour réduire les émissions des avions actuellement en service; ils seront probablement encore en service lorsque les avions plus modernes arriveront dans le ciel. L’une de ces solutions, l’optimisation des trajectoires de vol et des procédures de contrôle de la circulation, est envisagée de façon plus sérieuse pour deux raisons. La première est que le nombre accru de vols nécessitera des procédures améliorées pour garantir la sécurité du vol. La deuxième est que cette optimisation permettra de réduire la quantité de carburant consommé, donc le coût. Les États-Unis (Next Generation Air Transportation System, NextGen) et l’Europe (Single European Sky ATM Research, SESAR) sont actuellement les leaders de la recherche et de l’implantation des stratégies d’optimisation de vols, comme démontré dans les vidéos ci-dessous.

Les trajectoires de vol sont actuellement optimisées par les équipes au sol avant le décollage et par des appareils à bord de l’avion tels que le système de gestion de vol (FMS) et le planificateur de la circulation (TAP).  Ces appareils calculent les trajectoires optimales parmi lesquelles l’équipage peut choisir une fois l’autorisation de la tour de contrôle obtenue.

Certains des paramètres affectant la consommation de carburant et la durée de vol peuvent être modifiés par le pilote comme, par exemple, l’altitude et la vitesse de croisière. D’autres, par contre, sont stochastiques comme le vent et la température.

La température influence l’efficacité des moteurs. Plus l’environnement est chaud, plus les moteurs doivent consommer de carburant afin de fournir la poussée nécessaire au maintien de la vitesse et de l’altitude d’un vol donné.

Les vents ont une grande influence sur le coût des vols et même sur la sécurité. Ils peuvent se diviser sommairement en deux catégories selon leur direction : vent contraire et vent arrière. Le vent contraire, parce qu’il souffle dans le sens contraire de la trajectoire de l’avion, diminue la vitesse à laquelle l’avion vole (l’avion vole moins rapidement que la vitesse sol désirée, c’est-à-dire la vitesse relative à un observateur au sol). Les moteurs doivent donc fournir une poussée plus grande pour contrer la vitesse du vent et permettre à l’avion d’atteindre la vitesse sol désirée. Le vent arrière souffle dans la même direction que la trajectoire de vol; il « pousse » donc l’avion qui requiert une poussée plus petite des moteurs pour maintenir la vitesse sol désirée. Il est donc avantageux de voler dans les endroits présentant des vents arrière et des températures basses.

Solution

Au Laboratoire de recherche en commande active, avionique et aéroservoélasticité (LARCASE), nous résolvons le problème d’optimisation de trajectoire latérale d’avion à l’aide d’algorithmes de « recherche par graphe ».

Méthodologie

Dans un premier temps, la zone de vol est définie et discrétisée en points de cheminement. Une grille est construite, comme montré à la figure 1, où la ligne droite est la trajectoire géodésique (la plus petite distance entre deux points dans une sphère). La grille représente le graphe à résoudre.

Figure 1 Grille définissant l’espace de recherche

Les conditions météorologiques sont extraites du site Internet d’Environnement Canada. Les informations concernant le vent et la température sont assignées à chacun des points de cheminement en tenant compte de la latitude, de la longitude, de l’altitude et du moment où l’avion atteindra chacun des points de cheminement.

Figure 2 Illustration de la recherche du chemin entre un nœud de départ (coin inférieur gauche, rouge) et un nœud d’arrivée (coin supérieur droit, vert) au moyen de l’algorithme de Dijkstra pour un problème portant sur la planification de mouvement d’un robot. Les nœuds ouverts représentent l’ensemble des « possibilités ». Les nœuds remplis sont ceux visités et leur couleur est fonction de la distance, le vert étant le plus loin du point de départ. Tous les nœuds sont explorés dans différentes directions de manière uniforme, ce qui apparaît comme un front d’onde plus ou moins circulaire, l’algorithme de Dijkstra utilisant une heuristique identiquement nulle.

Comme le calcul du coût de toutes les trajectoires possibles prend beaucoup de temps, une méthode d’optimisation basée sur l’algorithme de Dijkstra a été utilisée pour ce projet de recherche. Cette méthode permet de trouver la trajectoire optimale dans un minimum de temps. Le principe de l’algorithme de Dijkstra est basé sur la détermination du chemin le plus court (ou de la trajectoire ayant le coût le plus bas pour ce projet de recherche) entre le point de départ A et celui d’arrivée B (figure 2). Cet algorithme évalue de façon systématique les sous-trajectoires et rejettera les moins avantageuses pour ne retenir que celle qui est optimale [5], et se base sur le principe de Bellman : « Toutes les sous-trajectoires qui composent une trajectoire optimale sont aussi optimales » [6].

L’algorithme mis au point au LARCASE se sert des conditions météorologiques de toutes les sous-trajectoires calculées pour en estimer le coût. Une base de données relative au rendement (PDB) nous a été fournie par notre partenaire industriel pour calculer la quantité de carburant brûlé. Cette base de données permettait d’obtenir la quantité de carburant brûlé pour de nombreuses combinaisons d’altitudes, de vitesses et de températures. Elle a été créée et validée au moyen de données expérimentales obtenues en effectuant des vols d’essai. Le LARCASE dispose de ce genre de base de données pour trois types d’avions différents.

La trajectoire optimisée a été comparée à une trajectoire de référence calculée en prenant la plus courte trajectoire (en distance) entre le point de départ et le point d’arrivée. Cette courbe est appelée « géodésique » (ou « grand cercle »). Lorsque on ne tient pas compte du vent et de la température, la trajectoire géodésique est toujours la plus économique. Par contre, dans ce projet de recherche, en tenant compte du vent et de la température, ce n’est plus toujours le cas.

Résultats

Une série de simulations a été effectuée pour deux avions différents afin d’étudier le potentiel d’optimisation de l’algorithme créé au LARCASE. De nombreux vols différents dont la date, la vitesse, l’altitude et la destination variaient ont été soumis à des analyses d’optimisation de trajectoire. La figure 3 montre la réduction de coûts obtenue par l’optimisation des vols qui ont été analysés.

Figure 3 Simulation d’optimisation de vols

Conclusion

La réduction de coût pour un vol se traduit par des économies pour les compagnies aériennes, mais aussi par une diminution de la pollution émise dans l’atmosphère.

Informations additionnelles

Les particularités de l’implantation de l’algorithme de Dijkstra et d’autres résultats obtenus lors de ce projet de recherche sont présentés dans l’article de recherche suivant :
Alejandro Murrieta-Mendoza et Ruxandra Botez, « Lateral Navigation Optimization Considering Winds and Temperatures for Fixed Altitude Cruise Using the Dijkstra’s Algorithm ». Cet article a été présenté à l’International Mechanical Engineering Congress & Exposition de l’ASME 2014 à Montréal (Canada).

Ce projet de recherche a été mené par le Laboratoire de recherche en commande active, avionique et aéroservoélasticité (LARCASE) et a été financé par le Programme des réseaux de centres d’excellence dirigés par l’entreprise GARDN (Groupement aéronautique de recherche et développement en environnement), en collaboration avec CMC Électroniques – Esterline pour encourager le développement de technologies aéronautiques vertes au Canada. D’autres approches étudiées au LARCASE pour le même type de projets de recherche peuvent être consultées à [7-15].

Si ce projet vous intéresse (ou tout autre projet de recherche du laboratoire LARCASE), consultez notre site web. N’hésitez pas à prendre rendez-vous avec le professeur Botez afin d’avoir la possibilité de discuter avec le personnel de recherche du laboratoire.