**Abstract**

Flight routes are paths calculated on a network of waypoints representing 3D-coordinates. A common approach is first to calculate a path in a 2D-network, taking into account feasibility constraints, and then to optimize the altitude of the flight.

We focus on the problem of determining the vertical trajectory defined by an altitude at each waypoint of a 2D-route. The cost of an airway depends, directly, on fuel consumption and on flying time, and, indirectly, on weight and on weather conditions. These dependencies invalidate the FIFO property, which is commonly assumed for time-dependent networks. Moreover, the amount of fuel at departure has an impact on the weight and depends on the length of the route. This, therefore, needs to be decided upon for our problem. We aim at minimizing the total cost.

We study path-finding algorithms, both exact and heuristic, that we iterate in a line-search procedure to decide the fuel amount at departure. We use real-life data for the experimental analysis and conclude that on those data the assumption of the FIFO property remains a good heuristic choice.