Study On Reliable Path Problem Based On Historical Data

Traffic trip is a basic requirement that is inevitable in our daily life.Obtaining reliable and effective information about traffic trip in advance can not only meet the basic travel needs of travelers,but also improve the travel efficiency.Therefore,path planning problem in the traffic network came into being.The previous studies on the shortest path problem,the reliable path problem and the corresponding solution algorithm are reviewed and summarized in this paper.Generally,without considering the uncertainty of travel time,the objective function of shortest path problem in the static traffic network is the mean travel time of the path.On the basis of the shortest path problem,the reliable path problem considers the linear combination of the standard deviation and mean of path travel time as the objective function.The uncertainty and randomness of travel time are considered in this model.Based on the review and summary,the main content of this paper is determined.This paper constructs a reliable path model based on historical data.Considering that the uncertainty of travel time and the spatial correlation among link travel times are essential characteristics of actual traffic networks,the reliable path model based on historical data takes the linear combination of mean path travel time and its standard deviation as the objective function.Based on a large number of historical data of link travel time,we can calculate the standard deviation of path travel time directly through the method of using sample variance to estimate the overall variance of random variables in the field of statistics.The standard deviation of path travel time represents that the model proposed by this paper considers the uncertainty and randomness of travel time.In addition,a large number of historical data of link travel time implies spatial correlation among link travel times,which makes the model more realistic.Solution algorithm of reliable path problem based on Lagrangian relaxation is proposed.The objective function of reliable path model based on historical data is nonlinear and non-additive,which is against Bellman’s principle of optimality.Therefore,this paper considers using the solution algorithm based on Lagrangian relaxation to solve the model proposed by this paper.The basic idea of the Lagrangian relaxation approach is moving the intractable constraints into the objective function by introducing non-negative Lagrangian multipliers.Simultaneously,the objective function remains linear.Accordingly,the Lagrangian relaxation problem that is equivalent to the original problem is obtained.The optimal solution obtained by the Lagrangian relaxation method is the lower bound of the optimal solution of the original problem.The optimal lower bound is obtained by the Lagrangian dual problem,which is the maximization problem of Lagrangian relaxation problem that takes the Lagrangian multipliers as variables.There are four steps of the solution algorithm of reliable path problem based on Lagrangian relaxation: problem reconstruction,constructing and simplifying Lagrangian relaxation problems,constructing Lagrangian dual problems,and solving dual problems.This paper applies the proposed model and solution method to traffic networks of different sizes.The small traffic network example with single OD pair is compared with the reliable path model based on the variance-covariance matrix.Thus,the correctness of the model and solution method is verified.To verify the applicability of the model and solution method to the mediumsized traffic network,the convergence speed,running time,and relative gap between upper bound and lower bound are analyzed through the Sioux-Falls traffic network example which is a mediumsized network with multiple OD pairs.