Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Probabilistic Routing for On-Street Parking Search

This project is based on cooperation with TomTom. It revolved around quickly finding a parking spot and resulted a paper accepted at the 24th European Symposium on Algorithms (ESA). This page contains the datasets we used in this work.

Authors

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

Abstract

An estimated 30 % of urban traffic is caused by searching for parking spots.  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.

Datasets

Due to license restrictions, the following data is currently only available upon request:

  • TomTom Map data for the Berlin area
  • Parking probabilities per edge

We plan to release this data as a license-free download based on public Open Street Maps in the near future.

Heatmap
A heatmap of the probability densities in the Berlin area between 9 p.m. and 6 a.m., averaged over all days of the week. Red roads represent low densities, green roads high densities.