## ABSTRACT

Today, aircraft are vital to the world economic development, however they require an important quantity of fuel to power flights. One way of reducing fuel burn during a flight is to provide a flight reference trajectory that requires minimal fuel consumption. At the Research Laboratory in Active Controls, Avionics and Aeroservoelasticity (LARCASE), an algorithm called the beam search algorithm was implemented to find the most economical combinations of speeds and altitudes for the vertical reference trajectory. Observations showed that, in most cases, the algorithm was able to find the optimal solution, which provided fuel savings of up to 2.99%.

**Key Words: Trajectory, Optimization, Commercial Aircraft, Pollution, CO2, Fuel, Beam Search, Branch and Bound, Flight Management System.**

## INTRODUCTION

Today, aircraft are vital to the world economic development. As it was reported by the Air Transport Action Group [1] in 2012, aircraft transported a third of the world’s trade cargo in value. Also, more than half of the people traveling to other countries did so by aircraft as this means of transportation is the fastest and most convenient means of traveling long distances. However, important quantities of fuel are required in order to power flight. When fuel is consumed, it produces polluting particles such as Carbon dioxide (CO2), Nitrogen Oxides (NOx), hydrocarbons, water vapor, etc. All these polluting particles deplete the ozone layer, add to the greenhouse effect, or are harmful to the population. Presently, a global aeronautical goal is to reduce CO2 emissions in 2050 by 50%, compared to the recorded levels in 2005 [2].

One way of reducing fuel burn during a flight is to provide a flight reference trajectory that requires minimal fuel consumption. The flight reference trajectory can be divided into the lateral reference trajectory and the vertical reference trajectory. The lateral reference trajectory consists of the latitude/longitude waypoints over a map. The lateral reference trajectory is also known as a ground track since it guides the aircraft over the Earth’s surface, as shown in Figure 1. The vertical reference trajectory consists in finding the speeds and altitudes at which the aircraft should fly when crossing every waypoint, as shown in Figure 2.

Trajectories are normally optimized before take-off; however, an avionics device called a Flight Management System (FMS) can optimize the reference trajectory once the aircraft is airborne. Different algorithms have been developed at LARCASE to optimize the vertical reference flight trajectories either before take-off or once the aircraft is flying to its destination.

## METHODOLOGY

At the LARCASE, an algorithm was developed to find the most economical combinations of speeds and altitudes for the vertical reference trajectory. This algorithm takes into account the whole flight (climb, cruise and descent phases), weather, air traffic constraints, cruise altitude changes, and a numerical performance model obtained from experimental flight data that provides the fuel burn.

The combination of speeds and altitudes that define the vertical reference trajectory can be arranged under the form of a graph as shown in Figure 3, where each level represents either the initial climb speed (IAS Climb), the Mach number, the initial cruise altitude, or the IAS Descent Speed. A graph search algorithm called beam search was implemented in order to find the most economical combination of nodes that define the vertical reference trajectory.

Beam search is a variation of the well-known branch and bound algorithm, where a function able to estimate the flight cost with minimal information (called heuristic) is used to predict the minimal fuel burn when visiting a given node. The algorithm systematically visits nodes (of the current level) and compares the heuristic flight cost against the current most economic reference cost. If the heuristic cost at a certain node is more expensive than the reference cost, that node and the nodes below that node are discarded. If the heuristic cost is lower than the reference cost, the next level is expanded and every node (of this next level) is analyzed. When the algorithm is evaluating the nodes at the last tree level all the elements required to compute the flight cost are known. For this reason, a time-consuming method able to compute an accurate flight cost is executed. If the computed flight cost is more economical than the actual reference cost, the new computed flight cost becomes the current most economic cost.

Heuristics are the most important aspect of this algorithm as they are used to discard parts of the graph tree that are unlikely to give the most economical fuel burn. By cutting parts of the tree, it is possible to quickly converge to the optimal or a really good sub-optimal solution. For example, the branches cut by the heuristics are in red, and the optimal solutions are shown in green on Figure 4.

The tree part in red was eliminated because its heuristic cost was higher than the current most economical solution. The green part represented a solution that remained to be analyzed. Since the green part is at the last tree level, its corresponding flight cost is not computed with the heuristic.

## RESULTS

Different flights were evaluated in order to find the most economical vertical reference trajectory for a 2-engine long-haul aircraft with a capacity of approximately 220 passengers.

The first set of results consisted in comparing the optimal solution delivered by the developed algorithm against the optimal solution. The goal of this test was to observe the cost difference between the global optimal solution, and the solution provided by the algorithm. It was observed that in most cases, the developed algorithm was able to find the optimal solution. When the algorithm did not find the optimal solution, the highest recorded cost difference was only 0.4%. This value was considered acceptable as the algorithm provided a solution faster than following the evaluation of all possible combinations.

The second set of results consisted in comparing the solution provided by the developed algorithm with the solution provided by the optimization algorithm loaded in a commercial Flight Management System. The same flight was evaluated under the same conditions by using these two algorithms. For all cases, the developed algorithm provided more efficient trajectories than the FMS algorithm. The optimization percentage can be seen in Figure 5.

The fuel savings represent fuel that was not used, thus pollution for those flights that was not released. Besides, this high fuel savings percentage represents savings for airlines, giving them the possibility to invest fuel money in other projects.

A more detailed explanation of this algorithm and more results of this research are available in the following article:

Alejandro Murrieta-Mendoza, Bruce Beuze, Laurane Ternisien and Ruxandra Botez, “Branch & Bound-Based Algorithm for Aircraft VNAV Profile Reference Trajectory Optimization”. This article was presented at the 15th AIAA Aviation Technology, Integration, and Operations Conference, AIAA AVIATION 2015 Forum in Dallas, Texas in 2015.

