Reliable Shortest Path Algorithm that Considers Travel Time Correlation
Reliable shortest path(RSP)problem reflects the variability of travel time and is more realistic than standard shortest path problem which considers only the average travel time.This paper describes an al gorithm for solving the mean-standard deviation RSP problem considering link travel time correlations.The proposed algorithm adopts the Lagrangian substitution and covariance matrix decomposition technique to deal with the difficulty resulting from non-linearity and non-additivity of the Mixed Integer Non-Linear Program(MINLP).Decomposing the problem into a standard shortest path problem and a convex optimization problem,the optimal solution of the convex optimization problem is proved,and the Lagrange multiplier range is relat ed to the eigenvalue of the covariance matrix,and the Lagrange multiplier update is proposed by sub-gradi ent method.The algorithm reduces the complexity of the original problem and scales to large networks.
NETL
NSTL
万方数据
