A Discrete-Continuous Algorithm for Free Flight Planning

Please always quote using this URN: urn:nbn:de:0297-zib-81343
  • 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.

Download full text files

Export metadata

Metadaten
Author:Ralf BorndörferORCiD, Fabian DaneckerORCiD, Martin WeiserORCiD
Document Type:ZIB-Report
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]
Date of first Publication:2020/12/20
Series (Serial Number):ZIB-Report (20-33)
ISSN:1438-0064
Published in:Algorithms
DOI:https://doi.org/10.3390/a14010004