TY - JOUR A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - Error Bounds for Discrete-Continuous Free Flight Trajectory Optimization JF - Journal of Optimization Theory and Applications N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1007/s10957-023-02264-7 VL - 198 SP - 830 EP - 856 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - Newton's Method for Global Free Flight Trajectory Optimization JF - Operations Research Forum N2 - 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. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91846 VL - 4 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - A Discrete-Continuous Algorithm for Free Flight Planning JF - Algorithms N2 - 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. KW - shortest path KW - flight planning KW - free flight KW - discrete-continuous algorithm KW - optimal control KW - discrete optimization Y1 - 2020 U6 - https://doi.org/10.3390/a14010004 SN - 1438-0064 VL - 14 IS - 1 SP - 4 PB - MDPI ER -