A Discrete-Continuous Algorithm for Free Flight Planning

  • 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.
Metadaten
Author:Ralf BorndörferORCiD, Fabian DaneckerORCiD, Martin WeiserORCiD
Document Type:Article
Parent Title (English):Algorithms
Volume:14
Issue:1
First Page:4
Publisher:MDPI
Tag:discrete optimization; discrete-continuous algorithm; flight planning; free flight; optimal control; shortest path
MSC-Classification:49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX] / 49Mxx Numerical methods [See also 90Cxx, 65Kxx] / 49M37 Methods of nonlinear programming type [See also 90C30, 65Kxx]
65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K10 Optimization and variational techniques [See also 49Mxx, 93B40]
65-XX NUMERICAL ANALYSIS / 65Lxx Ordinary differential equations / 65L10 Boundary value problems
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
Year of first publication:2021
ISSN:1438-0064
Preprint:urn:nbn:de:0297-zib-81343
DOI:https://doi.org/10.3390/a14010004