搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

张水舰 刘学军 杨洋

引用本文:
Citation:

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

张水舰, 刘学军, 杨洋

Dynamic stochastic shortest path algorithm

Zhang Shui-Jian, Liu Xue-Jun, Yang Yang
PDF
导出引用
  • 静态最短路径问题已经得到很好解决, 然而现实中的网络大多具有动态性和随机性. 网络弧和节点的状态及耗费不仅具有不确定性且相互关联, 弧和节点的耗费都服从一定的概率分布, 因此把最短路径问题看作是一个动态随机优化问题更具有一般性. 文中分析了网络弧和节点的动态随机特性及其相互关系, 定义了动态随机最短路径; 给出了动态随机最短路径优化数学模型, 提出了一种动态随机最短路径遗传算法; 针对网络的拓扑特性设计了高效合理的遗传算子. 实验结果表明, 文中提出的模型和算法能有效地解决动态随机最短路径问题, 可以运用到交通、通信等网络的网络流随机优化问题中.
    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.
    • 基金项目: 国家高技术研究发展计划(批准号: 2007AA12Z238)和江苏省博士后基金(批准号: 1101016B)资助的课题.
    • Funds: Project supported by the National High Technology Research and Development Program of China (Grant No. 2007AA12Z238) and the Postdoctoral Science Foundation of Jiangsu Province, China (Grant No. 1101016B).
    [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

计量
  • 文章访问数:  7550
  • PDF下载量:  2618
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-12-30
  • 修回日期:  2012-04-27
  • 刊出日期:  2012-08-05

/

返回文章
返回