License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.6
URN: urn:nbn:de:0030-drops-63489
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6348/
Arndt, Tobias ;
Hafner, Danijar ;
Kellermeier, Thomas ;
Krogmann, Simon ;
Razmjou, Armin ;
Krejca, Martin S. ;
Rothenberger, Ralf ;
Friedrich, Tobias
Probabilistic Routing for On-Street Parking Search
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.
BibTeX - Entry
@InProceedings{arndt_et_al:LIPIcs:2016:6348,
author = {Tobias Arndt and Danijar Hafner and Thomas Kellermeier and Simon Krogmann and Armin Razmjou and Martin S. Krejca and Ralf Rothenberger and Tobias Friedrich},
title = {{Probabilistic Routing for On-Street Parking Search}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {6:1--6:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-015-6},
ISSN = {1868-8969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6348},
URN = {urn:nbn:de:0030-drops-63489},
doi = {10.4230/LIPIcs.ESA.2016.6},
annote = {Keywords: parking search, on-street parking, probabilistic routing, constrained optimization, dataset}
}
|
Keywords: |
|
parking search, on-street parking, probabilistic routing, constrained optimization, dataset |
|
Collection: |
|
24th Annual European Symposium on Algorithms (ESA 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
18.08.2016 |
