Anytime Stochastic Routing with Hybrid Learning

Research output: Contribution to journalConference article in JournalResearchpeer-review

19 Citations (Scopus)


Increasingly massive volumes of vehicle trajectory data hold the potential to enable higher-resolution traffic services than hitherto possible. We use trajectory data to create a high-resolution, uncertain road-network graph, where edges are associated with travel-time distributions. In this setting, we study probabilistic budget routing that aims to find the path with the highest probability of arriving at a destination within a given time budget. A key challenge is to compute accurately and efficiently the travel-time distribution of a path from the travel-time distributions of the edges in the path. Existing solutions that rely on convolution assume independence among the distributions to be convolved, but as distributions are often dependent, the result distributions exhibit poor accuracy. We propose a hybrid approach that combines convolution with estimation based on machine learning to account for dependencies among distributions in order to improve accuracy. Since the hybrid approach cannot rely on the independence assumption that enables effective pruning during routing, naive use of the hybrid approach is costly. To address the resulting efficiency challenge, we propose an anytime routing algorithm that is able to return a “good enough” path at any time and that eventually computes a high-quality path.
Empirical studies involving a substantial real-world trajectory set offer insight into the design properties of the proposed solution, indicating that it is practical in real-world settings.
Original languageEnglish
JournalProceedings of the VLDB Endowment
Issue number9
Pages (from-to)1555-1567
Number of pages13
Publication statusPublished - 1 Sep 2020
Event2020 International Conference on Very Large Databases PhD Workshop, VLDB-PhD 2020 - Online, Japan
Duration: 31 Aug 20204 Sep 2020


Conference2020 International Conference on Very Large Databases PhD Workshop, VLDB-PhD 2020


Dive into the research topics of 'Anytime Stochastic Routing with Hybrid Learning'. Together they form a unique fingerprint.

Cite this