Fast stochastic routing under time-varying uncertainty

Research output: Contribution to journalJournal articleResearchpeer-review

5 Citations (Scopus)


Data are increasingly available that enable detailed capture of travel costs associated with the movements of vehicles in road networks, notably travel time, and greenhouse gas emissions. In addition to varying across time, such costs are inherently uncertain, due to varying traffic volumes, weather conditions, different driving styles among drivers, etc. In this setting, we address the problem of enabling fast route planning with time-varying, uncertain edge weights. We initially present a practical approach to transforming GPS trajectories into time-varying, uncertain edge weights that guarantee the first-in-first-out property. Next, we propose time-dependent uncertain contraction hierarchies (TUCHs), a generic speed-up technique that supports a wide variety of stochastic route planning functionality in the paper’s setting. In particular, we propose query processing methods based on TUCH for two representative types of stochastic routing: non-dominated routing and probabilistic budget routing. Experimental studies with a substantial GPS data set offer insight into the design properties of the paper’s proposals and suggest that they are capable of enabling efficient stochastic routing.
Original languageEnglish
JournalThe VLDB Journal
Issue number4
Pages (from-to)819-839
Number of pages21
Publication statusPublished - 1 Jul 2020


  • Contraction hierarchies
  • First-in-first-out
  • Stochastic routing
  • Time dependency
  • Trajectories
  • Uncertainty

Fingerprint Dive into the research topics of 'Fast stochastic routing under time-varying uncertainty'. Together they form a unique fingerprint.

Cite this