ACTUALITÉ SCIENTIFIQUE
ET INNOVATION DE L'ÉTS
L’algorithme de Dijkstra pour optimiser les trajectoires de vol - Par : Alejandro Murrieta-Mendoza, Ruxandra Botez,

L’algorithme de Dijkstra pour optimiser les trajectoires de vol


Ruxandra Botez
Ruxandra Mihaela Botez est professeure au département de génie de la production automatisée à l’ÉTS. Elle est spécialiste en modélisation et simulation de vols d’aéronefs, d’hélicoptères, de systèmes de vol, et d’ailes déformables.

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.

Dijkstra

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.

Illustration de l'algorithme de Dijkstra de recherche pour trouver le chemin d'un noeud de départ (inférieur gauche, rouge) à un noeud de but (en haut à droite, vert) dans un problème de planification de mouvement de robot. Les nœuds ouverts représentent l'ensemble "de principe". Les noeuds remplis sont ceux visités, avec la couleur représentant la distance: le vert, le plus loin. Tous les noeuds dans des directions différentes sont explorées de manière uniforme, apparaissant comme un front d'onde plus ou moins circulaire, comme l'algorithme de Dijkstra utilise une heuristique identiquement égal à 0.

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.

Dijkstra

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].

larcaseSi 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.

Auteurs

AM mendozaAlejandro Murrieta Mendoza est candidat au doctorat à l’École de technologie supérieure de Montréal (ÉTS) et assistant de recherche au Laboratoire de recherche en commande active, avionique et aéroservoélasticité (LARCASE). Ses intérêts de recherche portent sur l’optimisation des trajectoires de vol d’avion.

.

rbotezRuxandra Botez est professeure au Département de génie de la production automatisée à l’École de technologie supérieure (ÉTS). Elle est la responsable du laboratoire de recherche en commande active, avionique et aéroservoélasticité (LARCASE) et titulaire de la Chaire de recherche du Canada en technologies de modélisation et simulation des aéronefs.

