optimal solutions of basic problem variants on the world wide airway network with its 100,000 nodes and 600,000-700,000 edges within milliseconds. \(A^{*}\) methods can in principle be extended to deal with FRAs or free flight by excessive graph augmentation, but only up to a certain point, when the graphs become too large and dense.  
On the other hand, numerical methods of optimal control are able to compute optimal free flight trajectories to high precision with great efficiency, either with indirect methods based on [PERSON]'s maximum principle [12; 13; 14; 15], or by direct methods using a collocation discretization to reformulate the problem as a nonlinear program (NLP) [16; 17]. These methods compute a smooth trajectory independently of any a priori network discretization, i.e., the desired free flight path. The computational complexity of solving the optimality systems by [PERSON]'s method is asymptotically much smaller than for graph discretizations. If measured in terms of accuracy, higher order discretizations of the underlying ordinary differential equations exhibit even larger asymptotic gains. The drawback is that continuous optimal control methods converge only locally, and towards any local optimum, without providing any guarantee of global optimality. Approaches to compute globally optimal solutions to optimal control problems include global optimal control [18], mixed-integer optimal control [19], and various heuristics [20]. Applications to flight planning exist, but consider only very small networks [21] or vertical profiles [22].  
We propose in this paper the novel hybrid algorithm discrete-continuous optimization for enhanced resolution (DisCOptER) that combines the strengths of discrete and continuous approaches to flight planning, and provide a numerical study of its efficiency and accuracy. The discrete component of our method provides global optimality, the continuous component high accuracy and asymptotic efficiency. The idea of the method is to do a discrete search for a global optimum on a coarse, approximate, artificial network, and to use the resulting approximate solution to initialize a Newton method for the solution of a continuous optimal control problem. The correctness and effectiveness of this strategy depends on the choice of the crossover point between the discrete and the continuous part of the algorithm. The network for the discrete part must be coarse enough to be searched efficiently, and fine enough to guarantee sufficient proximity to the continuous optimum, such that a subsequent Newton iteration will converge to the latter. Clearly, the convergence radius of the continuous method strongly depends on the gradients of the wind field and affects, together with the approximation error associated with the graph, the computational complexity of both methods. We shall show that this idea is ideally suited for free flight settings.  
Our aim in this paper is to demonstrate the potential of combining discrete and continuous optimization methods for the solution of problems that involve space or time discretizations. The goal is to achieve global optimality and rapid convergence at the same time. The model that we consider is simple, and the special characteristics of flight planning have left their imprint. The basic idea, however, should, with suitable modifications, be applicable to various problems of similar nature. In this vein, our paper intends to give a first indication of the usefulness of such approaches.  
The paper is structured as follows. Sections 2.1-2.3 describe the free flight problem that we consider. The DisCOptER algorithm is introduced in Section 2.4 including error and complexity estimates. Finally, Section 3 provides a computational study and analyzes the choice of the switch over point.