The Beam Search Algorithm to Optimize Vertical Reference Trajectories
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.
Figure 1 Lateral Reference Trajectory following the Shortest Path between Montreal and London
Figure 2. Vertical Reference Trajectory
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.
Figure 3. The Vertical Reference Trajectory Problem seen as a Graph
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.
Figure 4. In red, branches cut by heuristics. In green the optimal solution.
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.
Figure 5. Fuel Burn Savings reached with the Developed Algorithm
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.
