Flight planning is concerned with the computation of time and fuel efficient flight paths with respect to the weather, see [1
] for a comprehensive survey. In particular, wind conditions make a big difference: flying with a headwind of 60 kts increases flight time and fuel consumption of an Airbus A321 by as much as 20% over a tailwind of 60 kts [2
]. To exploit this potential, and to mitigate airspace congestion, free flight aircraft routing has been suggested since 1995 [3
], and projects to complement, enhance, and finally replace the airway network that is currently used to organize all air traffic are now under way all over the world. Europe is introducing so-called free route airspaces (FRAs), in which one can fly on arbitrary straight lines between defined entry and exit points, and between more and more intermediate points, moving ever closer towards free flight. According to EUROCONTROL, FRA projects are now in place in three quarters of all European airspaces, and, once fully implemented, will save total fuel burn, CO2
, and H2
O emissions by 1.6–2.3%, which amounts to 3000 tonnes of fuel/day, 10,000 tonnes of CO2
/day, €3 million in fuel costs/day, and 500,000 nautical miles/day [4
The flight planning problem can be seen as a special type of time-dependent shortest path problem. A large number of algorithms has been developed in this general context, including contraction hierarchies, hub labeling, and arc flags for route planing in road networks, see [5
] for surveys, RAPTOR, transfer patterns, and connection scan for journey planning in public transport networks [6
], the isochrones method and dynamic programming for ship weather routing [7
], and sampling-based algorithms like rapidly exploring random graphs and trees (RRTs), probabilistic road maps (PRMs), artificial potential fields, as well as graph-based algorithms such as
, theta*, etc. for robot path planning [8
]. The variety of these methods reflects the different characteristics of the respective problems.
The best flight planning methods are currently super-fast
/Dijkstra algorithms that employ efficient problem specific speed-up techniques such as cost projection [9
], super-optimal wind [10
], and active constraint propagation [11
]. They can find globally 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.
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 Pontryagin’s maximum principle [12
], or by direct methods using a collocation discretization to reformulate the problem as a nonlinear program (NLP) [16
]. 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 Newton’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. Section 2.1
, Section 2.2
, Section 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.