Reliable Shortest Path Research Based On Big Data

With the rapidly development of economic society,expansion of the size of city and the increase of vehicle numbers,congestion problem caused by contradiction between supply and demand of urban traffic is becoming more severe.Increasing attention has been paid to the problem of improving travel efficiency and alleviating urban traffic congestion.Finding reliable shortest path is deemed to go far towards solving such problems.This article aims to help travelers make reliable path planning under travel time uncertainty,in which plan travelers get minimum travel time with desired on-time arrival probability.First,three typical reliable shortest path models(TTB,METT,MMD)are summarized.By analyzing the applicable conditions of each model,it is found that the MMD model under robustness will generate too many selectable paths in the high-delay network,resulting in the most reliable information being masked.By comparing the correlation between the robust model and the non-robust model,it is found that the maximum delay parameter can be fitted by using the probability distribution function to ensure that the MMD model also produces a reliable path.Second,taking into account the actual traffic conditions and different travel demand,three new heuristic functions for A*algorithm are proposed.In order to avoid congestion,the first estimates path travel time by physical distances and 85%high travel speed.The second adopts historical minimal path travel time under different time intervals.In consideration that the long passive waiting time at intersection,the third employs the number of intersections as the measurement of path travel time.The modified A*heuristic algorithms are superior to existing algorithms in time complexity and computational efficiency.Third,a comprehensive numerical example was presented using the floating car data in Beijing.Via comparison analysis between morning(8am)and evening(6pm)peak static traffic data collected on working days within a whole month,we revealed that congestion during evening hours is more severe than that of its morning counterpart.Comparing these algorithms under different heuristic definitions with dynamic data collected during morning peak hours(7-9am with lmin interval),experimental results indicated that the three modified A*algorithms perform much better than Euclidean heuristic algorithm,especially the latter two,which are even 10 times faster.In this paper,we study the reliable shortest path model and algorithm from the traffic data in Beijing.The characteristics of different reliable models were summarized.Three modified A*algorithms based on TTB were proposed and validated by the actual network.The research work of this paper will provide the theoretical basis for the urban residents to obtain the travel time according to the probabilistic path planning scheme.