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

摘要

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.