Random Network Routing Algorithm And Applications

Transportation, communication systems can be represented by networks with travel times that are both stochastic and time-dependent, which motivates the need for widely research on path planning in stochastic, time-dependent networks. When the arc lengths are stochastic and time-dependent, the problem becomes considerably more difficult. Standard shortest path algorithms (such as the Dijkstra algorithm) are not valid, since travel times are random, time-dependent variables. Especially, the recognition version of the stochastic shortest path problems is NP-complete. K expected shortest paths problem shown in this paper is one of these problems. It first shows the building of stochastic, time-dependent network model, the description of K expected shortest paths problem, the demonstration of travel time probability distributions for the arcs in transportation area, and the calculation of expected travel time on path. Next, this paper presents the theoretical foundation of K expected shortest path, which justifies the algorithm (K-ESP, K-PFSD algorithm), based on a weaker stochastic consistency condition and stochastic dominance. K-PFSD algorithm can solve problems of considerably greater size than would be possible with exhaustive search. Finally, this paper illustrates how the algorithm can be implemented and applied.