  We study stochastic routing in the PAth-CEntric (PACE) uncertain road network
model. In the PACE model, uncertain travel times are associated with not only
edges but also some paths. The uncertain travel times associated with paths are
able to well capture the travel time dependency among different edges. This
significantly improves the accuracy of travel time distribution estimations for
arbitrary paths, which is a fundamental functionality in stochastic routing,
compared to classic uncertain road network models where uncertain travel times
are associated with only edges.
  We investigate a new formulation of the shortest path with on-time arrival
reliability (SPOTAR) problem under the PACE model. Given a source, a
destination, and a travel time budget, the SPOTAR problem aims at finding a
path that maximizes the on-time arrival probability. We develop a generic
algorithm with different speed-up strategies to solve the SPOTAR problem under
the PACE model. Empirical studies with substantial GPS trajectory data offer
insight into the design properties of the proposed algorithm and confirm that
the algorithm is effective.
  This report extends the paper "Stochastic Shortest Path Finding in
Path-Centric Uncertain Road Networks", to appear in IEEE MDM 2018, by providing
a concrete running example of the studied SPOTAR problem in the PACE model and
additional statistics of the used GPS trajectories in the experiments.
