Details

Autor(en) / Beteiligte

• Niu, Yi-Feng
• Song, Yi-Fan
• Xu, Xiu-Zhen
• Zhao, Xia

Titel

Efficient reliability computation of a multi-state flow network with cost constraint

Ist Teil von

• Reliability engineering & system safety, 2022-06, Vol.222, p.108393, Article 108393

Ort / Verlag

Barking: Elsevier Ltd

Erscheinungsjahr

2022

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• •This paper presents a new search method to find (d,b)-minimal paths ((d, b)-MPs).•A correlation between (d, b)-MP and minimum cost circulation is established.•The presented method searches for d-MPs via minimum feasible circulations.•The presented method outperforms the existing ones in finding all (d, b)-MPs. The reliability and cost integrated performance measure R(d,b) of a multi-state flow network, defined as the probability of sending a flow of d units from the source to the sink with the total transmission cost no more than b, can be computed by means of (d, b)-minimal paths ((d, b)-MPs). The existing methods search for (d, b)-MPs by solving a large Diophantine system or several Diophantine subsystems that are shown to be NP-hard, then the computational efforts are prohibitive. This paper proposes a new search method for (d, b)-MPs, and major contributions include: (1) a correlation between (d, b)-MPs and minimum cost circulations is established, enabling the solution of (d, b)-MPs to be accomplished via minimum cost circulations; (2) a distinctive method merging the well-known capacity scaling algorithm and a decomposition technique is presented to find (d, b)-MPs. In contrast to the existing methods, the presented algorithm seeks for (d, b)-MPs without depending upon the solutions of Diophantine system and generating any duplicate (d, b)-MPs. An illustration of the proposed algorithm is presented, and computational results indicate the advantage of our algorithm over the existing methods.