Adaptive K-Expected Shortest Paths In Stochastic Time-Varying Networks

A stochastic and time-dependent network (i.e. STD network) is a network where arc travel times are random variables with time-dependent probability distributions. Stochastic and time-dependent properties are found in many modern communication and transportation systems. Fast expansion of such systems has made the study of STD networks very useful and even more challenging. So the study of shortest path problem in STD networks is of timely importance.In stochastic, time-dependent (or STD) transportation networks, one can make routing decisions en route as traversal times on traveled arcs are experienced and arrival times at intermediate locations are revealed. For each given origin destination pair at a specific departure time, a single path may not provide an adequate solution, thus, a set of K shortest strategies, referred to as hyperpaths, are generated to provide directions to the destination node conditioned upon arrival times at intermediate locations. In this paper, we provide an algorithm (A_KESP) based on adaptive paths and K expected shortest paths for determining the adaptive K expected shortest paths in STD networks. And the algorithm is not only appropriate for FIFO networks but also appropriate for non-FIFO networks.First, the STD network Model, the optimality conditions of STD network and the associated theories are proposed in this paper. Secondly, the AKESP algorithm is presented. Next, this paper proves the correctness of A_KESP algorithm and analyzes its time complexity. Finally, an experiment is designed to test the algorithm's performance and an illustrative example of the algorithm is provided. And the experiment results show that the AKESP algorithm is efficient.