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

ZHENG Shansuo; CAI Guowei; WANG Kaige; TIAN Qi

doi:10.3724/j.gyjzG25071806

Volume 55 Issue 12

Dec. 2025

Turn off MathJax

Article Contents

Article Navigation > INDUSTRIAL CONSTRUCTION > 2025 > 55(12): 9-16

ZHENG Shansuo, CAI Guowei, WANG Kaige, TIAN Qi. Seismic Reliability Assessment of Lifeline Systems Based on an Improved Warshall Algorithm[J]. INDUSTRIAL CONSTRUCTION, 2025, 55(12): 9-16. doi: 10.3724/j.gyjzG25071806

Citation:

ZHENG Shansuo, CAI Guowei, WANG Kaige, TIAN Qi. Seismic Reliability Assessment of Lifeline Systems Based on an Improved Warshall Algorithm[J]. INDUSTRIAL CONSTRUCTION, 2025, 55(12): 9-16. doi: 10.3724/j.gyjzG25071806

Citation:

PDF( 1505 KB)

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

doi: 10.3724/j.gyjzG25071806

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

Received Date: 2025-07-18
Available Online: 2026-01-06
Publish Date: 2025-12-20

Abstract

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

FullText(HTML)

References(33)

References

[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.