Paper Info
Title
Processing time-dependent shortest path queries without pre-computed speed information on road networks
Abstract
Shortest path (or least travel time path) identification has been actively studied for direct application to road networks. In addition, the processing of time-dependent shortest-path queries, which use past traffic data to compute the speed variations of road segments, has been investigated in order to incorporate speed variations over time. However, speed information pre-computed from static past traffic data is often invalid because road traffic is inherently dynamic. This paper addresses a new problem in processing a Dynamic Time-Dependent Shortest Path (DTDSP) query, which considers the current road status without assuming pre-determined speed patterns on roads. By dynamically adjusting the speed patterns of roads instead of fixing them based on past traffic data, the recommended paths, which reflect the current road status, are more effective in distributing the road traffic and thus reducing the travel time. To process DTDSP queries, we first propose a Continuous Piece-wise Linear Speed Pattern (CPLSP) model to compute the vehicle speed patterns, which is more flexible and realistic than previously adopted piece-wise constant speed pattern models. Using dynamically computed CPLSPs, we process a DTDSP query in two phases: (1) the least travel time path is found for the query and (2) the speed patterns of the following vehicles, which are affected by the participation of the new vehicle on the road network, are updated. We propose efficient algorithms for finding the least travel time path of a new query (vehicle) and for updating the speed patterns of the existing vehicles. Experiments on real data sets show that our query processing algorithms effectively distribute road traffic, and thus, significantly reduce both global and individual travel times.
Year
DOI
Venue
2014
10.1016/j.ins.2013.07.009
Inf. Sci.
Keywords
Field
DocType
speed pattern,pre-computed speed information,road network,processing time-dependent shortest path,pre-determined speed pattern,past traffic data,current road status,speed variation,dtdsp query,piece-wise constant speed pattern,road traffic,travel time path,ergonomics,routing,shortest path,suicide prevention,human factors,injury prevention,occupational safety
Data set,Road networks,Shortest path problem,Simulation,Floating car data,Road traffic,Real-time computing,Artificial intelligence,Accident prevention,Travel time,Machine learning,Mathematics
Journal
Volume
ISSN
Citations 
255,
0020-0255
7
PageRank 
References 
Authors
0.48
18
5
Name
Order
Citations
PageRank
Jin-ha Kim132918.78
Wook-Shin Han280557.85
Jinoh Oh330315.32
Sungchul Kim410810.36
Hwanjo Yu51715114.02