2012 · 35 citations · 20 references
ComputingTransportation PlanningPath PlanningTransportTransportationRoute PlanningRoutingRouting AlgorithmsShortest Path AlgorithmsStochastic Shortest Path ProblemsTransport ModelingApproximation Algorithms For Shortest PathsDelay OptimizationPath ComputationProbabilistic Data Structure DesignProbabilistic Shortest PathsShortest Path On Road NetworksStochastic RoutingWorst-case Bounds
We describe an algorithm for stochastic path planning and applications to route planning in the presence of traffic delays. We improve on the prior state of the art by designing, analyzing, implementing, and evaluating data structures that answer approximate stochastic shortest-path queries. For example, our data structures can be used to efficiently compute paths that maximize the probability of arriving at a destination before a given time deadline.
20
Mikkel Thorup, Uri Zwick · Journal of the ACM · 2005 · 618 citations
MATCHING GPS OBSERVATIONS TO LOCATIONS ON A DIGITAL MAP
Joshua Greenfeld · 2002 · 409 citations
Computing, Geoinformatics, Geographic Information Systems +13