Dijkstra’s algorithm to optimize flight trajectories

Problematic

Carbon Dioxide (CO2) and other pollution particles such as a Nitrogen Dioxide (NOx), hydrocarbons and water are released into the atmosphere during fossil fuel powered flights [1]. Studies suggest that in the following years the number of aircraft in service, thus the pollution of the released emissions will increment [2]. For this reason, the aeronautical industry is looking for alternatives to reduce emissions released to the atmosphere. Technological improvements such as lighter materials, new aerodynamic designs, and alternative fuels are being developed to be implemented in future generations of aircraft [3,4].

Nevertheless, because the aircraft life cycle is usually long (normally more than 20 years), it is important to find different alternatives to reduce emissions to current in-service aircraft, which will likely share the sky with the most modern aircraft in the near future. One of these alternatives is to optimize flight trajectories and traffic control procedures. This alternative is being taken seriously for two reasons. The first reason is that a higher number of aircraft in the air will require improved procedures to guarantee a safe flight, while the second reason would be the reduction of fuel burn using the most optimal trajectory to reduce flight costs. The United States with the Next Generation Air Transportation System (NextGen) and Europe with the Single European Sky ATM Research (SESAR) are currently the leaders in the air space optimization research and implementation, as shown in the videos below.

Flight trajectories are currently being optimized by ground teams before take-off and by airborne avionics such as the Flight Management System (FMS) and the Traffic Aware Planner (TAP). These devices compute optimal trajectories so that the crew can choose among them. Upon Air Traffic Control (ATC) authorization, these trajectories can be followed.

There are different parameters that can be controlled by the pilot; these parameters, such as cruise altitude and cruise speed, can affect fuel consumption and flight time. There are other stochastic parameters that also affect flight duration and consumption such as the wind and the temperature.

Temperature has an influence on engines. Normally, the warmer the environment, the more fuel the engines will require to produce the thrust needed to sustain a given flight at a given speed and altitude.

The Wind has an important influence on flight costs, and even in aircraft flight safety. The Wind can roughly be categorized into two types depending on its direction: headwind and tailwind. Because its direction is contrary to the direction of flight, headwinds have the effect of making the aircraft flying slower than the desired ground speed (speed relative to a viewer at ground). In order to reach the desired ground speed, more thrust is required from the engines to overcome the headwind effect. Tailwinds, on the other hand, following the same direction as the flight trajectory, “pushes” the aircraft, demanding less thrust from the engines to maintain the desired ground speed. For these reasons, it is desirable to fly in areas with tailwinds and low temperatures.

Solution

At the Research Laboratory in Active Controls, Avionics and Aeroservoelasticity (LARCASE), the lateral aircraft trajectory optimization problem is being solved by means of “graph search” algorithms.

Method

Firstly, the flight zone and its discretization in waypoints are defined. A grid is formed such as the one shown in Figure 1, where the straight line is the geodesic trajectory (shortest distance between two points in a sphere). This grid is the graph to be solved.

Figure 1 Grid defining the space search

The meteorological information is retrieved from the website of Environment Canada. Wind and temperature information are assigned at each waypoint taking into account the latitude, longitude, altitude and the time at which the aircraft will be at each waypoint.

Figure 2. Illustration of Dijkstra’s algorithm search for finding path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the “tentative” set. Filled nodes are visited ones, with color representing the distance: the greener, the farther. Nodes in all the different directions are explored uniformly, appearing as a more-or-less circular wavefront as Dijkstra’s algorithm uses a heuristic identically equal to 0.

Since calculating the cost of every available trajectory is time-consuming, an optimization method based on the Dijkstra’s algorithm was implemented in this research to find the optimal trajectory in a minimal time. The Dijskstra’s algorithm principle is based on solving the shortest path problem (or the trajectory with the lowest cost for this research) between the initial point A and the destination point B (figure 2). This algorithm will systematically evaluate and discard non-favorable sub-trajectories until finding the optimal one [5], and is based on the Bellman principle “In an optimal trajectory, all the sub-trajectories within it are also optimal” [6].

The algorithm developed at LARCASE takes the weather information for every sub-trajectory being calculated to estimate the flight cost. A Performance Database (PDB) was provided by our industrial partner to compute the fuel burned. This PDB has the fuel flow information for many different altitudes, speeds, and temperatures. This PDB was developed and validated with experimental flight test data. PDBs are available at LARCASE for three different aircraft.

The optimized trajectory was compared to a trajectory of reference. This reference is the shortest trajectory (in distance) between the initial point and the final point. This curve is called “geodesic” (or “great circle”). When wind or temperature are not taken into account, the geodesic trajectory always corresponds to the most economical trajectory. However, since this research takes wind and temperature into account, this is not always the case.

Results

A series of simulations were performed for two different aircraft to study the optimization potential of this algorithm developed at LARCASE. Many different flights in terms of dates, speeds, altitudes and destinations were considered in the trajectory optimization analysis. Figure 3 shows the results of the evaluated optimized flights evaluated, in terms of their costs.

Figure 3 Flight Simulation optimization

Conclusion

The flight cost reduction can be translated into savings for the airlines, but more importantly, the reduced fuel consumption lead to less pollution released into the atmosphere.

Additional information

Particularities of this implementation of the Dijkstra’s algorithm and more results of this research are available in the following article:

Alejandro Murrieta-Mendoza and Ruxandra Botez, “Lateral Navigation Optimization Considering Winds and Temperatures for Fixed Altitude Cruise Using the Dijkstra’s Algorithm”. This article was presented at the ASME 2014 International Mechanical Engineering Congress & Exposition in Montreal, Canada in 2014.

This research was conducted at the Research Laboratory in Active Controls, Avionics and Aeroservoelasticity (LARCASE) and was funded by the Business-Led Network Center of Excellence GARDN 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 [7-15].

If anyone would like to collaborate on this research, or on any other research project at the laboratory of Applied Research LARCASE, please visit the website and do not hesitate to make an appointment with professor Botez to talk with the research staff.