  The availability of massive vehicle trajectory data enables the modeling of
road-network constrained movement as travel-cost distributions rather than just
single-valued costs, thereby capturing the inherent uncertainty of movement and
enabling improved routing quality. Thus, stochastic routing has been studied
extensively in the edge-centric model, where such costs are assigned to the
edges in a graph representation of a road network. However, as this model still
disregards important information in trajectories and fails to capture
dependencies among cost distributions, a path-centric model, where costs are
assigned to paths, has been proposed that captures dependencies better and
provides an improved foundation for routing. Unfortunately, when applied in
this model, existing routing algorithms are inefficient due to two shortcomings
that we eliminate. First, when exploring candidate paths, existing algorithms
only consider the costs of candidate paths from the source to intermediate
vertices, while disregarding the costs of travel from the intermediate vertices
to the destination, causing many non-competitive paths to be explored. We
propose two heuristics for estimating the cost from an intermediate vertex to
the destination, thus improving routing efficiency. Second, the edge-centric
model relies on stochastic dominance-based pruning to improve efficiency. This
pruning assumes that costs are independent and is therefore inapplicable in the
path-centric model that takes dependencies into account. We introduce a notion
of virtual path that effectively enables stochastic dominance-based pruning in
the path-based model, thus further improving efficiency. Empirical studies
using two real-world trajectory sets offer insight into the properties of the
proposed solution, indicating that it enables efficient stochastic routing in
the path-centric model.
