Fast stochastic routing under time-varying uncertainty

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

3 Citationer (Scopus)

Abstrakt

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.
OriginalsprogEngelsk
TidsskriftThe VLDB Journal
Vol/bind2019
Sider (fra-til)1-21
Antal sider21
ISSN1066-8888
DOI
StatusE-pub ahead of print - 2019

Citationsformater