This research was conducted at the Research Laboratory in Active Controls, Avionics and Aeroservoelasticity (LARCASE) and was funded within the GARDN Business-Led Networks of Centers of Excellence, in collaboration with CMC Electronics – Esterline, to encourage Greener Aircraft Technology Achievements in Canada. Other approaches of this type of research at LARCASE can be found in [3] – [14].

If you would like to be involved in this research, or any other research project at the laboratory of Applied Research in Active Controls, Avionics and AeroServoElasticity (LARCASE), please visit the website, and do not hesitate to make an appointment with Professor Botez to talk with the research staff.

## Authors

Alejandro Murrieta-Mendoza is a PhD Student at the École de technologie supérieure (ÉTS) in Montréal, and Research Assistant at the Laboratory in Active Controls, Avionics and Aeroservoelasticity (LARCASE). He is conducting research in aircraft flight trajectory optimization.

Bruce Beuze completed a 6-month professional internship as EPF Master Student at the École de technologie supérieure (ÉTS) and as Research Assistant at the Laboratory of Applied Research in Active Controls, Avionics and Aeroservoelasticity (LARCASE). He worked on trajectory optimization and flight control. Bruce recently obtained his Master of Aeronautical and Space Engineering from the EPF Engineering School in France.

Laurane Ternisien is an Engineer in the Aerospace Sector in France. She finalized a 6-month professional internship as EPF Bachelor Student at the École de technologie Superieure (ÉTS) and as Research Assistant at the Laboratory in Active Controls, Avionics and Aeroservoelasticity (LARCASE).

Dr. Ruxandra Botez is Full Professor at the Department of Automated Manufacturing Engineering at École de technologie supérieure (ÉTS). She is Founder and Head of the Research Laboratory in Active Controls, Avionics and Aeroservoelasticity (LARCASE) and Holder of the Canada Research Chair Tier 1 in Aircraft Modeling and Simulation Technologies.

### Références

[1] ATAG. “Aviation Benefits Beyond Borders.” Air Transport Action Group, Geneva, Switzerland, 2013.

[2] ICAO. “Aviation’s contribution to climate change.” International Civil Aviation Organization, Montreal, 2010, p. 260.

[3] Murrieta-Mendoza, A., Ruiz, S., Kessaci, S., and Botez, R. M. “Vertical Reference Flight Trajectory Optimization with the Particle Swarm Optimisation,” The 36th IASTED International Conference on Modelling, Identification and Control (MIC 2017). Innsbrunck, Austria, 2017.

[4] Murrieta-Mendoza, A., Mugnier, P., and Botez, R. M. “Vertical Reference Trajectory Optimization and Simulation for a Commercial Aircraft,” 11th International Conference on Modelling, Optimization and Simulation – MOSIM’16. Montreal, QC, Canada, 2016.

[5] Murrieta-Mendoza, A., Botez, R. M., and Ford, S. “New method to compute the missed approach fuel consumption and its emissions,” The Aeronautical Journal Vol. 120, No. 1228, 2016, p. 18. doi: http://dx.doi.org/10.1017/aer.2016.37

[6] Murrieta-Mendoza, A., Félix-Patrón, R. S., and Botez, R. M. “Flight Altitude Optimization Using Genetic Algorithms Considering Climb and Descent Costs in Cruise with Flight Plan Information,” SAE 2015 AeroTech Congress & Exhibition. SAE International, Seattle, USA, 2015, p. 9. doi: http://dx.doi.org/10.4271/2015-01-2542

[7] Murrieta-Mendoza, A., and Botez, R. M. “Aircraft Vertical Route Optimization Deterministic Algorithm for a Flight Management System,” SAE 2015 AeroTech Congress & Exhibition. Vol. SAE Technical Paper 2015-01-2541, SAE International, Seattle, USA, 2015, p. 13. doi: http://dx.doi.org/10.4271/2015-01-2541

[8] Murrieta Mendoza, A., Felix-Patron, R. S., and Botez, R. M. “Genetic Algorithm for Altitude Optimization during Cruise,” AHS Sustainability 2015. Montreal, Canada, 2015.

[9] Félix-Patrón, R. S., and Botez, R. M. “Flight Trajectory Optimization Through Genetic Algorithms for Lateral and Vertical Integrated Navigation,” Journal of Aerospace Information Systems Vol. 12, No. 8, 2015, pp. 533-544. doi: http://dx.doi.org/10.2514/1.I010348

[10] Murrieta-Mendoza, A., and Botez, R. M. “Vertical Navigation Trajectory Optimization Algorithm For A Commercial Aircraft,” AIAA/3AF Aircraft Noise and Emissions Reduction Symposium, 2014. doi: http://dx.doi.org/10.2514/6.2014-3019

[11] 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

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

[13] Dancila, B., Botez, R. M., and Labour, D. “Fuel Burn Prediction Algorithm for Cruise, Constant Speed and Level Flight Segments,” The Aeronatuical Journal Vol. 117, No. 1191, 2013.

[14] Felix Patron, R. S., Botez, R. M., and Labour, D. “New Altitude Optimisation Algorithm for the Flight Management System CMA-9000 Improvement on the A310 and L-1011 Aircraft,” The Aeronautical Journal Vol. 117, No. 1194, 2013, pp. 787-805.

### Image References

The featured image was bought on Istock.com. Copyrights. Other images are from the authors. Substance CC License applies.