• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Transportation Research Part B: Methodological >Optimal paths in dynamic networks with dependent random link travel times
【24h】

Optimal paths in dynamic networks with dependent random link travel times

机译：动态网络中具有随机链路传播时间的最优路径

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper addresses the problem of finding optimal paths in a network where all link travel times are stochastic and time-dependent, and correlated over time and space. A disutility function of travel time is defined to evaluate the paths, and those with the minimum expected disutility are defined as the optimal paths. Bellman's Principle (Bellman, 1958) is shown to be invalid if the optimality or non-dominance of a path and its sub-paths is defined with respect to the complete set of departure times and joint realizations of link travel time. An exact label-correcting algorithm is designed to find optimal paths based on a new property for which Bellman's Principle holds. The algorithm has exponential worst-case computational complexity. Computational tests are conducted on three types of networks. Although the average running time is exponential, the number of the optimal path candidates is polynomial on two networks and grows exponentially in the third one. Computational results in large networks and analytical results in a small network show that stochastic dependencies affect optimal path finding in a stochastic network, and that the impact is closely related to the levels of correlation and risk attitude.
机译：本文解决了在网络中寻找最佳路径的问题，在该网络中，所有链路的旅行时间都是随机的且与时间相关的，并且随时间和空间而相关。定义了旅行时间的无效功能来评估路径，而将预期无效度最小的功能定义为最佳路径。如果一条路径及其子路径的最优性或非支配性是根据完整的出发时间集合和链接行进时间的联合实现来定义的，则贝尔曼原理（贝尔曼，1958年）被证明是无效的。一种精确的标签校正算法旨在根据Bellman原理所拥有的新属性找到最佳路径。该算法具有指数最坏情况的计算复杂度。计算测试是在三种类型的网络上进行的。尽管平均运行时间是指数级的，但最佳路径候选的数量在两个网络上都是多项式的，而在第三个网络上则呈指数级增长。大型网络中的计算结果和小型网络中的分析结果表明，随机依赖关系会影响随机网络中的最佳路径查找，并且这种影响与相关性和风险态度的水平密切相关。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号