Document Open Access Logo

Towards Realistic Pedestrian Route Planning

Authors Simeon Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, Dorothea Wagner

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2015.1.pdf
  • Filesize: 1.88 MB
  • 15 pages

Document Identifiers

Author Details

Simeon Andreev
Julian Dibbelt
Martin Nöllenburg
Thomas Pajor
Dorothea Wagner

Cite As Get BibTex

Simeon Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, and Dorothea Wagner. Towards Realistic Pedestrian Route Planning. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/OASIcs.ATMOS.2015.1

Abstract

Pedestrian routing has its specific set of challenges, which are often neglected by state-of-the-art route planners. For instance, the lack of detailed sidewalk data and the inability to traverse plazas and parks in a natural way often leads to unappealing and suboptimal routes. In this work, we first propose to augment the network by generating sidewalks based on the street geometry and adding edges for routing over plazas and squares. Using this and further information, our query algorithm seamlessly handles node-to-node queries and queries whose origin or destination is an arbitrary location on a plaza or inside a park. Our experiments show that we are able to compute appealing pedestrian routes at negligible overhead over standard routing algorithms.

Subject Classification

Keywords
  • pedestrian routing
  • realistic model
  • shortest paths
  • speed-up technique

Metrics

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

References

  1. H. Alt and E. Welzl. Visibility Graphs and Obstacle-avoiding Shortest Paths. Zeitschrift für Operations Research, 32(3-4):145-164, 1988. Google Scholar
  2. Simeon Danailov Andreev. Realistic Pedestrian Routing. Bachelor thesis, Karlsruhe Institute of Technology, November 2012. Google Scholar
  3. Miquel Ginard Ballester, Maurici Ruiz Pérez, and John Stuiver. Automatic Pedestrian Network Generation. In Proceedings 14th AGILE International Conference on GIS, pages 1-13, 2011. Google Scholar
  4. 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. Technical Report abs/1504.05140, ArXiv e-prints, 2015. Google Scholar
  5. Jon Louis Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM, 18(9):509-517, September 1975. Google Scholar
  6. Raymond C. Browning, Emily A. Baker, Jessica A. Herron, and Rodger Kram. Effects of Obesity and Sex on the Energetic Cost and Preferred Speed of Walking. Journal of Applied Physiology, 100(2):390-398, 2006. Google Scholar
  7. Francisc Bungiu, Michael Hemmer, John Hershberger, Kan Huang, and Alexander Kröller. Efficient Computation of Visibility Polygons. CoRR, abs/1403.3905, 2014. Google Scholar
  8. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008. Google Scholar
  9. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable Route Planning in Road Networks. Transportation Science, 2015. Google Scholar
  10. Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. Graph Partitioning with Natural Cuts. In 25th International Parallel and Distributed Processing Symposium (IPDPS'11), pages 1135-1146. IEEE Computer Society, 2011. Google Scholar
  11. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  12. Hassan A. Karimi and Piyawan Kasemsuppakorn. Pedestrian Network Map Generation Approaches and Recommendation. International Journal of Geographical Information Science, 27(5):947-962, 2013. Google Scholar
  13. Jean-Claude Latombe. Robot Motion Planning, volume 124 of Springer International Series in Engineering and Computer Science. Springer, 1991. Google Scholar
  14. Ellips Masehian and M. R. Amin-Naseri. A Voronoi Diagram-visibility Graph-potential Field Compound Algorithm for Robot Path Planning. J. Robotic Systems, 21(6):275-300, 2004. Google Scholar
  15. M. Mokhtarzade and M.J. Valadan Zoej. Road Detection from High-Resolution Satellite Images Using Artificial Neural Networks. International Journal of Applied Earth Observation and Geoinformation, 9(1):32-40, 2007. Google Scholar
  16. M. H. Overmars and Emo Welzl. New Methods for Computing Visibility Graphs. In Proc. 4th Annu. ACM Sympos. Comput. Geom., pages 164-171, 1988. Google Scholar
  17. Scott Parker and Ellen Vanderslice. Pedestrian Network Analysis. In Walk 21 IV, Portland, OR, 2003. Google Scholar
  18. Ting Peng, Ian H. Jermyn, Veronique Prinet, and Josiane Zerubia. Extended Phase Field Higher-Order Active Contour Models for Networks. International Journal of Computer Vision, 88(1):111-128, 2010. Google Scholar
  19. Peter Sanders and Dominik Schultes. Highway Hierarchies Hasten Exact Shortest Path Queries. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05), volume 3669 of Lecture Notes in Computer Science, pages 568-579. Springer, 2005. Google Scholar
  20. J.T. Schwartz and M. Sharir. A Survey of Motion Planning and Related Geometric Algorithms. Artificial Intelligence, 37(1–-3):157-169, 1988. Google Scholar
  21. Sabine Storandt. Route Planning for Bicycles - Exact Constrained Shortest Paths Made Practical Via Contraction Hierarchy . In Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, pages 234-242, 2012. Google Scholar
  22. The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 4.6 edition, 2015. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact