Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind

Authors Marco Blanco, Ralf Borndörfer, Nam-Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, Swen Schlobach



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.12.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Marco Blanco
Ralf Borndörfer
Nam-Dung Hoang
Anton Kaier
Adam Schienle
Thomas Schlechte
Swen Schlobach

Cite AsGet BibTex

Marco Blanco, Ralf Borndörfer, Nam-Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. 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 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/OASIcs.ATMOS.2016.12

Abstract

We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.
Keywords
  • shortest path problem
  • A*
  • flight trajectory optimization
  • preprocessing
  • contraction hierarchies
  • time-dependent shortest path problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Algorithms - ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, chapter Hierarchical Hub Labelings for Shortest Paths, pages 24-35. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. Google Scholar
  2. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. CoRR, abs/1504.05140, 2015. Google Scholar
  3. G. Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. Minimum time-dependent travel times with contraction hierarchies. J. Exp. Algorithmics, 18:1.4:1.1-1.4:1.43, April 2013. Google Scholar
  4. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. J. Exp. Algorithmics, 15:2.3:2.1-2.3:2.31, March 2010. Google Scholar
  5. Pierre Bonami, Alberto Olivares, Manuel Soler, and Ernesto Staffetti. Multiphase mixed-integer optimal control approach to aircraft trajectory optimization. Journal of Guidance, Control, and Dynamics, 36(5):1267-1277, July 2013. Google Scholar
  6. H.M. de Jong. Optimal track selection and 3-dimensional flight planning. Technical Report 93, Royal Netherlands Meteorological Institute, 1974. Google Scholar
  7. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Robust exact distance queries on massive networks. Technical Report MSR-TR-2014-12, July 2014. Google Scholar
  8. Daniel Delling and Dorothea Wagner. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems, chapter Time-Dependent Route Planning, pages 207-230. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. Google Scholar
  9. EUROCONTROL. Route availability document, 2016. [Online; accessed 2-June-2016]. URL: https://www.nm.eurocontrol.int/RAD/.
  10. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388-404, August 2012. Google Scholar
  11. A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. Technical Report MSR-TR-2004-24, Microsoft Research, Vancouver, Canada, July 2004. Google Scholar
  12. P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, July 1968. Google Scholar
  13. Stefan E. Karisch, Stephen S. Altus, Goran Stojković, and Mirela Stojković. Operations. In Cynthia Barnhart and Barry Smith, editors, Quantitative Problem Solving Methods in the Airline Industry, volume 169 of International Series in Operations Research &Management Science, pages 283-383. Springer US, 2012. Google Scholar
  14. Giacomo Nannicini, Daniel Delling, Dominik Schultes, and Leo Liberti. Bidirectional a* search on time-dependent road networks. Netw., 59(2):240-251, March 2012. Google Scholar
  15. Peter Sanders, Moritz Kobitzsch, Veit Batz, Robert Geisberger, Dennis Luxen, Dennis Schieferdecker, Dominik Schultes, and Christian Vetter. Fast and exact route planning, 2016. [Online; accessed 2-June-2016]. URL: http://algo2.iti.kit.edu/routeplanning.php.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail