Speedup Techniques for the Stochastic on-time Arrival Problem

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