License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2012.83
URN: urn:nbn:de:0030-drops-37050
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3705/
Go to the corresponding OASIcs Volume Portal

Samaranayake, Samitha ; Blandin, Sebastien ; Bayen, Alex

Speedup Techniques for the Stochastic on-time Arrival Problem

pdf-format:
10.pdf (2 MB)

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 =		{10.4230/OASIcs.ATMOS.2012.83},
  annote =	{Keywords: Stochastic routing, Dynamic programming, Traffic information systems}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI