AA3 – Networks

Project

AA3-3

Discrete-Continuous Shortest Path Problems in Flight Planning

Project Heads

Ralf Borndörfer, Martin Weiser

Project Members

Mohamed  Omari (ZIB), Fabian Danecker (ZIB) 

Project Duration

01.01.2019 – 31.12.2021

Located at

ZIB

Description

The introduction of free flight zones leads to increasing problem sizes for graph-based, discrete optimization in flight planning. Optimal control techniques scale better to higher accuracy, but produce only locally optimal solutions. We aim at combining discrete and continuous approaches next generation of flight planning.

Established flight planning involves shortest path selection in a pre-defined airway network, where effective edge lengths depend also on the wind speed at the time the plane passes that edge. In order to reduce fuel costs and air pollution, free flight zones are increasingly discussed. Removing the restriction of following the pre-defined airways allows taking better routes and exploiting advantageous wind situations more effectively. Achieving this flexibility with established graph-based optimization methods requires a massive refinement of the graph leading to significantly increased computing times.

The example of Denmark illustrates that the long-term solution to Free Flight cannot be to render the graph locally complete. As Dijkstra-based algorithms can solve time-dependent shortest path problems usually with a time-complexity of O(|E| + |V| log |V|), this quickly becomes infeasible (provided that the FIFO-property is satisfied, which is the case here). All the more so when several Free Flight airspaces are merged.

 

 

 

Continuous optimal control techniques based on discretization of ordinary differential equations scale much better than global graph-based approaches, i.e. the run time complexity in terms of the desired accuracy is much lower. Unfortunately, they compute only local optima.

 

 

The project therefore aims at

  • a theoretical understanding of the approximation and convergence properties of discrete and continuous approaches in form of error bounds,
  • the derivation of hybrid algorithms in form of a switch from discrete global to continuous local optimization at an optimal accuracy threshold, and
  • the integration of continuous optimization as a building block in more general flight planning problems including traffic flight restrictions.

Selected Publications

Selected Pictures

Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)

As Title in the above form please add a copyright.

And please give a short description of the picture and the context in the above textbox.

Don’t forget to press the “Save changes” button at the bottom of the box.

If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.