A Minimal Path-Based Method for Computing Multistate Network Reliability
Most of modern technological networks that can perform their tasks with various distinctive levels of efficiency are multistate networks, and reliability is a fundamental attribute for their safe operation and optimal improvement. For a multistate network, the two-terminal reliability at demand leve...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/8060794 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849403418384269312 |
|---|---|
| author | Xiu-Zhen Xu Yi-Feng Niu Can He |
| author_facet | Xiu-Zhen Xu Yi-Feng Niu Can He |
| author_sort | Xiu-Zhen Xu |
| collection | DOAJ |
| description | Most of modern technological networks that can perform their tasks with various distinctive levels of efficiency are multistate networks, and reliability is a fundamental attribute for their safe operation and optimal improvement. For a multistate network, the two-terminal reliability at demand level d, defined as the probability that the network capacity is greater than or equal to a demand of d units, can be calculated in terms of multistate minimal paths, called d-minimal paths (d-MPs) for short. This paper presents an efficient algorithm to find all d-MPs for the multistate two-terminal reliability problem. To advance the solution efficiency of d-MPs, an improved model is developed by redefining capacity constraints of network components and minimal paths (MPs). Furthermore, an effective technique is proposed to remove duplicate d-MPs that are generated multiple times during solution. A simple example is provided to demonstrate the proposed algorithm step by step. In addition, through computational experiments conducted on benchmark networks, it is found that the proposed algorithm is more efficient. |
| format | Article |
| id | doaj-art-8f038c0620fd4673874668e2ff662cbe |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-8f038c0620fd4673874668e2ff662cbe2025-08-20T03:37:16ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/80607948060794A Minimal Path-Based Method for Computing Multistate Network ReliabilityXiu-Zhen Xu0Yi-Feng Niu1Can He2School of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaSchool of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaSchool of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaMost of modern technological networks that can perform their tasks with various distinctive levels of efficiency are multistate networks, and reliability is a fundamental attribute for their safe operation and optimal improvement. For a multistate network, the two-terminal reliability at demand level d, defined as the probability that the network capacity is greater than or equal to a demand of d units, can be calculated in terms of multistate minimal paths, called d-minimal paths (d-MPs) for short. This paper presents an efficient algorithm to find all d-MPs for the multistate two-terminal reliability problem. To advance the solution efficiency of d-MPs, an improved model is developed by redefining capacity constraints of network components and minimal paths (MPs). Furthermore, an effective technique is proposed to remove duplicate d-MPs that are generated multiple times during solution. A simple example is provided to demonstrate the proposed algorithm step by step. In addition, through computational experiments conducted on benchmark networks, it is found that the proposed algorithm is more efficient.http://dx.doi.org/10.1155/2020/8060794 |
| spellingShingle | Xiu-Zhen Xu Yi-Feng Niu Can He A Minimal Path-Based Method for Computing Multistate Network Reliability Complexity |
| title | A Minimal Path-Based Method for Computing Multistate Network Reliability |
| title_full | A Minimal Path-Based Method for Computing Multistate Network Reliability |
| title_fullStr | A Minimal Path-Based Method for Computing Multistate Network Reliability |
| title_full_unstemmed | A Minimal Path-Based Method for Computing Multistate Network Reliability |
| title_short | A Minimal Path-Based Method for Computing Multistate Network Reliability |
| title_sort | minimal path based method for computing multistate network reliability |
| url | http://dx.doi.org/10.1155/2020/8060794 |
| work_keys_str_mv | AT xiuzhenxu aminimalpathbasedmethodforcomputingmultistatenetworkreliability AT yifengniu aminimalpathbasedmethodforcomputingmultistatenetworkreliability AT canhe aminimalpathbasedmethodforcomputingmultistatenetworkreliability AT xiuzhenxu minimalpathbasedmethodforcomputingmultistatenetworkreliability AT yifengniu minimalpathbasedmethodforcomputingmultistatenetworkreliability AT canhe minimalpathbasedmethodforcomputingmultistatenetworkreliability |