-
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.
[1] Peer S K, Dinesh K S 2007 Comput. Math. Appl. 53 729
[2] Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林 勇, 傅白白 2011 物理学报 60 050701]
[3] Wang K, Zhou S Y, Zhang Y F, Pei W J, Liu Q 2011 Acta Phys. Sin. 60 118903 (in Chinese) [王开, 周思源, 张毅锋, 裴文江, 刘茜 2011 物理学报 60 118903]
[4] Bellman E 1958 Quart. Appl. Math. 16 87
[5] Dijkstra E W 1959 Numer. Math. 1 269
[6] Dreyfus S 1969 Operat. Res. 17 395
[7] Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[8] Frank H 1969 Operat. Res. 17 583
[9] Hall R W 1986 Transport. Sci. 20 182
[10] Fu L, Rilett L R 1998 Transport. Res. B 32 499
[11] Miller-Hooks E D, Mahmassani H S 1998 Comput. Operat. Res 25 1107
[12] Miller-Hooks E D, Mahmassani H S 2000 Transport. Sci. 34 198
[13] Sigal C E, Pritsker A A B, Solberg J J 1980 Operat. Res. 28 1122
[14] Kamburowski J 1985 Operat. Res. 22 696
[15] Wellman M P 1995 Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence Montreal, Quebec, Canada, August 18-20, 1995 p18
[16] Jaillet P 1992 Networks 22 589
[17] Fan Y Y, Kalaba R E, Moore J E 2005 Comput. Math. Appl. 49 1549
[18] Dong J Y, Zhang J Y, Chen Z 2007 Acta Phys. Sin. 56 5013 (in Chinese) [董继扬, 张军英, 陈忠 2007 物理学报 56 5013]
[19] Alberto D V, Roberto M, Norman C, Andrea E R, Gambardella L M 2008 Eur. J. Operat. Res. 185 1174
[20] Thangiah S R, Nygard K, Juell P 1991 Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications Miami, USA, February 24-28, 1991 p422
[21] Inagaki J, Haseyama M, Kitajima H 1999 Proc. IEEE Int. Symp. Circuits and Systems Orlando, USA, May 30-June 2, 1999 p137
[22] Chang W A, Ramakrishna R S 2002 IEEE Trans. Evol. Comput. 6 566
[23] Nanayakkara S, Srinivasan D, Lup L, Xavier G, Elizabeth T, Ong S H 2007 IEEE Congress on Evolutionary Computation Singapore, September 25-28, 2007 p4469
[24] Davies C, Lingras P 2003 Eur. J. Operat. Res. 144 27
[25] Yang S, Cheng H, Wang F 2010 IEEE Trans. Syst. Man Cybernet. C 40 52
[26] Charles J S 1996 A Course in Probability and Statistics (California: Duxbury Press) p81
[27] Holland J H 1975 Adaptation in Natural and Artificial Systems (Michigan: University of Michigan Press) p22
[28] Thomas B W, White C C 2007 Eur. J. Operat. Res. 176 836
[29] Bell M G H, Iida Y 1997 Transportation Network Analysis (Chichester: John Willey and Sons) p17
-
[1] Peer S K, Dinesh K S 2007 Comput. Math. Appl. 53 729
[2] Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林 勇, 傅白白 2011 物理学报 60 050701]
[3] Wang K, Zhou S Y, Zhang Y F, Pei W J, Liu Q 2011 Acta Phys. Sin. 60 118903 (in Chinese) [王开, 周思源, 张毅锋, 裴文江, 刘茜 2011 物理学报 60 118903]
[4] Bellman E 1958 Quart. Appl. Math. 16 87
[5] Dijkstra E W 1959 Numer. Math. 1 269
[6] Dreyfus S 1969 Operat. Res. 17 395
[7] Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[8] Frank H 1969 Operat. Res. 17 583
[9] Hall R W 1986 Transport. Sci. 20 182
[10] Fu L, Rilett L R 1998 Transport. Res. B 32 499
[11] Miller-Hooks E D, Mahmassani H S 1998 Comput. Operat. Res 25 1107
[12] Miller-Hooks E D, Mahmassani H S 2000 Transport. Sci. 34 198
[13] Sigal C E, Pritsker A A B, Solberg J J 1980 Operat. Res. 28 1122
[14] Kamburowski J 1985 Operat. Res. 22 696
[15] Wellman M P 1995 Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence Montreal, Quebec, Canada, August 18-20, 1995 p18
[16] Jaillet P 1992 Networks 22 589
[17] Fan Y Y, Kalaba R E, Moore J E 2005 Comput. Math. Appl. 49 1549
[18] Dong J Y, Zhang J Y, Chen Z 2007 Acta Phys. Sin. 56 5013 (in Chinese) [董继扬, 张军英, 陈忠 2007 物理学报 56 5013]
[19] Alberto D V, Roberto M, Norman C, Andrea E R, Gambardella L M 2008 Eur. J. Operat. Res. 185 1174
[20] Thangiah S R, Nygard K, Juell P 1991 Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications Miami, USA, February 24-28, 1991 p422
[21] Inagaki J, Haseyama M, Kitajima H 1999 Proc. IEEE Int. Symp. Circuits and Systems Orlando, USA, May 30-June 2, 1999 p137
[22] Chang W A, Ramakrishna R S 2002 IEEE Trans. Evol. Comput. 6 566
[23] Nanayakkara S, Srinivasan D, Lup L, Xavier G, Elizabeth T, Ong S H 2007 IEEE Congress on Evolutionary Computation Singapore, September 25-28, 2007 p4469
[24] Davies C, Lingras P 2003 Eur. J. Operat. Res. 144 27
[25] Yang S, Cheng H, Wang F 2010 IEEE Trans. Syst. Man Cybernet. C 40 52
[26] Charles J S 1996 A Course in Probability and Statistics (California: Duxbury Press) p81
[27] Holland J H 1975 Adaptation in Natural and Artificial Systems (Michigan: University of Michigan Press) p22
[28] Thomas B W, White C C 2007 Eur. J. Operat. Res. 176 836
[29] Bell M G H, Iida Y 1997 Transportation Network Analysis (Chichester: John Willey and Sons) p17
Catalog
Metrics
- Abstract views: 9175
- PDF Downloads: 2646
- Cited By: 0
下载:
