• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>World Multiconference on Systemics, Cybernetics and Informatics(SCI 2002) v.11: Computer Science II; 20020714-20020718; Orlando,FL; US >A Parallel Algorithm for Finding K Expected Shortest Paths in Stochastic and Time-Dependent Networks
【24h】

A Parallel Algorithm for Finding K Expected Shortest Paths in Stochastic and Time-Dependent Networks

机译：在随机和时变网络中寻找K条预期最短路径的并行算法

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

摘要

Many transportation and communication systems can be represented by networks with travel times that are both stochastic and time-dependent. This has lead to a need for extensive research on path planning in stochastic and time-dependent networks. When the arc length of a system model is stochastic and time-dependent, the problem becomes considerably more difficult. Standard shortest path algorithms, such as the Dijkstra algorithm, are not valid in these circumstances, since travel times are now random and time-dependent variables. In this paper, we present a distributed and parallel algorithm to determine K shortest paths from source to destination on stochastic and time-dependent networks. We propose the decomposing arcs approach, give the implementation of the parallel algorithm, and prove the correctness of the algorithm. Finally, we test the performance of the parallel algorithm on a series of stochastic and time-dependent networks. The computational results show that the parallel algorithm can be used to solve large-scale shortest path problems on dynamic networks.
机译：许多运输和通信系统都可以用旅行时间既是随机的又是时间依赖的网络来表示。这导致需要对随机和时变网络中的路径规划进行广泛的研究。当系统模型的弧长是随机的且与时间有关时，问题将变得更加困难。在这种情况下，标准的最短路径算法（例如Dijkstra算法）无效，因为行驶时间现在是随机的且与时间有关的变量。在本文中，我们提出了一种分布式并行算法，以确定随机和时间相关网络上从源到目的地的K条最短路径。我们提出了分解弧线方法，给出了并行算法的实现，并证明了算法的正确性。最后，我们在一系列随机且与时间有关的网络上测试了并行算法的性能。计算结果表明，该并行算法可以解决动态网络中的大规模最短路径问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号