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. (C) 2013 Elsevier Inc. All rights reserved.