Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Samaranayake, Samitha; Blandin, Sebastien; Bayen, Alex http://www.dagstuhl.de/oasics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-37050
URL:

; ;

Speedup Techniques for the Stochastic on-time Arrival Problem

pdf-format:


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.

BibTeX - Entry

@InProceedings{samaranayake_et_al:OASIcs:2012:3705,
  author =	{Samitha Samaranayake and Sebastien Blandin and Alex Bayen},
  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 =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Daniel Delling and Leo Liberti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3705},
  URN =		{urn:nbn:de:0030-drops-37050},
  doi =		{http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.83},
  annote =	{Keywords: Stochastic routing, Dynamic programming, Traffic information systems}
}

Keywords: Stochastic routing, Dynamic programming, Traffic information systems
Seminar: 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue date: 2012
Date of publication: 2012


DROPS-Home | Fulltext Search | Imprint Published by LZI