Precomputation techniques for the stochastic on-time arrival problem

摘要: We consider the stochastic on-time arrival (SOTA) problem of finding optimal routing strategy for reaching a given destination within pre-specified time budget and provide first results on using preprocessing techniques speeding up query time. start by identifying some properties SOTA that limit types can be used in this setting, then define variants two deterministic shortest path adapted to problem, namely reach arc-flags. present algorithms each technique, also an extension standard based method provides additional pruning. Finally, we explain limitations approach due inefficiency phase fast heuristic scheme. Numerical San Francisco, Luxembourg synthetic road network show order magnitude improvement short queries, with even larger gains expected longer queries.