随机交通网络连通可靠度改进算法

交通运输系统工程与信息 ›› 2015, Vol. 15 ›› Issue (6): 197-204.

随机交通网络连通可靠度改进算法

范文博，王佳伟，杨成*

西南交通大学，成都610031

收稿日期:2015-06-09 修回日期:2015-09-24 出版日期:2015-12-25 发布日期:2015-12-25
作者简介:范文博（1981-），男，河南商丘人，讲师，博士.
基金资助:
国家自然基金项目(51378432)；中央高校基本科研业务科技创新项目(2682015CX042)

Improved Algorithm for Stochastic Network Connectivity Reliability

FANWen-bo,WANG Jia-wei,YANG Cheng

Southwest Jiaotong University，Chengdu 610031，China

Received:2015-06-09 Revised:2015-09-24 Online:2015-12-25 Published:2015-12-25

摘要/Abstract

摘要：

连通可靠度作为网络可靠性的基础指标是指导交通事故预防、灾后重建和日常维护等活动的重要理论，但其计算是经典的NP难问题.为了提高大规模网络应用的求解精度和效率，提出了基于k-最短路径和状态排序的改进算法——Target_Order 算法，集中考察影响网络连通性的关键节点及其状态，有效减少了无关网络连通性的节点组合产生的冗余网络状态，大幅降低了计算复杂度.最后，以成都规划年地铁网为例，通过与传统算法（ORDER算法）比较，分析了算法关键参数的影响，验证了改进算法在精度与效率方面的显著优势.研究结果同样适用于其他随机交通网络的连通可靠度计算与统计.

关键词: 城市交通, 连通可靠度, ORDER算法, Target_Order算法, 随机交通网络

Abstract:

As the basic indicator of network reliability, connectivity reliability analysis provides theoretical basis for practices of traffic accident prevention, post-disaster reconstruction, operational maintenance, etc. The computation of connectivity reliability, however, is a typical NP-hard problem. In order to improve the computing accuracy and efficiency of large-scale network application, an improved algorithm (called Target_Order) is proposed based on k- shortest path algorithm and ORDER algorithm (which is used to produce the most probable network states). Chengdu metro network (year of 2020) is selected as an example to explore the impact of algorithm parameters and illustrate the considerable advantages of the proposed algorithm against traditional ORDER algorithm in terms of computational accuracy and efficiency. The improved solution algorithm can be also applied to connectivity reliability evaluations of other transportation networks (e.g., railway and highway).

Key words: urban traffic, connectivity reliability, ORDER algorithm, Target_Order, stochastic network

中图分类号:

U492.3

范文博，王佳伟，杨成. 随机交通网络连通可靠度改进算法[J]. 交通运输系统工程与信息, 2015, 15(6): 197-204.

FANWen-bo,WANG Jia-wei,YANG Cheng. Improved Algorithm for Stochastic Network Connectivity Reliability[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(6): 197-204.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19102.shtml

http://www.tseit.org.cn/CN/Y2015/V15/I6/197

参考文献

[1] 王云琴. 基于复杂网络理论的城市轨道交通网络连通可靠性研究[D]. 北京：北京交通大学，2008：6. [WANG Y Q. Research on connectivity reliability of urban transit network based on theory of complex network [D]. Beijing: Beijing Jiaotong University, 2008: 6.]

[2] 朱顺应，王炜，邓卫，等. 交通网络可靠度及其通路算法研究[J]. 中国公路学报，2000，13(01)：94-97. [ZHU S Y, WANG W, DENG W, et al. Research on traffic network reliability and access road algorithm[J]. China Journal of Highway and Transport, 2000, 13(01): 94-97.]

[3] 陈晓明，邵春福，熊志华. 混合交通信号交叉口的通行能力可靠度[J]. 中国公路学报，2008，21(4)：99-104. [CHEN X M, SHAO C F, XIONG Z H. Reliability of signalized intersection capacity under mixed traffic[J]. China Journal of Highway and Transport, 2008, 21(4): 99-104.]

[4] 王婧，何杰，吴炼. 雨天高速公路网行程时间可靠性评价方法[J]. 交通运输系统工程与信息，2011，11(6)： 117-123. [WANG J, HE J, WU L. Evaluating approach of travel time reliability for highway network under rain environment[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(6): 117-123.]

[5] 岳焱超，马建勋，张硕英，等. 地震灾害下的桥梁网络可靠性分析[J]. 土木工程学报，2012，59(S1)：223- 226. [YUE Y C, MA J X, ZHANG S Y, et al. Network reliability analysis of bridge under earthquake hazards[J]. China Civil Engineering Journal, 2012, 59 (S1): 223-226.]

[6] Ball M O. Computational complexity of network reliability analysis：An overview[J]. IEEE Transactions on Reliability, 1986, 35(3): 230-239.

[7] Meyer J F. Closed-form solutions of performability[J]. IEEE Transactions on Computers, 1982, 31(7): 648-657.

[8] 马洪伟，周溪召，孙洪运. 城市交通网络连通可靠度计算研究[J]. 计算机应用研究，2013，30(01)：36-38. [MA H W, ZHOU X Z, SUN H Y. Study on computation of urban traffic network connectivity reliability[J]. Application Research of Computers, 2013, 30(01): 36- 38.]

[9] 何双华，赵洋，宋灿. 城市供水管网在地震时的连通可靠性分析[J]. 防灾减灾工程学报，2011，31(05)： 585-589. [HE S H, ZHAO Y, SONG C. Seismic connectivity reliability analysis of urban water supply network[J]. Journal of Disaster Prevention and Mitigation Engineering, 2011, 31(05): 585-589.]

[10] Li V O K, Silvester J A. Performance analysis of networks with unreliable components[J]. IEEE Transactions on Communications, 1984, 32(10): 1105- 1110.

[11] 岳焱超，马建勋，郜健，等. 蒙特卡罗方法和ORDER算法在网络可靠度计算中的对比[J]. 重庆交通大学学报（自然科学版），2013，32(S1)：776-778. [YUE Y C, MA J X, HAO J, et al. Comparison of Monte Carlo simulation and ORDER algorithm in calculation of network reliability[J]. Journal of Chongqing Jiaotong University (Natural Science), 2013，32(S1)：776-778.]

[12] Lam Y F, Li V O K. An improved algorithm for performance analysis of networks with unreliable components[J]. IEEE Transactions on Communications, 1986, 34(5): 496-497.

[13] Chiou S N, Li V O K. Reliability analysis of a communication network with multimode components[J]. IEEE Journal on Selected Areas in Communications, 1986, 4(7): 1156-1161.

[14] Shier D R. A new algorithm for performance analysis of communication systems[J]. IEEE Transactions on Communications, 1988, 36(04): 516-519.

[15] Shooman A M. Algorithms for network reliability and connection availability analysis[C]//Electro/95 International. Professional Program Proceedings. IEEE, 1995: 309-333.