{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T13:54:40Z","timestamp":1770818080829,"version":"3.50.1"},"reference-count":45,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,25]],"date-time":"2020-12-25T00:00:00Z","timestamp":1608854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DFG Research Center of Excellence MATH+ - Berlin Mathematics Research Center","award":["Project AA3-3"],"award-info":[{"award-number":["Project AA3-3"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our discrete-continuous optimization for enhanced resolution (DisCOptER) method 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 governed 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.<\/jats:p>","DOI":"10.3390\/a14010004","type":"journal-article","created":{"date-parts":[[2020,12,25]],"date-time":"2020-12-25T09:30:19Z","timestamp":1608888619000},"page":"4","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Discrete-Continuous Algorithm for Free Flight Planning"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7223-9174","authenticated-orcid":false,"given":"Ralf","family":"Bornd\u00f6rfer","sequence":"first","affiliation":[{"name":"Zuse Institute Berlin, Takustra\u00dfe 7, 14195 Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8953-808X","authenticated-orcid":false,"given":"Fabian","family":"Danecker","sequence":"additional","affiliation":[{"name":"Zuse Institute Berlin, Takustra\u00dfe 7, 14195 Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1071-0044","authenticated-orcid":false,"given":"Martin","family":"Weiser","sequence":"additional","affiliation":[{"name":"Zuse Institute Berlin, Takustra\u00dfe 7, 14195 Berlin, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,25]]},"reference":[{"key":"ref_1","unstructured":"Stojkovi\u0107, S.E.K.S.S.A.G., and Stojkovi\u0107, M. (2011). Quantitative Problem Solving Methods in the Airline Industry, Springer. Chapter 6\u2014Operations."},{"key":"ref_2","unstructured":"Airbus Industries (2020, December 24). Getting to Grips with Fuel Economy. Issue 4. Available online: https:\/\/ansperformance.eu\/library\/airbus-fuel-economy.pdf."},{"key":"ref_3","unstructured":"Radio Technical Commission for Aeronautics (1995). Final Report of RTCA Task Force 3 Free Flight Implementation, RTCA."},{"key":"ref_4","unstructured":"Jelinek, F., Carlier, S., Smith, J., and Quesne, A. (2020, December 24). The EUR RVSM Implementation ProjectEnvironmental Benefit AnalysisEEC\/ENV\/ 2002\/008, Available online: https:\/\/www.eurocontrol.int\/eec\/gallery\/content\/public\/document\/eec\/report\/2002\/023_RVSM_Implementation_Project.pdf."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Ahuja, R.K., M\u00f6hring, R.H., and Zaroliagis, C.D. (2009). Time-Dependent Route Planning. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems, Springer.","DOI":"10.1007\/978-3-642-05465-5"},{"key":"ref_6","unstructured":"Bast, H., Delling, D., Goldberg, A., M\u00fcller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., and Werneck, R.F. (2020, December 24). Route Planning in Transportation Networks. Available online: https:\/\/arxiv.org\/pdf\/1504.05140.pdf."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"107697","DOI":"10.1016\/j.oceaneng.2020.107697","article-title":"Ship weather routing: A taxonomy and survey","volume":"213","author":"Zis","year":"2020","journal-title":"Ocean Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1687","DOI":"10.1155\/2016\/7426913","article-title":"Survey of Robot 3D Path Planning Algorithms","volume":"2016","author":"Yang","year":"2016","journal-title":"J. Control Sci. Eng."},{"key":"ref_9","unstructured":"Blanco, M., Bornd\u00f6rfer, R., Hoang, N.D., De las Casas, A.K.P.M., Schlechte, T., and Schlobach, S. (2017, January 7\u20138). Cost projection methods for the shortest path problem with crossing costs. Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), Vienna, Austria."},{"key":"ref_10","unstructured":"Blanco, M., Bornd\u00f6rfer, R., Hoang, N.D., Kaier, A., Schienle, A., Schlechte, T., and Schlobach, S. (2016, January 25). Solving time dependent shortest path problems on airway networks using super-optimal wind. Proceedings of the 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), Aarhus, Denmark. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/978-3-319-66158-2_23","article-title":"Constraint handling in flight planning","volume":"Volume 10416","author":"Beck","year":"2017","journal-title":"Principles and Practice of Constraint Programming"},{"key":"ref_12","first-page":"188","article-title":"Numerical Techniques for Minimum-Time Routing on a Sphere with Realistic Winds","volume":"39","author":"Marchidan","year":"2016","journal-title":"Am. Inst. Aeronaut. Astronaut."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"165","DOI":"10.2514\/1.53614","article-title":"Methods for computing minimum-time paths in strong winds","volume":"35","author":"Jardin","year":"2012","journal-title":"J. Guid. Control Dyn."},{"key":"ref_14","unstructured":"McDonald, J.A., and Zhao, Y. (2000, January 14\u201317). Time benefits of free-flight for a commercial aircraft. Proceedings of the AIAA Guidance Navigation & Control Conference, Dever, CO, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02071065","article-title":"Direct and indirect methods for trajectory optimization","volume":"37","author":"Bulirsch","year":"1992","journal-title":"Ann. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"151","DOI":"10.2514\/3.56670","article-title":"Application of direct transcription to commercial aircraft trajectory optimization","volume":"18","author":"Betts","year":"1995","journal-title":"J. Guid. Contr. Dyn."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.proeng.2014.09.083","article-title":"A Comparison of Optimal Control Methods for Minimum Fuel Cruise at Constant Altitude and Course with Fixed Arrival Time","volume":"80","author":"Soler","year":"2014","journal-title":"Procedia Eng."},{"key":"ref_18","first-page":"1","article-title":"Global optimal control with the direct multiple shooting method","volume":"39","author":"Diedam","year":"2017","journal-title":"Optim. Control Appl. Meth."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10107-007-0185-6","article-title":"Direct Methods with Maximal Lower Bound for Mixed-Integer Optimal Control Problems","volume":"118","author":"Sager","year":"2009","journal-title":"Math. Program."},{"key":"ref_20","first-page":"497","article-title":"A Survey of Numerical Methods for Optimal Control","volume":"135","author":"Rao","year":"2010","journal-title":"Adv. Astronaut. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.2514\/1.60492","article-title":"Multiphase mixed-integer optimal control approach to aircraft trajectory optimization","volume":"36","author":"Bonami","year":"2013","journal-title":"J. Guid. Control Dyn."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Moreno, L., F\u00fcgenschuh, A., Kaier, A., and Schlobach, S. (2018). A Nonlinear Model for Vertical Free-Flight Trajectory Planning. Operations Research Proceedings, Springer.","DOI":"10.1007\/978-3-319-89920-6_59"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1002\/zamm.19310110205","article-title":"\u00dcber das Navigationsproblem bei ruhender oder ver\u00e4nderlicher Windverteilung","volume":"11","author":"Zermelo","year":"1931","journal-title":"ZAMM Z. Angew. Math. Mech."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/BF01582096","article-title":"First and second-order necessary and sufficient optimality conditions for infinite-dimensional programming problems","volume":"16","author":"Maurer","year":"1979","journal-title":"Math. Program."},{"key":"ref_25","unstructured":"Pontrjagin, L., Boltyansky, V., Gamkrelidze, V., and Mischenko, E. (1962). Mathematical Theory of Optimal Processes, Wiley-Interscience."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"193","DOI":"10.2514\/2.4231","article-title":"Survey of Numerical Methods for Trajectory Optimization","volume":"21","author":"Betts","year":"1998","journal-title":"J. Guid. Control. Dyn."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"338","DOI":"10.2514\/3.20223","article-title":"Direct trajectory optimization using nonlinear programming and collocation","volume":"10","author":"Hargraves","year":"1987","journal-title":"J. Guid. Control Dyn."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"160","DOI":"10.2514\/2.4862","article-title":"Direct Trajectory Optimization by a Chebyshev Pseudospectral Method","volume":"25","author":"Fahroo","year":"2002","journal-title":"J. Guid. Control Dyn."},{"key":"ref_29","unstructured":"Ascher, U., Mattheij, R., and Russell, R. (1988). Numerical Solution of Boundary Value Problems for Ordinary Differential Equations, Prentice Hall."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0377-2217(97)00221-X","article-title":"A soft dynamic programming approach for on-line aircraft 4D-trajectory optimization","volume":"107","author":"Hagelauer","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1137\/0720042","article-title":"The conjugate gradient method and trust regions in large scale optimization","volume":"20","author":"Steihaug","year":"1983","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_32","unstructured":"Duff, I. (1981). Towards an efficient sparsity exploiting Newton method for minimization. Sparse Matrices and Their Use, Academic Press."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1080\/10556780600605129","article-title":"Affine conjugate adaptive Newton methods for nonlinear elastomechanics","volume":"22","author":"Weiser","year":"2007","journal-title":"Optim. Meth. Softw."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Deuflhard, P., and Bornemann, F. (2002). Scientific Computing with Ordinary Differential Equations, Springer. [2nd ed.]. Texts in Applied Mathematics.","DOI":"10.1007\/978-0-387-21582-2"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1137\/S0363012999351097","article-title":"Adaptive finite element methods for optimal control of partial differential equations: Basic concepts","volume":"39","author":"Becker","year":"2000","journal-title":"SIAM J. Control Optim."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1080\/10556788.2011.651469","article-title":"On goal-oriented adaptivity for elliptic optimal control problems","volume":"28","author":"Weiser","year":"2013","journal-title":"Optim. Meth. Softw."},{"key":"ref_37","unstructured":"Deuflhard, P. (2004). Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms, Springer. Computational Mathematics."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1830","DOI":"10.1137\/S0036142903434047","article-title":"Asymptotic Mesh Independence of Newton\u2019s Method Revisited","volume":"42","author":"Weiser","year":"2005","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-based algorithms for optimal motion planning","volume":"30","author":"Karaman","year":"2011","journal-title":"Int. J. Robot. Res."},{"key":"ref_40","unstructured":"Bornd\u00f6rfer, R., Danecker, F., and Weiser, M. Error Bounds for Free Flight Planning with Locally Connected Airway Networks, Zuse Institute Berlin. in preparation."},{"key":"ref_41","first-page":"259","article-title":"A set oriented approach to global optimal control","volume":"10","author":"Junge","year":"2004","journal-title":"ESAIM: Contr. Opt. Calc. Var."},{"key":"ref_42","unstructured":"Karatas, T., and Bullo, F. (2001, January 4\u20137). Randomized searches and nonlinear programming in trajectory planning. Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No.01CH37228), Orlando, FL, USA."},{"key":"ref_43","first-page":"2009","article-title":"A Hybrid Randomized\/Nonlinear Programming Technique For Small Aerial Vehicle Trajectory Planning in 3D","volume":"63","author":"Bouffard","year":"2009","journal-title":"Plan. Percept. Navig. Intell. Veh. (PPNIV)"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Brunner, M., Br\u00fcggemann, B., and Schulz, D. (2013, January 6\u201310). Hierarchical Rough Terrain Motion Planning using an Optimal Sampling-Based Method. Proceedings of the 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, Germany.","DOI":"10.1109\/ICRA.2013.6631372"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s11370-011-0092-9","article-title":"Optimal navigation in planar time-varying flow: Zermelo\u2019s problem revisited","volume":"4","author":"Techy","year":"2011","journal-title":"Intell. Serv. Robot."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/4\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:46:15Z","timestamp":1760179575000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,25]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010004"],"URL":"https:\/\/doi.org\/10.3390\/a14010004","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,25]]}}}