动态随机最短路径算法研究

Dynamic stochastic shortest path algorithm

静态最短路径问题已经得到很好解决,然而现实中的网络大多具有动态性和随机性.网络弧和节点的状态及耗费不仅具有不确定性且相互关联,弧和节点的耗费都服从一定的概率分布,因此把最短路径问题看作是一个动态随机优化问题更具有一般性.文中分析了网络弧和节点的动态随机特性及其相互关系,定义了动态随机最短路径;给出了动态随机最短路径优化数学模型,提出了一种动态随机最短路径遗传算法;针对网络的拓扑特性设计了高效合理的遗传算子.实验结果表明,文中提出的模型和算法能有效地解决动态随机最短路径问题,可以运用到交通、通信等网络的网络流随机优化问题中.

The static shortest path problem has been solved well. However, in reality, more networks are dynamic and stochastic. The states and costs of network arcs and nodes are not only uncertain but also correlated with each other, and the costs of the arcs and nodes are subject to a certain probability distribution. Therefore, it is more general to model the shortest path problem as a dynamic and stochastic optimization problem. In this paper, the dynamic and stochastic characteristics of network nodes and arcs and the correlation between the nodes and arcs are analyzed. The dynamic stochastic shortest path is determined. The dynamic stochastic optimization model of shortest path is provided, and a shortest path genetic algorithm is proposed to solve dynamic and stochastic shortest path problem. The effective and reasonable genetic operators are designed according to the topological characteristics of the network. The experimental results show that this algorithm can be used to effectively solve the dynamic stochastic shortest path problem. The proposed model and algorithm can be applied to the network flow optimization problem in transportation, communication networks, etc.