DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2012.83

Speedup Techniques for the Stochastic on-time Arrival Problem

Authors: Samitha Samaranayake, Sebastien Blandin, and Alex Bayen

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract

We consider the stochastic on-time arrival (SOTA) routing problem of finding a routing policy that maximizes the probability of reaching a given destination within a pre-specified time budget in a road network with probabilistic link travel-times. The goal of this work is to provide a theoretical understanding of the SOTA problem and present efficient computational techniques to enable the development of practical applications for stochastic routing. We present multiple speedup techniques that include a label-setting algorithm based on the existence of a minimal link travel-time on each road link, advanced convolution methods centered on the Fast Fourier Transform and the idea of zero-delay convolution, and localization techniques for determining an optimal order of policy computation. We describe the algorithms for each speedup technique and analyze their impact on computation time. We also analyze the behavior of the algorithms as a function of the network topology and present numerical results to demonstrate this. Finally, experimental results are provided for the San Francisco Bay Area arterial road network to show how the algorithms would work in an operational setting.

Cite as

Samitha Samaranayake, Sebastien Blandin, and Alex Bayen. Speedup Techniques for the Stochastic on-time Arrival Problem. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 83-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{samaranayake_et_al:OASIcs.ATMOS.2012.83,
  author =	{Samaranayake, Samitha and Blandin, Sebastien and Bayen, Alex},
  title =	{{Speedup Techniques for the Stochastic on-time Arrival Problem}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{83--96},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.83},
  URN =		{urn:nbn:de:0030-drops-37050},
  doi =		{10.4230/OASIcs.ATMOS.2012.83},
  annote =	{Keywords: Stochastic routing, Dynamic programming, Traffic information systems}
}

Search Results

Documents authored by Blandin, Sebastien

Speedup Techniques for the Stochastic on-time Arrival Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message