Paper Info
Title
PACE: a PAth-CEntric paradigm for stochastic path finding
Abstract
AbstractWith the growing volumes of vehicle trajectory data, it becomes increasingly possible to capture time-varying and uncertain travel costs, e.g., travel time, in a road network. The current paradigm for doing so is edge-centric: it represents a road network as a weighted graph and splits trajectories into small fragments that fit the underlying edges to assign time-varying and uncertain weights to edges. It then applies path finding algorithms to the resulting, weighted graph. We propose a new PAth-CEntric paradigm, PACE, that targets more accurate and more efficient path cost estimation and path finding. By assigning weights to paths, PACE avoids splitting trajectories into small fragments. We solve two fundamental problems to establish the PACE paradigm: (i) how to compute accurately the travel cost distribution of a path and (ii) how to conduct path finding for a source---destination pair. To solve the first problem, given a departure time and a query path, we show how to select an optimal set of paths that cover the query path and such that the weights of the paths enable the most accurate joint cost distribution estimation for the query path. The joint cost distribution models well the travel cost dependencies among the edges in the query path, which in turn enables accurate estimation of the cost distribution of the query path. We solve the second problem by showing that the resulting path cost distribution estimation method satisfies an incremental property that enables the method to be integrated seamlessly into existing stochastic path finding algorithms. Further, we propose a new stochastic path finding algorithm that fully explores the improved accuracy and efficiency provided by PACE. Empirical studies with trajectory data from two different cities offer insight into the design properties of the PACE paradigm and offer evidence that PACE is accurate, efficient, and effective in real-world settings.
Year
DOI
Venue
2018
10.1007/s00778-017-0491-4
Hosted Content
Keywords
Field
DocType
Stochastic routing,Routing,Trajectories,Road networks,Path cost distributions
Data mining,Graph,Pace,Mathematical optimization,Road networks,Computer science,Cost estimate,Travel time,Trajectory,Empirical research,Joint cost
Journal
Volume
Issue
ISSN
27
2
1066-8888
Citations 
PageRank 
References 
10
0.51
29
Authors
5
Name
Order
Citations
PageRank
Bin Yang170634.93
Jian Dai2975.95
Chenjuan Guo330116.81
Christian S. Jensen4106511129.45
Jilin Hu5745.69