Reliable shortest path finding in stochastic time-dependent road network with spatial-temporal link correlations: A case study from Beijing

In view of the time-dependent characteristic of travel times in road networks and the travel time reliability (TTR) requirements by different travelers, it is complicated and time-consuming to determine the reliable shortest path (RSP) in large-scale road networks. To search the RSP in stochastic and time-dependent (STD) network with spatial-temporal correlated link travel times, an efficient path finding algorithm is presented. First, the fitting test results based on floating car data show that it is more appropriate to characterize the travel time distributions (TTDs) of links using lognormal distributions. In order to quantify spatial-temporal correlations between links, correlation coefficients of link travel times are calculated. Also, influences of spatial distance (counted by the number of links), temporal distance (counted by the number of time intervals) and road type on link correlations is analyzed. Afterwards, the dynamic moment-matching method (DMM) is used to calculate the approximate path TTD when correlated link travel times are considered. Accounting for different travelers' risk tolerance, a dynamic-moment-matching-based A* algorithm (STCRSP-DMA*) is proposed to provide personalized path navigation for individual travelers. Last, numerical case studies based on abundant floating car data as well as a subsistent road network in Beijing are conducted to demonstrate the applicability and the computational advantage of the devised algorithm in solving RSP searching problems.