随机时间依赖网络的K期望最短路径

K Expected Shortest Path in Stochastic and Time-Dependent Network

首先给出了随机时间依赖网络模型、K期望最短路径问题的形式化描述 ,并针对公交网络推导出到达弧头结点的时刻所服从的概率密度函数、路径期望耗费的计算方法 ;然后 ,基于随机一致性假设和随机优势的概念给出了K期望最短路径问题的理论基础和算法并证明了算法的正确性 ;最后 。

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 weights 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 variable with probability distribution functions that vary with time. This paper addresses the problem of determining K expected shortest paths in stochastic, time-dependent networks. 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 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_PFSD algorithm), based on a weaker stochastic consistency condition and stochastic dominance. K_PFSD algorithm determines the a priori K expected shortest paths for any departure time. Finally, this paper illustrates how the algorithm can be implemented and applied.