An efficient variable ordering heuristic for binary decision diagram–based reliability analysis of network with imperfect nodes

While most of the research efforts on network reliability analysis have focused on networks with imperfect links but perfectly reliable nodes, binary decision diagram–based methods have recently been developed to determine reliability of networks with imperfect links and imperfect nodes. The smaller...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the Institution of Mechanical Engineers. Part O, Journal of risk and reliability Journal of risk and reliability, 2017-12, Vol.231 (6), p.628-642
Main Authors: Pan, Zhusheng, Xing, Liudong, Mo, Yuchang, Li, Wenbai
Format: Article
Language:English
Subjects:
Decision analysis
Empirical analysis
Heuristic
Links
Network reliability
Networks
Reliability analysis
Searching
System reliability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:While most of the research efforts on network reliability analysis have focused on networks with imperfect links but perfectly reliable nodes, binary decision diagram–based methods have recently been developed to determine reliability of networks with imperfect links and imperfect nodes. The smaller the binary decision diagram size is, the better the performance of the binary decision diagram–based algorithm will be. The binary decision diagram size heavily depends on the chosen variable ordering. As finding the optimal variable ordering is a nondeterministic polynomial time-complete problem, a heuristic is typically used. Various heuristics based on depth-first search, breadth-first search, and network-driven search have been developed for network reliability analysis. However, they often assume the networks have perfectly reliable nodes. This article advances the state-of-the-art by proposing a new ordering heuristic for the binary decision diagram–based reliability analysis of networks with imperfect links/edges and nodes. Empirical studies show that the proposed new ordering heuristic can generate significantly smaller binary decision diagram size for a wide variety of network structures than the traditional depth-first search–based, breadth-first search–based, network-driven search–based heuristics for most cases, enabling efficient binary decision diagram–based reliability analysis of large-scale networks considering both link and node failures. Robustness of the proposed heuristic is also investigated through empirical studies.
ISSN:1748-006X
1748-0078
DOI:10.1177/1748006X17721789