.png){kind=icon}
返回
An exact algorithm for the mean-standard deviation shortest path problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.trb.2015.04.002.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper studies the reliable path problem in the form of minimizing the sum of mean and standard deviation of path travel time. For the case of independent link travel times, we show that the problem can be solved exactly by repeatedly solving a subproblem minimizing the sum of mean and variance of path travel time. The latter is an additive shortest path problem, and can be solved using a standard labeling algorithm. While these subproblems are similar in form to those obtained from Lagrangian relaxation, this formulation admits proof of finite convergence to the optimal solution. An iterative labeling algorithm is developed that solves the non-additive reliable path problem from a single origin to all destinations. Moreover, a labeling technique is employed to further reduce the computational time of the proposed algorithm by partially updating the network in each iteration. As an alternative, a bisection-type search algorithm is developed that solves the problem for the single-origin and single-destination case. Numerical tests are presented, indicating that the proposed algorithm outperform others recently proposed in the literature: unlike Lagrangian relaxation, two of the proposed algorithms find solutions exactly, and the computation time is an order of magnitude faster than outer approximation methods. (C) 2015 Elsevier Ltd. All rights reserved.
Keyword:
Reliability
Non-additive shortest path
Mean-standard deviation
Path efficient frontier
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.3
论文数:
3.5K
被引数:
1.9W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容