Fast stochastic routing under time-varying uncertainty

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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 languageUndefined/Unknown
JournalThe VLDB Journal
Pages (from-to)1-21
Number of pages21
ISSN1066-8888
DOIs
Publication statusPublished - 31 Oct 2019

Cite this

@article{93e20b64ad2a428d920c40e408e3f886,
title = "Fast stochastic routing under time-varying uncertainty",
abstract = "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.",
author = "Pedersen, {Simon Aagaard} and Bin Yang and Jensen, {Christian S.}",
year = "2019",
month = "10",
day = "31",
doi = "10.1007/s00778-019-00585-6",
language = "Udefineret/Ukendt",
pages = "1--21",
journal = "V L D B Journal",
issn = "1066-8888",
publisher = "Springer",

}

Fast stochastic routing under time-varying uncertainty. / Pedersen, Simon Aagaard; Yang, Bin; Jensen, Christian S.

In: The VLDB Journal, 31.10.2019, p. 1-21.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Fast stochastic routing under time-varying uncertainty

AU - Pedersen, Simon Aagaard

AU - Yang, Bin

AU - Jensen, Christian S.

PY - 2019/10/31

Y1 - 2019/10/31

N2 - 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.

AB - 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.

UR - https://doi.org/10.1007/s00778-019-00585-6

U2 - 10.1007/s00778-019-00585-6

DO - 10.1007/s00778-019-00585-6

M3 - Tidsskriftartikel

SP - 1

EP - 21

JO - V L D B Journal

JF - V L D B Journal

SN - 1066-8888

ER -