文章基本信息

标题：Probabilistic Routing for On-Street Parking Search
本地全文：下载
作者：Tobias Arndt ; Danijar Hafner ; Thomas Kellermeier 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：57
页码：6:1-6:13
DOI：10.4230/LIPIcs.ESA.2016.6
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：parking search; on-street parking; probabilistic routing; constrained optimization; dataset