科研之友
微信
新浪微博
Facebook
分享链接
摘要
The static K shortest paths (KSP) problem has been resolved. In reality, however, most of the networks are actually dynamic stochastic networks. The state of the arcs and nodes are not only uncertain in dynamic stochastic networks but also interrelated. Furthermore, the cost of the arcs and nodes are subject to a certain probability distribution. The KSP problem is generally regarded as a dynamic stochastic optimization problem. The dynamic stochastic characteristics of the network and the relationships between the arcs and nodes of the network are analyzed in this paper, and the probabilistic shortest path concept is defined. The mathematical optimization model of the dynamic stochastic KSP and a genetic algorithm for solving the dynamic stochastic KSP problem are proposed. A heuristic population initialization algorithm is designed to avoid loops and dead points due to the topological characteristics of the network. The reasonable crossover and mutation operators are designed to avoid the illegal individuals according to the sparsity characteristic of the network. Results show that the proposed model and algorithm can effectively solve the dynamic stochastic KSP problem. The proposed model can also solve the network flow stochastic optimization problems in transportation, communication networks, and other networks.
- 出版日期2013-6
- 单位南京师范大学
