Probabilistic Routing for On-Street Parking Search

Authors Tobias Arndt, Danijar Hafner, Thomas Kellermeier, Simon Krogmann, Armin Razmjou, Martin S. Krejca, Ralf Rothenberger, Tobias Friedrich



PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.6.pdf
  • Filesize: 5.04 MB
  • 13 pages

Document Identifiers

Author Details

Tobias Arndt
Danijar Hafner
Thomas Kellermeier
Simon Krogmann
Armin Razmjou
Martin S. Krejca
Ralf Rothenberger
Tobias Friedrich

Cite AsGet BibTex

Tobias Arndt, Danijar Hafner, Thomas Kellermeier, Simon Krogmann, Armin Razmjou, Martin S. Krejca, Ralf Rothenberger, and Tobias Friedrich. Probabilistic Routing for On-Street Parking Search. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.6

Abstract

An estimated 30% of urban traffic is caused by search for parking spots [Shoup, 2005]. Suggesting routes along highly probable parking spots could reduce traffic. In this paper, we formalize parking search as a probabilistic problem on a road graph and show that it is NP-complete. We explore heuristics that optimize for the driving duration and the walking distance to the destination. Routes are constrained to reach a certain probability threshold of finding a spot. Empirically estimated probabilities of successful parking attempts are provided by TomTom on a per-street basis. We release these probabilities as a dataset of about 80,000 roads covering the Berlin area. This allows to evaluate parking search algorithms on a real road network with realistic probabilities for the first time. However, for many other areas, parking probabilities are not openly available. Because they are effortful to collect, we propose an algorithm that relies on conventional road attributes only. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. This leads to the conclusion that conventional road attributes may be sufficient to compute reasonably good parking search routes.
Keywords
  • parking search
  • on-street parking
  • probabilistic routing
  • constrained optimization
  • dataset

Metrics

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

References

  1. Alan Agresti and Brent A. Coull. Approximate is better than "exact" for interval estimation of binomial proportions. The American Statistician, 52(2):119-126, 1998. URL: http://www.jstor.org/stable/2685469.
  2. C Richard Cassady and John E Kobza. A probabilistic approach to evaluate strategies for selecting a parking space. Transportation Science, 32(1):30-42, 1998. Google Scholar
  3. Simon Evenepoel, Jan Van Ooteghem, Sofie Verbrugge, Didier Colle, and Mario Pickavet. On-street smart parking networks at a fraction of their cost: performance analysis of a sampling approach. Transactions on Emerging Telecommunications Technologies, 25(1):136-149, 2014. Google Scholar
  4. Ming Hua and Jian Pei. Probabilistic path queries in road networks: Traffic uncertainty aware path selection. In Proceedings of the 13th International Conference on Extending Database Technology, pages 347-358, 2010. URL: http://dx.doi.org/10.1145/1739041.1739084.
  5. Gregor Jossé, Klaus Arthur Schmid, and Matthias Schubert. Probabilistic resource route queries with reappearance. In Proceedings of the 18th International Conference on Extending Database Technology, pages 445-456, 2015. URL: http://dx.doi.org/10.5441/002/edbt.2015.39.
  6. Yaron Kanza, Eliyahu Safra, and Yehoshua Sagiv. Route search over probabilistic geospatial data. In Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases, pages 153-170, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02982-0_12.
  7. Eliyahu Safra, Yaron Kanza, Nir Dolev, Yehoshua Sagiv, and Yerach Doytsher. Computing a k-route over uncertain geographical data. In Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases, pages 276-293, 2007. URL: http://dl.acm.org/citation.cfm?id=1784462.1784478.
  8. Donald Shoup. The High Cost of Free Parking. APA Planners Press, 2005. 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