基于改进Warshall算法的生命线系统抗震可靠性评估

郑山锁; 蔡国威; 王凯歌; 田琦

doi:10.3724/j.gyjzG25071806

基于改进Warshall算法的生命线系统抗震可靠性评估

doi: 10.3724/j.gyjzG25071806

郑山锁^1,2,
蔡国威^1,2, ,,
王凯歌^1,2,
田琦^1,2

1. 西安建筑科技大学土木工程学院, 西安 710055;
2. 西安建筑科技大学结构工程与抗震教育部重点实验室, 西安 710055

基金项目:

国家自然科学基金项目（52278530）。

详细信息

作者简介:
郑山锁，教授，博士生导师，主要从事结构工程与工程抗震研究，zhengshansuo@263.net。

通讯作者:
蔡国威,硕士研究生,主要从事基础设施工程抗震研究,Cai-Guowei@outlook.com。

计量
- 文章访问数: 13
- HTML全文浏览量: 1
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2025-07-18
- 网络出版日期: 2026-01-06

Seismic Reliability Assessment of Lifeline Systems Based on an Improved Warshall Algorithm

ZHENG Shansuo^1,2,
CAI Guowei^{1,2
, ,},
WANG Kaige^1,2,
TIAN Qi^1,2

1. School of Civil Engineering，Xi’an University of Architecture and Technology，Xi’an 710055，China;
2. Key Lab of Structural Engineering and Earthquake Resistance，Ministry of Education （XAUAT），Xi’an 710055，China

摘要

摘要: 生命线系统在低概率、高影响事件下的拓扑结构会动态变化，导致网络断裂，形成隔离子网络。针对传统Warshall算法未考虑隔离子网络对连通路径计算效率的影响，提出了改进Warshall算法，进行了时间复杂度分析，并将此算法应用于电力系统的抗震可靠性评估。以陕西省西安市电力系统为算例，对比了改进前后Warshall算法的计算结果及效率，分析了某节点的连通概率收敛曲线。结果表明：相同地震作用及网络拓扑结构下，超过5000次的蒙特卡洛模拟可确保分析结果的统计收敛性；不同抽样次数下，两者计算的节点连通概率高度一致，改进Warshall算法的计算效率存在显著优势，验证了改进算法的有效性。
- 生命线系统 /
- 隔离子网络 /
- 改进Warshall算法 /
- 可靠性 /
- 蒙特卡洛
Abstract: The topology of the lifeline system under low-probability and high-impact events changes dynamically， resulting in network fragmentation and the formation of isolated sub-networks. In view of the fact that the traditional Warshall algorithm does not consider the influence of isolated sub-networks on the computational efficiency of connectivity paths， this study proposed an improved Warshall algorithm， conducted a time complexity analysis， and applied the algorithm to the seismic reliability assessment of power systems. Taking the power system of Xi’an City， Shaanxi Province as an example， the computational results and efficiency of the Warshall algorithm before and after the improvement were compared， and the convergence curve of node connectivity probability was analyzed. The results showed that more than 5000 Monte Carlo simulations under the same seismic action and network topology ensured the statistical convergence of the analytical results. Under different sampling times， the node connectivity probabilities calculated by the two methods were highly consistent， and the computational efficiency of the improved Warshall algorithm showed a significant advantage， which verified the effectiveness of the improvement.
- lifeline systems /
- isolated sub-network /
- improved Warshall algorithm /
- reliability /
- Monte Carlo

HTML全文

参考文献(33)

