@phdthesis{Danecker2023, author = {Danecker, Fabian}, title = {A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization}, year = {2023}, abstract = {This thesis introduces the novel hybrid algorithm DisCOptER for globally optimal flight planning. DisCOptER (Discrete-Continuous Optimization for Enhanced Resolution) com- bines discrete and continuous optimization in a two-stage approach to find optimal trajectories up to arbitrary precision in finite time. In the discrete phase, a directed auxiliary graph is created in order to define a set of candidate paths that densely covers the relevant part of the trajectory space. Then, Yen's algorithm is employed to identify a set of promising candidate paths. These are used as starting points for the subsequent stage in which they are refined with a locally convergent optimal control method. The correctness, accuracy, and complexity of DisCOptER are intricately linked to the choice of the switch-over point, defined by the discretization coarseness. Only a sufficiently dense graph enables the algorithm to find a path within the convex domain surrounding the global minimizer. Initialized with such a path, the second stage rapidly converges to the optimum. Conversely, an excessively dense graph poses the risk of overly costly and redundant computations. The determination of the optimal switch-over point necessitates a profound understanding of the local behavior of the problem, the approximation properties of the graph, and the convergence characteristics of the employed optimal control method. These topics are explored extensively in this thesis. Crucially, the density of the auxiliary graph is solely dependent on the en- vironmental conditions, yet independent of the desired solution accuracy. As a consequence, the algorithm inherits the superior asymptotic convergence properties of the optimal control stage. The practical implications of this computational efficiency are demonstrated in realistic environments, where the DisCOptER algorithm consistently delivers highly accurate globally optimal trajectories with exceptional computational efficiency. This notable improvement upon existing approaches underscores the algorithm's significance. Beyond its technical prowess, the DisCOptER algorithm stands as a valuable tool contributing to the reduction of costs and the overall enhancement of flight operations efficiency.}, language = {en} } @article{BorndoerferDaneckerWeiser2021, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Free Flight Planning}, volume = {14}, journal = {Algorithms}, number = {1}, publisher = {MDPI}, issn = {1438-0064}, doi = {10.3390/a14010004}, pages = {4}, year = {2021}, abstract = {We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.}, language = {en} } @inproceedings{BorndoerferDaneckerWeiser2023, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {Convergence Properties of Newton's Method for Globally Optimal Free Flight Trajectory Optimization}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, doi = {10.4230/OASIcs.ATMOS.2023.3}, pages = {3:1 -- 3:6}, year = {2023}, abstract = {The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.}, language = {en} } @article{BorndoerferDaneckerWeiser2023, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {Newton's Method for Global Free Flight Trajectory Optimization}, volume = {4}, journal = {Operations Research Forum}, doi = {10.1007/s43069-023-00238-z}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91846}, year = {2023}, abstract = {Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case.}, language = {en} } @article{BorndoerferDaneckerWeiser2023, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {Error Bounds for Discrete-Continuous Free Flight Trajectory Optimization}, volume = {198}, journal = {Journal of Optimization Theory and Applications}, doi = {10.1007/s10957-023-02264-7}, pages = {830 -- 856}, year = {2023}, abstract = {Flight planning, the computation of optimal routes in view of flight time and fuel consumption under given weather conditions, is traditionally done by finding globally shortest paths in a predefined airway network. Free flight trajectories, not restricted to a network, have the potential to reduce the costs significantly, and can be computed using locally convergent continuous optimal control methods. Hybrid methods that start with a discrete global search and refine with a fast continuous local optimization combine the best properties of both approaches, but rely on a good switchover, which requires error estimates for discrete paths relative to continuous trajectories. Based on vertex density and local complete connectivity, we derive localized and a priori bounds for the flight time of discrete paths relative to the optimal continuous trajectory, and illustrate their properties on a set of benchmark problems. It turns out that localization improves the error bound by four orders of magnitude, but still leaves ample opportunities for tighter bounds using a posteriori error estimators.}, language = {en} } @inproceedings{BorndoerferDaneckerWeiser2022, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, doi = {10.4230/OASIcs.ATMOS.2022.2}, pages = {1 -- 13}, year = {2022}, abstract = {We present an efficient algorithm that finds a globally optimal solution to the 2D Free Flight Trajectory Optimization Problem (aka Zermelo Navigation Problem) up to arbitrary precision in finite time. The algorithm combines a discrete and a continuous optimization phase. In the discrete phase, a set of candidate paths that densely covers the trajectory space is created on a directed auxiliary graph. Then Yen's algorithm provides a promising set of discrete candidate paths which subsequently undergo a locally convergent refinement stage. Provided that the auxiliary graph is sufficiently dense, the method finds a path that lies within the convex domain around the global minimizer. From this starting point, the second stage will converge rapidly to the optimum. The density of the auxiliary graph depends solely on the wind field, and not on the accuracy of the solution, such that the method inherits the superior asymptotic convergence properties of the optimal control stage.}, language = {en} } @misc{BorndoerferDaneckerWeiser2020, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Free Flight Planning}, issn = {1438-0064}, doi = {10.3390/a14010004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81343}, year = {2020}, abstract = {We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.}, language = {en} } @inproceedings{BorndoerferJocasWeiser2026, author = {Bornd{\"o}rfer, Ralf and Jocas, Arturas and Weiser, Martin}, title = {An Eikonal Approach for Globally Optimal Free Flight Trajectories}, arxiv = {http://arxiv.org/abs/2603.11830}, year = {2026}, abstract = {We present an eikonal-based approach that is capable of finding a continuous globally optimal trajectory for an aircraft in a stationary wind field. This minimizes emissions and fuel consumption. If the destination is close to a cut locus of the associated Hamilton-Jacobi-Bellman equation, small numerical discretization errors can lead to selecting a merely locally optimal trajectory and missing the globally optimal one. Based on finite element error estimates, we construct a trust region around the cut loci in order to guarantee uniqueness of trajectories for destinations sufficiently far from cut loci.}, language = {en} }