[accordion title= »Références » close= »1″][1]    IATA, « Vision 2050, » International Air Transport Association, Singapore2011.
[2]    ATAG, « Aviation Befefits Beyond Borders, » Air Transport Action Group, Geneva ,SwitzerlandMarch 2013 2012.
[3]    IATA, « Beginner’s Guide to Aviation Biofuels, » International Air Transport Association, Geneva, Swissetzrland2009.
[4]    W. Freitag, Terry, Shulze E., « Blended Winglets Improve Performance, » Aeromagazine Boeing, pp. 9-12, 2009.
[5]    E. W. Dijkstra, « A note on two problems in connexion with graphs, » Numerische Mathematik, vol. 1, pp. 269-271, 1959.
[6]    R. Bellman, « On the Theory of Dynamic Programming, » Proceedings of the National Academy of Sciences, vol. 38, pp. 716-719, August 1, 1952 1952.
[7]    R. Felix-Patron, A. Kessaci, and R. Botez, « Flight trajectories optimization under the influence of winds using genetic algorithms, » presented at the AIAA Guidance, Navigation, and Control (GNC) Conference, Boston USA, 2013.
[8]    R. Felix-Patron, B. Yolène, and R. Botez, « Climb, Cruise and Descent 3D Trajectory Optimization Algorithm for the FMS CMA-9000, » in AIAA/3AF Aircraft Noise and Emissions Reduction Symposium, Atlanta, Georgia, 2014.
[9]    A. Murrieta-Mendoza, « Vertical and lateral flight optimization algorithm and missed approach cost calculation., » Master, École de Technologie Supérieure, Montreal, 2013.
[10]    Murrieta-Mendoza, Alejandro, Ruxandra Botez, and Steven Ford. « Estimation of Fuel Consumption and Polluting Emissions Generated during the Missed Approach Procedure. » 33nd IASTED International Conference on Modelling, Identification, and Control (MIC), IASTED, Innsbruck, Austria. 2014.
[11]    Murrieta-Mendoza, Alejandro, Demanage Simin, George François, Ruxandra Botez, and Steven Ford. « Estimation of Fuel Consumption and Polluting Emissions Generated during the Missed Approach Procedure. » 34th IASTED International Conference on Modelling, Identification, and Control (MIC), IASTED, Innsbruck, Austria. 2015.
[12]    Felix-Patron, R., Botez, R. M., and Labour, D. « Low calculation time interpolation method on the altitude optimization algorithm for the FMS CMA-9000 improvement on the A310 and L-1011 aircraft, » 2013 Aviation Technology, Integration, and Operations Conference. American Institute of Aeronautics and Astronautics, Los Angeles. USA, 2013.
[13]    Felix-Patron, R., and Botez, R. M. « Flight trajectory optimization through genetic algorithms coupling vertical and lateral profiles, » International Mechanical Engineering Congress & Exposition. Montreal, Canada, 2014.
[14]    Sidibe, S., and Botez, R. M. « Trajectory optimization of FMS-CMA 9000 by dynamic programming, » CASI AÉRO 2013 conference, 60th Aeronautics Conference and AGM. Toronto, Canada, 2013.
[15]    Murrieta Mendoza, A., and Botez, R. « Vertical Navigation Trajectory Optimization Algorithm For A Commercial Aircraft, » AIAA/3AF Aircraft Noise and Emissions Reduction Symposium. American Institute of Aeronautics and Astronautics, Atlanta, Georgia, 2014.
[16]    Gagné, J., Murrieta, A., Botez, R., and Labour, D. « New method for aircraft fuel saving using Flight Management System and its validation on the L-1011 aircraft, » 2013 Aviation Technology, Integration, and Operations Conference. American Institute of Aeronautics and Astronautics, Los Angeles USA, 2013.
[17]    B. Dancila, R. Botez, and Labour, D. « Fuel burn prediction algorithm for cruise, constant speed and level flight segments, » The Aeronatuical Journal Vol. 117, No. 1191, 2013.
[18]    Dancila, B., Botez, R., and Labour, D. « Altitude Optimization Algorithm for Cruise, Constant Speed and Level Flight Segments, » AIAA Guidance, Navigation, and Control Conference. American Institute of Aeronautics and Astronautics, 2012.
[19]    Félix Patrón, R. S., Berrou, Y., and Botez, R. M. « New methods of optimization of the flight profiles for performance database-modeled aircraft, » Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2014.doi: 10.1177/0954410014561772[/accordion]

[accordion title= »Références – Figures et images » close= »1″]
Image d’entête d’un « Starlifter AC-141 » produisant une trainée au dessus de l’Antarctique. Image prise par un employé du « U.S. Air Force », domaine public. Source.
Figure 1 :Murrieta-Mendoza, A., Botez, R. M. « Lateral Navigation Optimization Considering Winds And Temperatures For Fixed Altitude Cruise Using The Dijkstra’s Algorithm, » International Mechanical Engineering Congress & Exposition. Montreal, Canada, 2014.

Figure 2 de Subh83, licence CC, source.
Toutes les autres figures et images proviennent des auteurs.[/accordion]

Alejandro Murrieta-Mendoza

Profil de l'auteur(e)

Laboratoires de recherche : LARCASE – Laboratoire de recherche en commande active, avionique et aéroservoélasticité 

Profil de l'auteur(e)

Ruxandra Botez

Profil de l'auteur(e)

Ruxandra Mihaela Botez est professeure au département de génie de la production automatisée à l’ÉTS. Elle est spécialiste en modélisation et simulation de vols d’aéronefs, d’hélicoptères, de systèmes de vol, et d’ailes déformables.

Programme : Génie de la production automatisée 

Chaire de recherche : Chaire de recherche du Canada en technologies de modélisation et simulation des aéronefs 

Laboratoires de recherche : LARCASE – Laboratoire de recherche en commande active, avionique et aéroservoélasticité 

Profil de l'auteur(e)