[1]	于永清，李光范，李鹏等. 四川电网汶川地震电力设施受灾调研分析[J]. 电网技术，2008，32（11）:5-10.
[2]	于文，葛学礼，朱立新. 电力系统震害分析和抗震防灾对策[J]. 工业建筑，2016，46（6）:12-15.
[3]	张中近，刘如山，姜立新. 基于损失统计的变电站地震经济损失评估方法[J]. 自然灾害学报，2016，25（4）:93-100.
[4]	侯忠良，耿树江. 生命线工程的抗震减灾措施[J]. 工业建筑，1991，21（1）:8-11.
[5]	陆益挺，蒋建群，胡云进，等. 城市供水管道抗震可靠度评估方法与应用[J]. 城市道桥与防洪，2012（6）:150-154.
[6]	张明媛，双晴，袁永博. 基于DEA分析的生命线网络节点抗灾相对可靠度评估[J]. 防灾减灾工程学报，2011，31（4）:403-407.
[7]	何军，李杰. 大型生命线工程抗震可靠度分析的递推分解算法[J]. 同济大学学报（自然科学版），2001（7）:757-762.
[8]	顾倩，夏恒，何军. 相依失效生命线工程系统抗震可靠度估计的统一RDA算法[J]. 工程力学，2020，37（10）:155-167.
[9]	JOHNSON B，CHALISHAZAR V，COTILLA-SANCHEZ E，et al. A Monte Carlo methodology for earthquake impact analysis on the electrical grid[J]. Electric Power Systems Research，2020，184，106332.
[10]	史运涛，刘召，刘伟川，等. 基于贝叶斯网络的社区配电网系统动态风险评估[J]. 安全与环境工程，2021，28（2）:121-132.
[11]	孟祥成，何军. 基于高维Gumbel Copula参数拟合估计的大型相依失效生命线网络地震动力可靠度计算[J]. 防灾减灾工程学报，2023，43（2）:210-221.
[12]	何志超，王艳辉，安超，等. 基于拓扑网络模型的高速列车转向架系统中薄弱部件辨识方法[J]. 安全与环境工程，2021，28（2）:72-79.
[13]	LIU X，ZHENG S，WU X，et al. Research on a seismic connectivity reliability model of power systems based on the quasi-Monte Carlo method[J]. Reliability Engineering& System Safety，2021，215，107888.
[14]	郑山锁，汪靖，贺金川，等. 变电站主接线系统地震易损性分析[J]. 华中科技大学学报（自然科学版），2020，48（3）:98-103.
[15]	李吉超. 基于概率的变电站系统抗震性能评估方法研究[D]. 哈尔滨:中国地震局工程力学研究所，2018.
[16]	刘祎. 大电网可靠性蒙特卡罗模拟的最优f散度重要抽样方法研究[D]. 重庆:重庆大学，2021.
[17]	李杰. 生命线工程的研究进展与发展趋势[J]. 土木工程学报，2006，39（1）:1-6.
[18]	高军利，和兴锁，陶文祥. 结构系统可靠度分析方法及其实现[J]. 工业建筑，2008，38（增刊1）:316-319.
[19]	JIRUTITIJAROEN P，SINGH C. Comparison of simulation methods for power system reliability indexes and their distributions[J]. IEEE Transactions on Power Systems，2008，23（2）:486-493.
[20]	MELO A C G，OLIVEIRA G C，FO M M，et al. A hybrid algorithm for Monte Carlo/enumeration based composite reliability evaluation（power systems）[C]// 1991 Third International Conference on Probabilistic Methods Applied to Electric Power Systems. London:1991:70-74.
[21]	OLIVEIRA G C，PEREIRA M V F，CUNHA S H F. A technique for reducing computational effort in Monte-Carlo based composite reliability evaluation[J]. IEEE Transactions on Power Systems，1989，4（4）:1309-1315.
[22]	SANKARAKRISHNAN A，BILLINTON R. Sequential Monte Carlo simulation for composite power system reliability analysis with time varying loads[J]. IEEE Transactions on Power Systems，1995，10（3）:1540-1545.
[23]	CAI J，HAO L，XU Q，et al. Reliability assessment of renewable energy integrated power systems with an extendable Latin hypercube importance sampling method[J]. Sustainable Energy Technologies and Assessments，2022，50，101792.
[24]	MOHAMMED N A. Comparing halton and sobol sequences in integral evaluation[J]. Zanco Journal of Pure and Applied Sciences，2019，31（1）:32-39.
[25]	CERVAN D，CORONADO A M，LUYO J E. Cluster-based stratified sampling for fast reliability evaluation of composite power systems based on sequential Monte Carlo simulation[J]. International Journal of Electrical Power& Energy Systems，2023，147，108813.
[26]	ALMEIDA D B，BORGES C L T，OLIVEIRA G C，et al. Multi-area reliability assessment based on importance sampling，MCMC and stratification to incorporate variable renewable sources[J]. Electric Power Systems Research，2021，193，107001.
[27]	WARSHALL S. A theorem on boolean matrices[J]. Journal of the ACM（JACM），1962，9（1）:11-12.
[28]	BIELECKI W，KRASKA K，KLIMEK T. Using basis dependence distance vectors in the modified floyd-warshall algorithm[J]. Journal of Combinatorial Optimization，2015，30:253-275.
[29]	张世龙，沈玉利. 稀疏矩阵情况下 Warshall 算法的改进[J]. 计算机工程与应用，2008，44（28）:60-61.
[30]	WANG Z，WU Y，XU Y，et al. An efficient algorithm to determine the connectivity of complex directed networks[J]. IEEE Transactions on Cybernetics，2020，52（7）:7164-7171.
[31]	贺金川，刘晓航，郑山锁，等. 基于三角形算法的电力系统连通可靠性分析[J]. 防灾减灾工程学报，2020，40（5）:764-770.
[32]	AINI A，SALEHIPOUR A. Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem[J]. Applied Mathematics Letters，2012，25（1）:1-5.
[33]	Federal Emergency Management Agency. Hazus earthquake model technical manual，hazus 5.1[R]. Washington D C:Federal Emergency Management Agency，2022.