Abstract
Flight routes are paths in a network, the nodes of which represent waypoints in a 3D space. A common approach to route planning is first to calculate a cheapest path in a 2D space, and then to optimize the flight cost in the third dimension. We focus on the problem of finding a cheapest path through a network describing the 2D projection of the 3D waypoints. In European airspaces, traffic flow is handled by heavily constraining the flight network. The constraints can have very diverse structures, among them a generalization of the forbidden pairs type. They invalidate the FIFO property, commonly assumed in shortest path problems. We formalize the problem and provide a framework for the description, representation and propagation of the constraints in path finding algorithms, best-first, and A\(^*\) search. In addition, we study a lazy approach to deal with the constraints. We conduct an experimental evaluation based on real-life data and conclude that our techniques for constraint propagation work best together with an iterative search approach, in which only constraints that are violated in previously found routes are introduced in the constraint set before the search is restarted.
K.S. Larsen—was supported in part by the Danish Council for Independent Research, Natural Sciences, grant DFF-1323-00247.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The total cost is calculated as a weighted sum of time and fuel consumed. In our specific case, we have used 3$ per gallon of fuel and 1000$ per hour.
- 2.
Note that a more accurate determination of subsumption between two trees, accurately reflecting semantic logical implication, would require solving a subgraph isomorphism that can be quite costly due to its NP-completeness.
- 3.
The cost index is an efficiency ratio between the time-related cost and the fuel cost that airlines use to specify how to operate the aircraft, determining the speed of the aircraft. It is decided upon at a strategic level and cannot be changed during the planning phase.
References
Knudsen, A.N., Chiarandini, M., Larsen, K.S.: Vertical optimization of resource dependent flight paths. In: Twentysecond European Conference on Artificial Intelligence (ECAI). Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 639–645. IOS Press (2016)
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, M., Sanders, T., Wagner, D., Werneck, R.F.: Route planning in transportation networks. Technical report. arXiv:1504.05140 [cs.DS] (2015)
Olivares, A., Soler, M., Staffetti, E.: Multiphase mixed-integer optimal control applied to 4D trajectory planning in air traffic management. In: Proceedings of the 3rd International Conference on Application and Theory of Automation in Command and Control Systems (ATACCS), pp. 85–94. ACM (2013)
de Jong, H.M.: Optimal Track Selection and 3-Dimensional Flight Planning: Theory and Practice of the Optimization Problem in air Navigation Under Space-Time Varying Meteorological Conditions. Staatsuitgeverij, Madison (1974)
Blanco, M., Borndörfer, R., Hoang, N.-D., Kaier, A., Schienle, A., Schlechte, T., Schlobach, S.: Solving time dependent shortest path problems on airway networks using super-optimal wind. In: 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), pp. 12:1–12:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2016)
Yinnone, H.: On paths avoiding forbidden pairs of vertices in a graph. Discret. Appl. Math. 74(1), 85–92 (1997)
Kováč, J.: Complexity of the path avoiding forbidden pairs problem revisited. Discret. Appl. Math. 161(10–11), 1506–1512 (2013)
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Hooker, J.N., Ottosson, G.: Logic-based benders decomposition. Math. Program. 96(1), 33–60 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Knudsen, A.N., Chiarandini, M., Larsen, K.S. (2017). Constraint Handling in Flight Planning. In: Beck, J. (eds) Principles and Practice of Constraint Programming. CP 2017. Lecture Notes in Computer Science(), vol 10416. Springer, Cham. https://doi.org/10.1007/978-3-319-66158-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-66158-2_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-66157-5
Online ISBN: 978-3-319-66158-2
eBook Packages: Computer ScienceComputer Science (R0)