考虑行程时间相关性的可靠最短路径算法  

Reliable Shortest Path Algorithm that Considers Travel Time Correlation

作　　者：江恩 张镇洋 Jiang En;Zhang Zhenyang(Chongqing City Integrated Transportation Hub(Group)Co.,Ltd.,Chongqing,China;Chongqing Comprehensive Transportation Research Institue Co.,Ltd.,Chongqing,China)

机构地区：[1]重庆城市综合交通枢纽(集团)有限公司,重庆 [2]重庆市综合交通运输研究所有限公司,重庆

出　　处：《科学技术创新》2024年第16期13-16,共4页Scientific and Technological Innovation

摘　　要：可靠最短路径(RSP)问题反映了出行时间的可变性,比只考虑平均出行时间的标准最短路径问题更加实际可行。本文提出了一种考虑路段行程时间相关性的均值-标准偏差RSP问题的求解思路。该算法采用拉格朗日代入和协方差矩阵分解技术,解决了混合整数非线性规划(MINLP)的非线性和不可加性带来的困难。将该问题分解为标准最短路径问题和凸优化问题,证明了凸优化问题的最优解,并将拉格朗日乘子范围与协方差矩阵的特征值联系起来,提出采用次梯度法进行拉格朗日乘子更新。该算法能降低了原问题的复杂性,可扩展到大型网络。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 algorithm 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 related to the eigenvalue of the covariance matrix,and the Lagrange multiplier update is proposed by sub-gradient method.The algorithm reduces the complexity of the original problem and scales to large networks.

关 键 词：可靠最短路径 路段行程时间 凸优化 算法 

分 类 号：U491.6[交通运输工程—交通运输规划与管理]