考虑行程时间相关性的可靠最短路径算法
Reliable Shortest Path Algorithm that Considers Travel Time Correlation
江恩 1张镇洋2
作者信息
- 1. 重庆城市综合交通枢纽(集团)有限公司,重庆
- 2. 重庆市综合交通运输研究所有限公司,重庆
- 折叠
摘要
可靠最短路径(RSP)问题反映了出行时间的可变性,比只考虑平均出行时间的标准最短路径问题更加实际可行.本文提出了一种考虑路段行程时间相关性的均值-标准偏差RSP问题的求解思路.该算法采用拉格朗日代入和协方差矩阵分解技术,解决了混合整数非线性规划(MINLP)的非线性和不可加性带来的困难.将该问题分解为标准最短路径问题和凸优化问题,证明了凸优化问题的最优解,并将拉格朗日乘子范围与协方差矩阵的特征值联系起来,提出采用次梯度法进行拉格朗日乘子更新.该算法能降低了原问题的复杂性,可扩展到大型网络.
Abstract
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.
关键词
可靠最短路径/路段行程时间/凸优化/算法Key words
reliable shortest path/link travel time/convex optimization/algorithm引用本文复制引用
出版年
2024
NETL
NSTL
万方数据