# Efficient Enumeration ofd-Minimal Paths in Reliability Evaluation of Multistate Networks

Authors: Xiu-Zhen Xu; Yi-Feng Niu; Qing Li
Journal: Complexity
 (2019)

---

## Abstract

A number of real-world complex networks can be modeled as multistate networks for performance analysis. A multistate network consists of multistate components and possesses multiple different performance levels. For such a network, reliability is concerned with the probability of the network capacity level greater than or equal to a predetermined demand leveld. One major method for multistate network reliability evaluation is usingd-minimal paths. This paper proposes an efficient algorithm to findd-minimal paths. First, a new concept of qualified state vector is defined so as to fix a relatively smaller search space ofd-minimal paths, and a sufficient and necessary condition for a qualified state vector to bed-minimal path is established. Then, the max-flow algorithm and the enumeration algorithm are integrated to search ford-minimal paths in the determined search space that is recursively divided into subspaces such that the searching efficiency can be increased as much as possible. Both analytical and numerical results show that the proposed algorithm is more efficient in finding alld-minimal paths. In addition, a case study related to power transmission network is performed to demonstrate the implication of network reliability.


---

## Body

## 1. Introduction

Network models have been extensively applied in analyzing real-world complex systems, such as computer and information networks [1, 2], power transmission networks [3], manufacturing networks [4], logistics networks [5–13], and gene regulatory networks [14–16]. From the viewpoint of network reliability, network model is generally classified as binary state network model and multistate network model [10]. Binary state network model assumes two states for network components: fully working or completely failed [17–20]. For example, in a gene regulatory network, the state of each gene is described by two levels: either active (fully working) or inactive (completely failed) [20], so it can be modeled as a binary state network. However, a number of actual complex systems are often affected by various random parameters due to external or internal uncertainties [21], such that they could exhibit multiple behaviors. In such situation, binary state network model is insufficient in network analysis. For example, consider a power transmission network constructed by a set of nodes (high voltage transmission towers, high voltage substations, or power plants) and a set of arcs (transmission lines). Each transmission line linking two nodes is combined with several physical lines and each physical line may provide a specific capacity or fail with a probability [3]. That is, each transmission line has several capacities due to complete failure, partial failure or maintenance, etc. In this sense, the behavior of the power transmission network is multistate. For practical applications, binary state network model has been extended and replaced by multistate network model to characterize complex behaviors of multistate networks.A multistate network is composed of multistate components and holds a finite number of different states for performance rate. For such a network, an interesting question is to evaluate its reliability defined as the probability of the network capacity level greater than or equal to a predetermined demand leveld. Researchers have presented various algorithms to evaluate the reliability of multistate networks, including direct algorithm [22–24] and indirect algorithm [25–33]. Indirect algorithm is often called network-based algorithm established in terms of minimal paths or minimal cuts. One common indirect method for reliability computation of multistate networks is based on minimal path vectors to leveld (d-minimal paths for short) [25–33]. And, all of these methods pay attention to the enumeration ofd-minimal paths.Two important types of models have been reported to solved-minimal paths. One is proposed by Lin et al. [25], and the other is proposed by Yeh [26]. All minimal paths are assumed to be known; the model by Lin et al. [25] is constructed via the network structure and the flow conservation law. A path is a sequence of arcs that connect the source node to the sink node, and a minimal path is such a path that removing any arc will make it no longer a path. Afterward, some algorithms have been developed to findd-minimal paths in terms of the model by Lin et al. [25], such as the methods by Lin [27], Yeh [28], Chen and Lin [29], and Xu et al. [13]. It is noted that there are two drawbacks for these methods in [13, 25, 27–29]. The first is that they require all minimal paths as prior knowledge, which is an NP-hard problem, and the second is the extra burden for removing duplicated-minimal paths.The model by Yeh [26] requires no minimal paths knowledge, and thus possesses an advantage relative to the model by Lin et al. [25]. But, one remarkable limitation of Yeh's model is that a huge number of state vectors need to be enumerated, which leads to high computational complexity. Recently, Niu et al. [30] have attempted to improve the method of Yeh [26] by means of the concept of lower capacity bound, but the efficiency of their method highly depends on the network structure and the specified demand level d. In particular, the method by Niu et al. [30] is even inferior to the one by Yeh when the demand level is low. The method by Xu and Niu [31] is another improvement to the method by Yeh [26] and is proven to be more efficient in solvingd-minimal paths.The enumeration ofd-minimal paths is a difficult task because it is an NP-hard problem [23], and developing an efficient algorithm is worthwhile from the viewpoint of reliability evaluation. Therefore, this paper focuses on the efficient enumeration ofd-minimal paths in multistate network reliability evaluation. More explicitly, the incremental contributions of this paper are twofold. First, a new concept of qualified state vector is defined to determine the search space ofd-minimal paths more accurately, and a sufficient and necessary condition for a qualified state vector to bed-minimal path is established. Second, the max-flow algorithm and the enumeration method are integrated to search ford-minimal paths in the determined search space that is recursively divided into subspaces so that the efficiency of findingd-minimal paths can be increased as much as possible. Both analytical and numerical results indicate that the proposed algorithm compares favorably with the existing algorithm. Finally, a case study related to power transmission network is performed to demonstrate the implications of network reliability.The rest of this paper is arranged as follows: Section2 introduces multistate network model and reviews the concept of network reliability. In Section 3, a concept of qualified state vector is introduced, and a sufficient and necessary condition for a qualified state vector to bed-minimal path is proposed. Moreover, the main ideas for searching ford-minimal paths are discussed, based on which an algorithm is developed along with analyses on its time complexity. In Section 4, an illustrative example and a numerical example are provided to validate the effectiveness and efficiency of the proposed algorithm. A practical case is studied in Section 5 to demonstrate the implications of network reliability. The final section presents some concluding remarks.


## 2. Multistate Network Model and Network Reliability

### 2.1. Multistate Network Model

Mathematically, a multistate network is modeled as a directed graphG(N,A,Ω), where N={s,1,2,…,m,t} is the set of nodes, A=ai∣1≤i≤n is the set of arcs, and Ω=c∣c=c1,c2,…,cn,ci∈Kifor1≤i≤n is the universal space of state vectors. The state (capacity) of arc ai defined by ci is a nonnegative integer random variable ranging from the smallest value 0 to the largest value ui with a known probability distribution. A state vectorc = (c1, c2,…, cn) represents the current states of all arcs in the network. The state (capacity) of a network under state vector c is determined by the so-called structure functionM(c) denoting the maximum amount of flow that can be sent from the source node s to the sink node t when the sates of arcs are defined by c. For simplicity, the universal space Ω can be denoted by its smallest state vector l and largest state vector u as Ω=[l,u]. Let C be a set of state vectors, then C is a subset of Ω.For example, consider a multistate networkG(N,A,Ω) shown in Figure 1 with N={s,1,2,t}, A=a1,a2,a3,a4,a5,a6, and Ω = [(0, 0, 0, 0, 0, 0), (3, 2, 1, 1, 1, 2)] according to Table 1. For a state vectorc = (2, 1, 1, 1, 1, 2), the state of the network under c isM(c) = 3, that is, the maximum amount of flow that can be sent from the source node s to the sink node t is 3 when c1 = 2,  c2 = 1,  c3 = 1,  c4 = 1,  c5 =1,  c6 = 2. Given a set of state vector C=c1,c2,c3,c4,c5,c6∣1≤c1≤3,1≤c2≤2,0≤c3≤1,c4=0,c5=0,0≤c6≤2, its smallest state vector and largest state vector arelC = (1, 1, 0, 0, 0, 0) anduC = (3, 2, 1, 0, 0, 2), respectively.Table 1
The states of arcs in Figure1.
Arc States State probability distribution a 1 0 1 2 3 0.05 0.10 0.15 0.70 a 2 0 1 2 - 0.10 0.15 0.75 - a 3 0 1 - - 0.05 0.95 - - a 4 0 1 - - 0.05 0.95 - - a 5 0 1 - - 0.10 0.90 - - a 6 0 1 2 - 0.05 0.10 0.85 -Figure 1
A multistate two-terminal network.Following the literature in [25, 26, 28–33], this paper considers four assumptions: (1) the state/capacity of each arc is a nonnegative integer random variable following a given probability distribution; (2) the states/capacities of different arcs are statistically independent; (3) each node is perfectly reliable; (4) all flows in the network obey the flow conservation law, i.e., total flows into and from a node (other than the source and sink nodes) are all equal.


### 2.2. Network Reliability

Reliability is a fundamental attribute for the safe operation of modern technological networks [34], and generally speaking, it represents the ability of a network to achieve its intended function within a given environment. For a multistate network, the reliability index Rd is defined as the probability that at least d units of flow can be sent from the source node to the sink node or the probability that the network capacity level is greater than or equal to a predetermined demand leveld, that is Rd=Prc∣Mc≥d. Evidently, to calculate Rd, one direct way is to enumerate every state vector c of Ω by checking the conditionM(c) ≥d, and then sum up their probabilities. And yet, it is extremely time-consuming due to the huge number of state vectors in Ω for a multistate network. Instead, most of studies have focused on thed-minimal path method. Ad-minimal path c is the minimal state vector satisfyingM(c) =d. In other words, a state vector c is ad-minimal path if and only ifM(c) =d, andM(c –0(ai)) <d for each ci > 0, where 0(ai) = (0, …, 0, 1, 0, …, 0), i.e., the state of ai is 1 and the states of other arcs are 0. Given that alld-minimal paths of a network are found, Rd can be calculated by the well-known Inclusion-Exclusion method or Sum of Disjoint Product method. Therefore, findingd-minimal paths is the key for computing Rd. In the following discussions, we focus on how to efficiently search ford-minimal paths in a multistate network.


## 2.1. Multistate Network Model

Mathematically, a multistate network is modeled as a directed graphG(N,A,Ω), where N={s,1,2,…,m,t} is the set of nodes, A=ai∣1≤i≤n is the set of arcs, and Ω=c∣c=c1,c2,…,cn,ci∈Kifor1≤i≤n is the universal space of state vectors. The state (capacity) of arc ai defined by ci is a nonnegative integer random variable ranging from the smallest value 0 to the largest value ui with a known probability distribution. A state vectorc = (c1, c2,…, cn) represents the current states of all arcs in the network. The state (capacity) of a network under state vector c is determined by the so-called structure functionM(c) denoting the maximum amount of flow that can be sent from the source node s to the sink node t when the sates of arcs are defined by c. For simplicity, the universal space Ω can be denoted by its smallest state vector l and largest state vector u as Ω=[l,u]. Let C be a set of state vectors, then C is a subset of Ω.For example, consider a multistate networkG(N,A,Ω) shown in Figure 1 with N={s,1,2,t}, A=a1,a2,a3,a4,a5,a6, and Ω = [(0, 0, 0, 0, 0, 0), (3, 2, 1, 1, 1, 2)] according to Table 1. For a state vectorc = (2, 1, 1, 1, 1, 2), the state of the network under c isM(c) = 3, that is, the maximum amount of flow that can be sent from the source node s to the sink node t is 3 when c1 = 2,  c2 = 1,  c3 = 1,  c4 = 1,  c5 =1,  c6 = 2. Given a set of state vector C=c1,c2,c3,c4,c5,c6∣1≤c1≤3,1≤c2≤2,0≤c3≤1,c4=0,c5=0,0≤c6≤2, its smallest state vector and largest state vector arelC = (1, 1, 0, 0, 0, 0) anduC = (3, 2, 1, 0, 0, 2), respectively.Table 1
The states of arcs in Figure1.
Arc States State probability distribution a 1 0 1 2 3 0.05 0.10 0.15 0.70 a 2 0 1 2 - 0.10 0.15 0.75 - a 3 0 1 - - 0.05 0.95 - - a 4 0 1 - - 0.05 0.95 - - a 5 0 1 - - 0.10 0.90 - - a 6 0 1 2 - 0.05 0.10 0.85 -Figure 1
A multistate two-terminal network.Following the literature in [25, 26, 28–33], this paper considers four assumptions: (1) the state/capacity of each arc is a nonnegative integer random variable following a given probability distribution; (2) the states/capacities of different arcs are statistically independent; (3) each node is perfectly reliable; (4) all flows in the network obey the flow conservation law, i.e., total flows into and from a node (other than the source and sink nodes) are all equal.


## 2.2. Network Reliability

Reliability is a fundamental attribute for the safe operation of modern technological networks [34], and generally speaking, it represents the ability of a network to achieve its intended function within a given environment. For a multistate network, the reliability index Rd is defined as the probability that at least d units of flow can be sent from the source node to the sink node or the probability that the network capacity level is greater than or equal to a predetermined demand leveld, that is Rd=Prc∣Mc≥d. Evidently, to calculate Rd, one direct way is to enumerate every state vector c of Ω by checking the conditionM(c) ≥d, and then sum up their probabilities. And yet, it is extremely time-consuming due to the huge number of state vectors in Ω for a multistate network. Instead, most of studies have focused on thed-minimal path method. Ad-minimal path c is the minimal state vector satisfyingM(c) =d. In other words, a state vector c is ad-minimal path if and only ifM(c) =d, andM(c –0(ai)) <d for each ci > 0, where 0(ai) = (0, …, 0, 1, 0, …, 0), i.e., the state of ai is 1 and the states of other arcs are 0. Given that alld-minimal paths of a network are found, Rd can be calculated by the well-known Inclusion-Exclusion method or Sum of Disjoint Product method. Therefore, findingd-minimal paths is the key for computing Rd. In the following discussions, we focus on how to efficiently search ford-minimal paths in a multistate network.


## 3. Development ofd-Minimal Path Algorithm

### 3.1. Determination of Search Space ofd-Minimal Paths

Theoretically, the universal spaceΩ=c∣c=c1,c2,…,cn,ci∈Kifor1≤i≤n is the whole search space ofd-minimal paths, where Ki=0,1,…,ui is the set of states of ai. It is a cumbersome task to search ford-minimal paths in Ω due to the large number of state vectors. The definition ofd-minimal path indicates that if a state vector c is ad-minimal path, two conditions must be met:M(c) =d, andM(c – 0(ai)) <d for each ci > 0. As the source node s and the sink node t are two special nodes with the unique feature that s only has outgoing arcs and t only has incoming arcs, when c is ad-minimal path, the following conditions must be satisfied:(1)∑ai∈s,•ci=dfor0≤ci≤min⁡ui,d(2)∑aj∈•,tcj=dfor0≤cj≤min⁡uj,dNow we define a new concept called qualified state vector to determine a smaller search space ofd-minimal paths compared to Ω.Definition 1.
For a given demand leveld, a state vector c is called a qualified state vector if c satisfies conditions (1) and (2).The following theorem points out one basic property of qualified state vectors.Theorem 2.
Ifc is a qualified state vector, thenM(c) ≤d.Proof.
Note that(s,•) is a minimal cut of the network. Because ∑ai∈(s,•)ci=d,M(c) ≤d follows from the max-flow min-cut theorem of network flows [35, 36].
Obviously, ad-minimal path is a qualified state vector, but a qualified state vector is not necessarily ad-minimal path. In conditions (1) and (2), suppose (s,•)=as1,as2,…,asv and (•,t)=at1,at2,…,atw. Letδj = (cs1j, cs2j,…, csvj, ct1j, ct2j,…, ctwj) (1 ≤j ≤H) represent a combination satisfying conditions (1) and (2), and Cj=c∣ci=cijforai∈s,•∪•,t,0≤ci≤min⁡ui,d for ai∈A∖((s,•)∪(•,t)) (1 ≤j ≤H) is a set of state vectors corresponding toδj, then every state vector inCj is a qualified state vector. Thus, C1∪C2∪…∪CH composes a new search space that is a subspace of the universal space Ω and includes all qualified state vectors. Because ad-minimal path is a qualified state vector, the search space ofd-minimal paths can be limited to C1∪C2∪…∪CH instead of Ω.
For illustration, we consider to find 3-minimal paths in Figure1. Note that (s,•)=a1,a5, and (•,t)=a2,a6, then all possible combinations satisfying conditions (1) and (2) areδ1 = (2, 1, 1, 2),δ2 = (2, 1, 2, 1),δ3 = (3, 0, 1, 2), andδ4 = (3, 0, 2, 1). Thus, C1=c1,c2,c3,c4,c5,c6∣c1=2,c2=1,0≤c3≤1,0≤c4≤1,c5=1,c6=2, C2=c1,c2,c3,c4,c5,c6∣c1=2,c2=2,0≤c3≤1,0≤c4≤1,c5=1,c6=1, C3=c1,c2,c3,c4,c5,c6∣c1=3,c2=1,0≤c3≤1,0≤c4≤1,c5=0,c6=2, and C4=c1,c2,c3,c4,c5,c6∣c1=3,c2=2,0≤c3≤1,0≤c4≤1,c5=0,c6=1. That is, all 3-minimal paths are included in search space C1∪C2∪C3∪C4.


### 3.2. The Condition for Qualified State Vector to Bed-Minimal Path

When the amount of flow sent froms to t isd, ad-flow is a vector (f1d, f2d,…, fnd) consisting of flow fid through each arc ai (1 ≤i ≤n) [31]. Thus, according to the theory of network flows [35, 36], a state vector c is ad-flow if and only ifM(c) =d and c satisfies the flow conservation law. The following theorem gives the condition for a qualified state vector to be ad-flow.Theorem 3.
A qualified state vectorc is ad-flow if and only if c satisfies the flow conservation law.Proof.
If a qualified state vectorc satisfies the flow conservation law, then c is a feasible flow; meanwhile, ∑ai∈(s,•)ci=d and ∑aj∈(•,t)cj=d, which meansM(c) =d. Hence,c is ad-flow.
Ad-flow is not necessarily ad-minimal path, and their relationship is determined by Lemma 4 proposed by Xu and Niu [31].Lemma 4.
Ad-flow c is ad-minimal path if and only if there is no directed cycle in it.Thus, we can obtain the following conclusion.Theorem 5.
A qualified state vectorc is ad-minimal path if and only if c satisfies the flow conservation law and there is no directed cycle in it.Proof.
Directly from Theorem3 and Lemma 4.
Theorem5 explicitly presents the sufficient and necessary condition for a qualified state vector to bed-minimal path. In the subsequent discussions, Theorem 5 will be utilized to search ford-minimal paths in setCj (1 ≤j≤H).


### 3.3. Searching ford-Minimal Paths in Set Cj (1 ≤j ≤H)

Recall that every state vector inCj (1 ≤j≤H) is a qualified state vector, so the enumeration method, by Theorem 5, can be used to search ford-minimal paths in setCj. However, it is still not practical to enumerate every state vector ofCj (1 ≤j ≤H), and there is room for improvement. Next, we will detail how to integrate the max-flow algorithm with the enumeration method to search ford-minimal paths in setCj (1 ≤j ≤H).For every setCj (1 ≤j≤H), we consider its largest state vector uCj. IfM (uCj) <d, thenM (c) ≤M (uCj) <d for any state vector c∈C, which indicates there is nod-minimal path inCj by definition, and thusCj is discarded (i.e., there is no need to enumerateCj). Consequently, only the caseM (uCj) =d needs to be discussed. The following theorem reveals that oned-flow can be derived from setCj whenM (uCj) =d.Theorem 6.
For setCj (1 ≤j ≤H), ifM(uCj) =d, then oned-flow (f1d,f2d,…, fnd) can be derived fromCj.Proof.
Firstly, note thatuiCj=liCj for ai∈((s,•)∪(•,t)), and liCj= 0 for ai∈A∖((s,•)∪(•,t)). SinceM(uCj) =d, the maximum amount of flow that can be sent from s to t isd, and moreover the max-flow of the network under uCj is just ad-flow (f1d,f2d,…,fnd) according to the theory of network flows [35, 36]. As fid=uiCj=liCj for ai∈((s,•)∪(•,t)),  liCj=0≤fid≤uiCj for ai∈A∖((s,•)∪(•,t)), then we have liCj≤fid≤uiCj for ai∈A.
In Theorem6, the max-flow algorithm can be employed to computeM (uCj), and simultaneously determine ad-flow (f1d,f2d,…,fnd) whenM(uCj) =d. By Lemma 4, if (f1d,f2d,…,fnd) contains no directed cycle, it is ad-minimal path. After finding ad-flow (f1d,f2d,…,fnd), letAd(Cj) = ai∣ai∈A∖s,•∪•,t&fid>liCj. Note that uiCj=fid=liCj for ai∈((s,•)∪(•,t)), and liCj≤fid≤uiCj for ai∈A∖((s,•)∪(•,t)). IfAd(Cj) = Φ, then fid=liCj for ai∈A∖((s,•)∪(•,t)). As a result, we havefid=liCj for ai∈A. That is, lCj=(f1d,f2d,…,fnd) whenAd(Cj) = Φ. In such a case, asM(lCj) =d and lCj is the smallest state vector in setCj, it is impossible for any other state vector ofCj to bed-minimal path, and thusCj is discarded.
IfAd(Cj) ≠ Φ, postulate thatAd(Cj) = ax1,ax2,…,axq, then we havefid>liCj for ai∈Ad(Cj), and fid=liCj for ai∈A∖Ad(Cj). Based on the obtainedd-flow (f1d,f2d,…,fnd) andAd(Cj) = {ax1,ax2,…,axq}, setCj can be divided into disjoint subsets. The technique for dividingCj is originally reported by Jane and Laih [23], and is adapted for use in this paper. Pivoting on arcs ax1,ax2,…,axq one by one,Cj is divided into C1j, C2j,…, Cqj and C0j  as follows:
(1) Pivot on arcax1:(3)C1j=c1,c2,…,cn∣lx1Cj≤cx1<fx1d,ci∈KiCjforai∈A∖ax1;
(2) Pivot on arcax2:(4)C2j=c1,c2,…,cn∣fx1d≤cx1≤ux1Cj,lx2Cj≤cx2<fx2d,ci∈KiCjforai∈A∖ax1,ax2;
…
( q ) Pivot on arc axq:(5)Cqj=c1,c2,…,cn∣fid≤ci≤uiCjforai∈ax1,ax2,…,axq-1,lxqCj≤cxq<fxqd,ci∈KiCjforai∈A∖AdCj;
(q+1) (6)C0j=c1,c2,…,cn∣fid≤ci≤uiCjforai∈AdCj,ci∈KiCjforai∈A∖AdCj.According to Jane and Laih [23], subsets C0j, C1j, C2j,…, and Cqj satisfy two properties: (1)Cj = C0j∪C1j∪C2j∪…∪Cqj; (2) C0j, C1j, C2j,⋯, and Cqj are disjoint. Meanwhile, it is obvious that all of the state vectors in Ckj (0 ≤k ≤q) are still qualified state vectors.The remaining work is to search ford-minimal paths in these subsets. First, we consider C0j, and note that thed-flow (f1d,f2d,…,fnd) derived fromCj is the smallest state vector in C0j, then all of the other state vectors in C0j are nod-minimal paths by definition. In such a case, there is no need to enumerate the state vectors in C0j, i.e., C0j is discarded.Now we considerCkj for 2 ≤k ≤q. IfM (uCkj) <d, then there exists nod-minimal path in Ckj, and Ckj is discarded either. But, ifM(uCkj) =d, the existence ofd-minimal paths in Ckj is uncertain. In this case, because all of the state vectors in Ckj (0 ≤k ≤q) are still qualified state vectors, by Theorem 5, the enumeration method can be used to search ford-minimal paths in Ckj.Finally, we considerC1j. IfM (uC1j) <d, then there exists nod-minimal path in C1j, and C1j  is discarded. Now we discuss the caseM (uC1j) =d. Observe that C1j = c1,c2,…,cn∣lx1Cj≤cx1<fx1d,ci∈KiCjforai∈A∖ax1 which means lC1j=lCj, then C1j can be coped with in the same way asCj. That is, ad-flow (f1d,f2d,…,fnd) can be obtained from C1j whenM(C1j) =d by Theorem 6, and then C1j is similarly decomposed into disjoint subsets that are discussed in the same way as the subsets derived fromCj. This decomposition process will stop when there exists no subset C∗ meeting lC∗=lCj andM(uC∗) =d. At this moment, all of thed-minimal paths in setCj have been found.


### 3.4. The Developed Algorithm

According to the above discussions, we now present an algorithm for findingd-minimal paths in a multistate network G(N,A,Ω). To make the proposed algorithm more understandable, we use two parts, Algorithm A and Algorithm B, to describe it hereunder.Algorithm A.
Findingd-minimal paths in a multistate network G(N,A,Ω).
Input. A multistate network G(N,A,Ω) with demand leveld.
Output. Alld-minimal paths.
A. Step 1. Use the enumeration method to solve all of the combinations satisfying conditions (1) and (2), and then determine the search space C1∪C2∪…∪CH.
A. Step 2. For eachCj(1 ≤j ≤H), letC=Ci and callAlgorithm B to search ford-minimal paths inC.Algorithm B.
Findingd-minimal paths in setC.
B. Step 1. ComputeM(uC). IfM(uC) <d, there is nod-minimal path inC, and stop.
B. Step 2. Find ad-flow (f1d,f2d,…,fnd) inC, if it contains no directed cycle, it is ad-minimal path.
B. Step 3. ComputeAd(C) = ai∣ai∈A∖s,•∪•,t&fid>liCj. IfAd(C) =Φ, then stop; otherwise, supposeAd(C) = {ax1,ax2,…,axq}.
B. Step 4. Divide C intoq+1 nonempty disjoint subsets C0, C1, C2,…, Cq.
B. Step 5. Ifq >1, computeM(uCk) (2 ≤k≤q). IfM(uCk) <d, there is nod-minimal path in Ck; otherwise,for each c∈Ck (2 ≤k ≤q), if c satisfies the flow conservation law and there is no directed cycle in it, it is ad-minimal path.
B. Step 6. LetC = C1, and go toB.Step 1.To help follow the procedure of the proposed algorithm, we briefly explain the role of every step. In Algorithm A, A. Sep 1 is a proprocessing step for determining a smaller search space ofd-minimal paths, which includes H sets, and A. Step 2 is to search ford-minimal paths of each setCj by calling Algorithm B. Note that Algorithm B is a recursive algorithm for solvingd-minimal paths. B. Step 1 checks whether there may existd-minimal paths in C by computing the maximum flow under the largest state vector. B. Step 2 is to find ad-flow and to check whether it is ad-minimal path. Once ad-flow is obtained, B. Step 3 and B. Step 4 are to divide set C intoq+1 disjoint subsets. B. Step 5 searches ford-minimal paths in subsets C2,…, Cq. Subset C1 is regarded as a new set to be solved from the beginning step, i.e., B. Step 1 (a new iteration), and thus B. Step 6 is to put subset C1 into the next iteration.It is noteworthy that the major characteristics of the proposed algorithm are twofold. First, a smaller search space ofd-minimal paths is determined in A. Step 1. Second, the search space is recursively divided into subspaces such that the traditional max-flow algorithm (find ad-flow in B. Step 2) and the enumeration method (check whether c satisfies the flow conservation law in B. Step 5) are integrated to search ford-minimal paths in subsets. Notably, there is no need to enumerate subset C0, and whenM(uCk) <d (2 ≤k ≤q) holds in B. Step 5, there is also no need to enumerate subset Ck (nod-minimal paths exist in Ck either), which no doubt contributes to the efficiency improvement in searching ford-minimal paths.Now, we discuss the time complexity of the proposed algorithm. Complexity analysis of Algorithm A: it takesO(n(∏ai∈(s,•)(1+min{ui,d})+∏aj∈(•,t)(1+min{uj,d}))) time to solve all of the combinations satisfying conditions (1) and (2). After obtaining the combinations, it then needsO(Hn) time to determine the search space. As a result, A. Step 1 totally requires O(n(∏ai∈(s,•)(1+min{ui,d})+∏aj∈(•,t)(1+min{uj,d}))) time. The time complexity of A. Step 2 is obviously determined by the time complexity of Algorithm B. Complexity analysis of Algorithm B: B. Step 1 takesO(mn2) time to computeM(uC) [37]. OnceM(uC) =d is determined, ad-flow (f1d,f2d,…,fnd) can be obtained inO(n) time, and checking a directed cycle needsO(m) time. Thus, B. Step 2 requiresO(m+n) time to check whetherd-flow (f1d,f2d,…,fnd) is ad-minimal path or not. B. Step 3 requiresO(n) time to computeAd(C). B. Step 4 takesO(n) time to divide set C. B. Step 6 takesO(n) time to implement assignment operation. Therefore, the algorithm totally takesO(mn2) time without consideration of the time complexity of B. Step 5. Since solving alld-minimal paths is an NP-hard problem, the time complexity of the proposed algorithm mainly depends on B. Step 5 that employs the enumeration method to search ford-minimal paths. The number of enumerated state vectors in B. Step 5 is upper bounded by C1∪C2∪…∪CH, i.e., H∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d}), and it takesO(m) time to check whether a qualified state vector satisfies the flow conservation law, andO(m) time to check a directed cycle. Thus, B. Step 5 takes O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})) time in the worst case. Thus, the time complexity of Algorithm B is O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})) in the worst case. As a result, the time complexity of the proposed algorithm is O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})).We compare the proposed algorithm with the existing algorithms theoretically in terms of time complexity. Note that the algorithms in [13, 27, 29] are all based on the model proposed by Lin et al. [25], so they have the same time complexity as the algorithm by Lin et al. [25]. The time complexity of the algorithm by Lin et al. [25] is Ompmin⁡p+d-1d,∏i=1p1+min⁡CPi,d where p is the number of minimal paths andO(p) =O(2m), and the time complexity of both the algorithm by Yeh [26] and the modified algorithm by Xu and Niu [31] is O((m+n)∏ai∈A(1+minui,d)). As H is the total number of possible combinations satisfying conditions (1) and (2), it is trivial to have H<∏ai∈(s,•)∪(•,t)(1+min{ui,d}), and thus O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d}))≤O(m∏ai∈A(1+min{ui,d})) ≤ O((m+n)∏ai∈A(1+min{ui,d})). Furthermore, notice that O((m+n)∏ai∈A1+minui,d)≪Ompmin⁡p+d-1d,∏i=1p1+min⁡CPi,d [26]. Therefore, we can obtain O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})) ≤ O((m+n)∏ai∈A1+min⁡ui,d)≪Ompmin⁡p+d-1d,∏i=1p1+min⁡CPi,d. That is, the proposed algorithm compares favorably with the algorithms of Lin et al. [25], Yeh [26], and Xu and Niu [31] in terms of time complexity.


## 3.1. Determination of Search Space ofd-Minimal Paths

Theoretically, the universal spaceΩ=c∣c=c1,c2,…,cn,ci∈Kifor1≤i≤n is the whole search space ofd-minimal paths, where Ki=0,1,…,ui is the set of states of ai. It is a cumbersome task to search ford-minimal paths in Ω due to the large number of state vectors. The definition ofd-minimal path indicates that if a state vector c is ad-minimal path, two conditions must be met:M(c) =d, andM(c – 0(ai)) <d for each ci > 0. As the source node s and the sink node t are two special nodes with the unique feature that s only has outgoing arcs and t only has incoming arcs, when c is ad-minimal path, the following conditions must be satisfied:(1)∑ai∈s,•ci=dfor0≤ci≤min⁡ui,d(2)∑aj∈•,tcj=dfor0≤cj≤min⁡uj,dNow we define a new concept called qualified state vector to determine a smaller search space ofd-minimal paths compared to Ω.Definition 1.
For a given demand leveld, a state vector c is called a qualified state vector if c satisfies conditions (1) and (2).The following theorem points out one basic property of qualified state vectors.Theorem 2.
Ifc is a qualified state vector, thenM(c) ≤d.Proof.
Note that(s,•) is a minimal cut of the network. Because ∑ai∈(s,•)ci=d,M(c) ≤d follows from the max-flow min-cut theorem of network flows [35, 36].
Obviously, ad-minimal path is a qualified state vector, but a qualified state vector is not necessarily ad-minimal path. In conditions (1) and (2), suppose (s,•)=as1,as2,…,asv and (•,t)=at1,at2,…,atw. Letδj = (cs1j, cs2j,…, csvj, ct1j, ct2j,…, ctwj) (1 ≤j ≤H) represent a combination satisfying conditions (1) and (2), and Cj=c∣ci=cijforai∈s,•∪•,t,0≤ci≤min⁡ui,d for ai∈A∖((s,•)∪(•,t)) (1 ≤j ≤H) is a set of state vectors corresponding toδj, then every state vector inCj is a qualified state vector. Thus, C1∪C2∪…∪CH composes a new search space that is a subspace of the universal space Ω and includes all qualified state vectors. Because ad-minimal path is a qualified state vector, the search space ofd-minimal paths can be limited to C1∪C2∪…∪CH instead of Ω.
For illustration, we consider to find 3-minimal paths in Figure1. Note that (s,•)=a1,a5, and (•,t)=a2,a6, then all possible combinations satisfying conditions (1) and (2) areδ1 = (2, 1, 1, 2),δ2 = (2, 1, 2, 1),δ3 = (3, 0, 1, 2), andδ4 = (3, 0, 2, 1). Thus, C1=c1,c2,c3,c4,c5,c6∣c1=2,c2=1,0≤c3≤1,0≤c4≤1,c5=1,c6=2, C2=c1,c2,c3,c4,c5,c6∣c1=2,c2=2,0≤c3≤1,0≤c4≤1,c5=1,c6=1, C3=c1,c2,c3,c4,c5,c6∣c1=3,c2=1,0≤c3≤1,0≤c4≤1,c5=0,c6=2, and C4=c1,c2,c3,c4,c5,c6∣c1=3,c2=2,0≤c3≤1,0≤c4≤1,c5=0,c6=1. That is, all 3-minimal paths are included in search space C1∪C2∪C3∪C4.


## 3.2. The Condition for Qualified State Vector to Bed-Minimal Path

When the amount of flow sent froms to t isd, ad-flow is a vector (f1d, f2d,…, fnd) consisting of flow fid through each arc ai (1 ≤i ≤n) [31]. Thus, according to the theory of network flows [35, 36], a state vector c is ad-flow if and only ifM(c) =d and c satisfies the flow conservation law. The following theorem gives the condition for a qualified state vector to be ad-flow.Theorem 3.
A qualified state vectorc is ad-flow if and only if c satisfies the flow conservation law.Proof.
If a qualified state vectorc satisfies the flow conservation law, then c is a feasible flow; meanwhile, ∑ai∈(s,•)ci=d and ∑aj∈(•,t)cj=d, which meansM(c) =d. Hence,c is ad-flow.
Ad-flow is not necessarily ad-minimal path, and their relationship is determined by Lemma 4 proposed by Xu and Niu [31].Lemma 4.
Ad-flow c is ad-minimal path if and only if there is no directed cycle in it.Thus, we can obtain the following conclusion.Theorem 5.
A qualified state vectorc is ad-minimal path if and only if c satisfies the flow conservation law and there is no directed cycle in it.Proof.
Directly from Theorem3 and Lemma 4.
Theorem5 explicitly presents the sufficient and necessary condition for a qualified state vector to bed-minimal path. In the subsequent discussions, Theorem 5 will be utilized to search ford-minimal paths in setCj (1 ≤j≤H).


## 3.3. Searching ford-Minimal Paths in Set Cj (1 ≤j ≤H)

Recall that every state vector inCj (1 ≤j≤H) is a qualified state vector, so the enumeration method, by Theorem 5, can be used to search ford-minimal paths in setCj. However, it is still not practical to enumerate every state vector ofCj (1 ≤j ≤H), and there is room for improvement. Next, we will detail how to integrate the max-flow algorithm with the enumeration method to search ford-minimal paths in setCj (1 ≤j ≤H).For every setCj (1 ≤j≤H), we consider its largest state vector uCj. IfM (uCj) <d, thenM (c) ≤M (uCj) <d for any state vector c∈C, which indicates there is nod-minimal path inCj by definition, and thusCj is discarded (i.e., there is no need to enumerateCj). Consequently, only the caseM (uCj) =d needs to be discussed. The following theorem reveals that oned-flow can be derived from setCj whenM (uCj) =d.Theorem 6.
For setCj (1 ≤j ≤H), ifM(uCj) =d, then oned-flow (f1d,f2d,…, fnd) can be derived fromCj.Proof.
Firstly, note thatuiCj=liCj for ai∈((s,•)∪(•,t)), and liCj= 0 for ai∈A∖((s,•)∪(•,t)). SinceM(uCj) =d, the maximum amount of flow that can be sent from s to t isd, and moreover the max-flow of the network under uCj is just ad-flow (f1d,f2d,…,fnd) according to the theory of network flows [35, 36]. As fid=uiCj=liCj for ai∈((s,•)∪(•,t)),  liCj=0≤fid≤uiCj for ai∈A∖((s,•)∪(•,t)), then we have liCj≤fid≤uiCj for ai∈A.
In Theorem6, the max-flow algorithm can be employed to computeM (uCj), and simultaneously determine ad-flow (f1d,f2d,…,fnd) whenM(uCj) =d. By Lemma 4, if (f1d,f2d,…,fnd) contains no directed cycle, it is ad-minimal path. After finding ad-flow (f1d,f2d,…,fnd), letAd(Cj) = ai∣ai∈A∖s,•∪•,t&fid>liCj. Note that uiCj=fid=liCj for ai∈((s,•)∪(•,t)), and liCj≤fid≤uiCj for ai∈A∖((s,•)∪(•,t)). IfAd(Cj) = Φ, then fid=liCj for ai∈A∖((s,•)∪(•,t)). As a result, we havefid=liCj for ai∈A. That is, lCj=(f1d,f2d,…,fnd) whenAd(Cj) = Φ. In such a case, asM(lCj) =d and lCj is the smallest state vector in setCj, it is impossible for any other state vector ofCj to bed-minimal path, and thusCj is discarded.
IfAd(Cj) ≠ Φ, postulate thatAd(Cj) = ax1,ax2,…,axq, then we havefid>liCj for ai∈Ad(Cj), and fid=liCj for ai∈A∖Ad(Cj). Based on the obtainedd-flow (f1d,f2d,…,fnd) andAd(Cj) = {ax1,ax2,…,axq}, setCj can be divided into disjoint subsets. The technique for dividingCj is originally reported by Jane and Laih [23], and is adapted for use in this paper. Pivoting on arcs ax1,ax2,…,axq one by one,Cj is divided into C1j, C2j,…, Cqj and C0j  as follows:
(1) Pivot on arcax1:(3)C1j=c1,c2,…,cn∣lx1Cj≤cx1<fx1d,ci∈KiCjforai∈A∖ax1;
(2) Pivot on arcax2:(4)C2j=c1,c2,…,cn∣fx1d≤cx1≤ux1Cj,lx2Cj≤cx2<fx2d,ci∈KiCjforai∈A∖ax1,ax2;
…
( q ) Pivot on arc axq:(5)Cqj=c1,c2,…,cn∣fid≤ci≤uiCjforai∈ax1,ax2,…,axq-1,lxqCj≤cxq<fxqd,ci∈KiCjforai∈A∖AdCj;
(q+1) (6)C0j=c1,c2,…,cn∣fid≤ci≤uiCjforai∈AdCj,ci∈KiCjforai∈A∖AdCj.According to Jane and Laih [23], subsets C0j, C1j, C2j,…, and Cqj satisfy two properties: (1)Cj = C0j∪C1j∪C2j∪…∪Cqj; (2) C0j, C1j, C2j,⋯, and Cqj are disjoint. Meanwhile, it is obvious that all of the state vectors in Ckj (0 ≤k ≤q) are still qualified state vectors.The remaining work is to search ford-minimal paths in these subsets. First, we consider C0j, and note that thed-flow (f1d,f2d,…,fnd) derived fromCj is the smallest state vector in C0j, then all of the other state vectors in C0j are nod-minimal paths by definition. In such a case, there is no need to enumerate the state vectors in C0j, i.e., C0j is discarded.Now we considerCkj for 2 ≤k ≤q. IfM (uCkj) <d, then there exists nod-minimal path in Ckj, and Ckj is discarded either. But, ifM(uCkj) =d, the existence ofd-minimal paths in Ckj is uncertain. In this case, because all of the state vectors in Ckj (0 ≤k ≤q) are still qualified state vectors, by Theorem 5, the enumeration method can be used to search ford-minimal paths in Ckj.Finally, we considerC1j. IfM (uC1j) <d, then there exists nod-minimal path in C1j, and C1j  is discarded. Now we discuss the caseM (uC1j) =d. Observe that C1j = c1,c2,…,cn∣lx1Cj≤cx1<fx1d,ci∈KiCjforai∈A∖ax1 which means lC1j=lCj, then C1j can be coped with in the same way asCj. That is, ad-flow (f1d,f2d,…,fnd) can be obtained from C1j whenM(C1j) =d by Theorem 6, and then C1j is similarly decomposed into disjoint subsets that are discussed in the same way as the subsets derived fromCj. This decomposition process will stop when there exists no subset C∗ meeting lC∗=lCj andM(uC∗) =d. At this moment, all of thed-minimal paths in setCj have been found.


## 3.4. The Developed Algorithm

According to the above discussions, we now present an algorithm for findingd-minimal paths in a multistate network G(N,A,Ω). To make the proposed algorithm more understandable, we use two parts, Algorithm A and Algorithm B, to describe it hereunder.Algorithm A.
Findingd-minimal paths in a multistate network G(N,A,Ω).
Input. A multistate network G(N,A,Ω) with demand leveld.
Output. Alld-minimal paths.
A. Step 1. Use the enumeration method to solve all of the combinations satisfying conditions (1) and (2), and then determine the search space C1∪C2∪…∪CH.
A. Step 2. For eachCj(1 ≤j ≤H), letC=Ci and callAlgorithm B to search ford-minimal paths inC.Algorithm B.
Findingd-minimal paths in setC.
B. Step 1. ComputeM(uC). IfM(uC) <d, there is nod-minimal path inC, and stop.
B. Step 2. Find ad-flow (f1d,f2d,…,fnd) inC, if it contains no directed cycle, it is ad-minimal path.
B. Step 3. ComputeAd(C) = ai∣ai∈A∖s,•∪•,t&fid>liCj. IfAd(C) =Φ, then stop; otherwise, supposeAd(C) = {ax1,ax2,…,axq}.
B. Step 4. Divide C intoq+1 nonempty disjoint subsets C0, C1, C2,…, Cq.
B. Step 5. Ifq >1, computeM(uCk) (2 ≤k≤q). IfM(uCk) <d, there is nod-minimal path in Ck; otherwise,for each c∈Ck (2 ≤k ≤q), if c satisfies the flow conservation law and there is no directed cycle in it, it is ad-minimal path.
B. Step 6. LetC = C1, and go toB.Step 1.To help follow the procedure of the proposed algorithm, we briefly explain the role of every step. In Algorithm A, A. Sep 1 is a proprocessing step for determining a smaller search space ofd-minimal paths, which includes H sets, and A. Step 2 is to search ford-minimal paths of each setCj by calling Algorithm B. Note that Algorithm B is a recursive algorithm for solvingd-minimal paths. B. Step 1 checks whether there may existd-minimal paths in C by computing the maximum flow under the largest state vector. B. Step 2 is to find ad-flow and to check whether it is ad-minimal path. Once ad-flow is obtained, B. Step 3 and B. Step 4 are to divide set C intoq+1 disjoint subsets. B. Step 5 searches ford-minimal paths in subsets C2,…, Cq. Subset C1 is regarded as a new set to be solved from the beginning step, i.e., B. Step 1 (a new iteration), and thus B. Step 6 is to put subset C1 into the next iteration.It is noteworthy that the major characteristics of the proposed algorithm are twofold. First, a smaller search space ofd-minimal paths is determined in A. Step 1. Second, the search space is recursively divided into subspaces such that the traditional max-flow algorithm (find ad-flow in B. Step 2) and the enumeration method (check whether c satisfies the flow conservation law in B. Step 5) are integrated to search ford-minimal paths in subsets. Notably, there is no need to enumerate subset C0, and whenM(uCk) <d (2 ≤k ≤q) holds in B. Step 5, there is also no need to enumerate subset Ck (nod-minimal paths exist in Ck either), which no doubt contributes to the efficiency improvement in searching ford-minimal paths.Now, we discuss the time complexity of the proposed algorithm. Complexity analysis of Algorithm A: it takesO(n(∏ai∈(s,•)(1+min{ui,d})+∏aj∈(•,t)(1+min{uj,d}))) time to solve all of the combinations satisfying conditions (1) and (2). After obtaining the combinations, it then needsO(Hn) time to determine the search space. As a result, A. Step 1 totally requires O(n(∏ai∈(s,•)(1+min{ui,d})+∏aj∈(•,t)(1+min{uj,d}))) time. The time complexity of A. Step 2 is obviously determined by the time complexity of Algorithm B. Complexity analysis of Algorithm B: B. Step 1 takesO(mn2) time to computeM(uC) [37]. OnceM(uC) =d is determined, ad-flow (f1d,f2d,…,fnd) can be obtained inO(n) time, and checking a directed cycle needsO(m) time. Thus, B. Step 2 requiresO(m+n) time to check whetherd-flow (f1d,f2d,…,fnd) is ad-minimal path or not. B. Step 3 requiresO(n) time to computeAd(C). B. Step 4 takesO(n) time to divide set C. B. Step 6 takesO(n) time to implement assignment operation. Therefore, the algorithm totally takesO(mn2) time without consideration of the time complexity of B. Step 5. Since solving alld-minimal paths is an NP-hard problem, the time complexity of the proposed algorithm mainly depends on B. Step 5 that employs the enumeration method to search ford-minimal paths. The number of enumerated state vectors in B. Step 5 is upper bounded by C1∪C2∪…∪CH, i.e., H∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d}), and it takesO(m) time to check whether a qualified state vector satisfies the flow conservation law, andO(m) time to check a directed cycle. Thus, B. Step 5 takes O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})) time in the worst case. Thus, the time complexity of Algorithm B is O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})) in the worst case. As a result, the time complexity of the proposed algorithm is O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})).We compare the proposed algorithm with the existing algorithms theoretically in terms of time complexity. Note that the algorithms in [13, 27, 29] are all based on the model proposed by Lin et al. [25], so they have the same time complexity as the algorithm by Lin et al. [25]. The time complexity of the algorithm by Lin et al. [25] is Ompmin⁡p+d-1d,∏i=1p1+min⁡CPi,d where p is the number of minimal paths andO(p) =O(2m), and the time complexity of both the algorithm by Yeh [26] and the modified algorithm by Xu and Niu [31] is O((m+n)∏ai∈A(1+minui,d)). As H is the total number of possible combinations satisfying conditions (1) and (2), it is trivial to have H<∏ai∈(s,•)∪(•,t)(1+min{ui,d}), and thus O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d}))≤O(m∏ai∈A(1+min{ui,d})) ≤ O((m+n)∏ai∈A(1+min{ui,d})). Furthermore, notice that O((m+n)∏ai∈A1+minui,d)≪Ompmin⁡p+d-1d,∏i=1p1+min⁡CPi,d [26]. Therefore, we can obtain O(mH∏ai∈(A∖((s,•)∪(•,t)))(1+min{ui,d})) ≤ O((m+n)∏ai∈A1+min⁡ui,d)≪Ompmin⁡p+d-1d,∏i=1p1+min⁡CPi,d. That is, the proposed algorithm compares favorably with the algorithms of Lin et al. [25], Yeh [26], and Xu and Niu [31] in terms of time complexity.


## 4. Computational Examples

### 4.1. Illustrative Example

The multistate network in Figure1 is adopted to elucidate the proposed algorithm. Given the demand leveld = 3, the following steps illustrate how to search for all of 3-minimal paths using the proposed algorithm (For simplicity, a set of state vectors C is denoted by its smallest state vectorlC and largest state vectoruC as [lC,uC] ).Algorithm A.
A. Step 1. Use the enumeration method to solve all of the combinations satisfying conditions (1) and (2) as follows:c1 + c5 =3, where 0 ≤ c1 ≤ 3 and 0 ≤ c5 ≤ 1c2 + c6 =3, where 0 ≤ c2 ≤ 2 and 0 ≤ c6 ≤ 2
And the obtained combinations are (2, 1, 1, 2), (2, 1, 2, 1), (3, 0, 1, 2), and (3, 0, 2, 1), Thus, the search spaces areC1 = [(2, 1, 0, 0, 1, 2), (2, 1, 1, 1, 1, 2)], C2 = [(2, 2, 0, 0, 1, 1), (2, 2, 1, 1, 1, 1)], C3 = [(3, 1, 0, 0, 0, 2), (3, 1, 1, 1, 0, 2)] and C4 = [(3, 2, 0, 0, 0, 1), (3, 2, 1, 1, 0, 1)].
A. Step 2. LetC= C1 = [(2, 1, 0, 0, 1, 2), (2, 1, 1, 1, 1, 2)] and search for 3-minimal paths by calling Algorithm B as follows:
B. Step 1.M(uC) = 3.
B. Step 2. (2, 1, 1, 0, 1, 2) is a 3-flow inC, and it contains no directed cycle, then (2, 1, 1, 0, 1, 2) is a 3-minimal path.
B. Step 3. A3(C) = a3 ≠Φ,q = 1.
B. Step 4.C is divided into two subsets C0 = [(2, 1, 1, 0, 1, 2), (2, 1, 1, 1, 1, 2)] and C1 = [(2, 1, 0, 0, 1, 2), (2, 1, 0, 1, 1, 2)].
B. Step 5.q = 1.
B. Step 6. LetC = C1 =[(2, 1, 0, 0, 1, 2), (2, 1, 0, 1, 1, 2)], and go to B. Step 1. // next iteration //
B. Step 1.M(uC) = 2 < 3, then there is no 3-minimal path inC, and stop.
A. Step 2. LetC= C2 = [(2, 2, 0, 0, 1, 1), (2, 2, 1, 1, 1, 1)] and search for 3-minimal paths by calling Algorithm B as follows:
B. Step 1.M(uC) = 3.
…Finally, there are totally obtained three 3-minimal paths, as shown in Table2. Let V1=c∣c≥2,1,1,0,1,2, V2=c∣c≥2,2,0,0,1,1, V3=c∣c≥3,2,1,0,0,1, then R3 can be evaluated via the Inclusion-Exclusion method as follows: R3 = Prc∣Mc≥d = Pr(V1∪V2∪…∪V3) = PrV1 + PrV2 + PrV3 – PrV1∩V2 – PrV1∩V3 – PrV2∩V3 + PrV1∩V2∩V3= Prx∣x≥2,1,1,0,1,2 + Prx∣x≥2,2,0,0,1,1 + Prx∣x≥3,2,1,0,0,1 – Prx∣x≥2,2,1,0,1,2 – Prx∣x≥3,2,1,0,1,1 – Prx∣x≥3,2,1,0,1,2 + Prx∣x≥3,2,1,0,1,2= 0.685104.Table 2
The obtained results using the proposed algorithm.
Search space 3-minimal path C 1 = [ ( 2,1 , 0,0 , 1,2 ) ] , ( 2,1 , 1,1 , 1,2 ) ] (2, 1, 1, 0, 1, 2) C 2 = [ ( 2,2 , 0,0 , 1,1 ) ] , ( 2,2 , 1,1 , 1,1 ) ] (2, 2, 0, 0, 1, 1) C 3 = [ ( 3,1 , 0,0 , 0,2 ) ] , ( 3,1 , 1,1 , 0,2 ) ] - C 4 = [ ( 3,2 , 0,0 , 0,1 ) ] , ( 3,2 , 1,1 , 0,1 ) ] (3, 2, 1, 0, 0, 1)


### 4.2. Numerical Example for Efficiency Investigation

In this section, we focus on the computational efficiency of the proposed algorithm in finding alld-minimal paths. As mentioned before, the method in [31] has been proved to be more efficient than the algorithms of Lin et al. [25], and Yeh [26] in terms of findingd-minimal paths, so we compare the proposed algorithm with it through numerical computations. Both algorithms are coded in a MATLAB program, and run on the same personal computer with Intel(R) Core (TM) i5-3210M 2.50 GHz CPU.A medium-sized network shown in Figure2 is used as benchmark network to perform numerical experiments. For comparison, we consider two scenarios. Scenario 1: the largest states of all arcs are equal to 4, i.e., ui = 4 (1 ≤i ≤ 13), and Scenario 2: the largest states of all arcs are equal to 5, i.e., ui = 5 (1 ≤i ≤ 13). For each scenario, the demand level d ranges from 1 to the largest valueM(u), i.e., all of thed-minimal paths corresponding to multiple demand levels are solved. We focus on the computational time required to search for alld-minimal paths of each demand level. Meanwhile, to make intuitive comparisons, we define ratio λ as the computational time of the method in [31] divided by the computational time of the proposed algorithm. Then, the ratio λ represents the relative efficiency of two algorithms.Figure 2
A benchmark network for numerical experiments.From both Figures3 and 4, it can be seen that the ratio λ is always above one for every demand level d under both scenarios, implying the proposed algorithm is more efficient than the method in [31]. Meanwhile, note that as the demand level d increases, the ratio λ increases, indicating the efficiency advantage of the proposed algorithms becomes much stronger. For example, the proposed algorithm is more than 10 times faster than the algorithm in [31] when solvingd-minimal paths with demand level d above 5 under both Scenario 1 and Scenario 2, and the proposed algorithm is more than 20 times faster than the algorithm in [31] when solvingd-minimal paths with demand level d above 6 under Scenario 1 and with demand level d above 7 under Scenario 2, respectively.Figure 3
Ratioλ when ui = 4.Figure 4
Ratioλ when ui = 5.


## 4.1. Illustrative Example

The multistate network in Figure1 is adopted to elucidate the proposed algorithm. Given the demand leveld = 3, the following steps illustrate how to search for all of 3-minimal paths using the proposed algorithm (For simplicity, a set of state vectors C is denoted by its smallest state vectorlC and largest state vectoruC as [lC,uC] ).Algorithm A.
A. Step 1. Use the enumeration method to solve all of the combinations satisfying conditions (1) and (2) as follows:c1 + c5 =3, where 0 ≤ c1 ≤ 3 and 0 ≤ c5 ≤ 1c2 + c6 =3, where 0 ≤ c2 ≤ 2 and 0 ≤ c6 ≤ 2
And the obtained combinations are (2, 1, 1, 2), (2, 1, 2, 1), (3, 0, 1, 2), and (3, 0, 2, 1), Thus, the search spaces areC1 = [(2, 1, 0, 0, 1, 2), (2, 1, 1, 1, 1, 2)], C2 = [(2, 2, 0, 0, 1, 1), (2, 2, 1, 1, 1, 1)], C3 = [(3, 1, 0, 0, 0, 2), (3, 1, 1, 1, 0, 2)] and C4 = [(3, 2, 0, 0, 0, 1), (3, 2, 1, 1, 0, 1)].
A. Step 2. LetC= C1 = [(2, 1, 0, 0, 1, 2), (2, 1, 1, 1, 1, 2)] and search for 3-minimal paths by calling Algorithm B as follows:
B. Step 1.M(uC) = 3.
B. Step 2. (2, 1, 1, 0, 1, 2) is a 3-flow inC, and it contains no directed cycle, then (2, 1, 1, 0, 1, 2) is a 3-minimal path.
B. Step 3. A3(C) = a3 ≠Φ,q = 1.
B. Step 4.C is divided into two subsets C0 = [(2, 1, 1, 0, 1, 2), (2, 1, 1, 1, 1, 2)] and C1 = [(2, 1, 0, 0, 1, 2), (2, 1, 0, 1, 1, 2)].
B. Step 5.q = 1.
B. Step 6. LetC = C1 =[(2, 1, 0, 0, 1, 2), (2, 1, 0, 1, 1, 2)], and go to B. Step 1. // next iteration //
B. Step 1.M(uC) = 2 < 3, then there is no 3-minimal path inC, and stop.
A. Step 2. LetC= C2 = [(2, 2, 0, 0, 1, 1), (2, 2, 1, 1, 1, 1)] and search for 3-minimal paths by calling Algorithm B as follows:
B. Step 1.M(uC) = 3.
…Finally, there are totally obtained three 3-minimal paths, as shown in Table2. Let V1=c∣c≥2,1,1,0,1,2, V2=c∣c≥2,2,0,0,1,1, V3=c∣c≥3,2,1,0,0,1, then R3 can be evaluated via the Inclusion-Exclusion method as follows: R3 = Prc∣Mc≥d = Pr(V1∪V2∪…∪V3) = PrV1 + PrV2 + PrV3 – PrV1∩V2 – PrV1∩V3 – PrV2∩V3 + PrV1∩V2∩V3= Prx∣x≥2,1,1,0,1,2 + Prx∣x≥2,2,0,0,1,1 + Prx∣x≥3,2,1,0,0,1 – Prx∣x≥2,2,1,0,1,2 – Prx∣x≥3,2,1,0,1,1 – Prx∣x≥3,2,1,0,1,2 + Prx∣x≥3,2,1,0,1,2= 0.685104.Table 2
The obtained results using the proposed algorithm.
Search space 3-minimal path C 1 = [ ( 2,1 , 0,0 , 1,2 ) ] , ( 2,1 , 1,1 , 1,2 ) ] (2, 1, 1, 0, 1, 2) C 2 = [ ( 2,2 , 0,0 , 1,1 ) ] , ( 2,2 , 1,1 , 1,1 ) ] (2, 2, 0, 0, 1, 1) C 3 = [ ( 3,1 , 0,0 , 0,2 ) ] , ( 3,1 , 1,1 , 0,2 ) ] - C 4 = [ ( 3,2 , 0,0 , 0,1 ) ] , ( 3,2 , 1,1 , 0,1 ) ] (3, 2, 1, 0, 0, 1)


## 4.2. Numerical Example for Efficiency Investigation

In this section, we focus on the computational efficiency of the proposed algorithm in finding alld-minimal paths. As mentioned before, the method in [31] has been proved to be more efficient than the algorithms of Lin et al. [25], and Yeh [26] in terms of findingd-minimal paths, so we compare the proposed algorithm with it through numerical computations. Both algorithms are coded in a MATLAB program, and run on the same personal computer with Intel(R) Core (TM) i5-3210M 2.50 GHz CPU.A medium-sized network shown in Figure2 is used as benchmark network to perform numerical experiments. For comparison, we consider two scenarios. Scenario 1: the largest states of all arcs are equal to 4, i.e., ui = 4 (1 ≤i ≤ 13), and Scenario 2: the largest states of all arcs are equal to 5, i.e., ui = 5 (1 ≤i ≤ 13). For each scenario, the demand level d ranges from 1 to the largest valueM(u), i.e., all of thed-minimal paths corresponding to multiple demand levels are solved. We focus on the computational time required to search for alld-minimal paths of each demand level. Meanwhile, to make intuitive comparisons, we define ratio λ as the computational time of the method in [31] divided by the computational time of the proposed algorithm. Then, the ratio λ represents the relative efficiency of two algorithms.Figure 2
A benchmark network for numerical experiments.From both Figures3 and 4, it can be seen that the ratio λ is always above one for every demand level d under both scenarios, implying the proposed algorithm is more efficient than the method in [31]. Meanwhile, note that as the demand level d increases, the ratio λ increases, indicating the efficiency advantage of the proposed algorithms becomes much stronger. For example, the proposed algorithm is more than 10 times faster than the algorithm in [31] when solvingd-minimal paths with demand level d above 5 under both Scenario 1 and Scenario 2, and the proposed algorithm is more than 20 times faster than the algorithm in [31] when solvingd-minimal paths with demand level d above 6 under Scenario 1 and with demand level d above 7 under Scenario 2, respectively.Figure 3
Ratioλ when ui = 4.Figure 4
Ratioλ when ui = 5.


## 5. Case Study of Power Transmission Network

In modern society, electric power is the necessity to our daily life. Thus, a reliable power transmission network is critical to the stable operation of the whole society. As exemplified in Section1, power transmission networks can be regarded as typical multistate networks. Therefore, we take a power transmission network as case study to demonstrate the utility of the proposed algorithm and the related implications of network reliability.A power transmission network with sixteen transmission lines is shown in Figure5. The capacity and capacity distribution of each transmission line of the power transmission network are presented in Table 3. Suppose that the supervisor would like to assess the capability of the power transmission network to successfully transmit 6 units (MW) of electric power from the power plant (nodes) to the targeted high voltage substation (nodet). Then, the network reliability R6 can be computed in terms of 6-minimal paths. Using the proposed algorithm, a total of 143 6-minimal paths are obtained. As a result, it can be calculated that R6 = 0.928546 by the Inclusion-Exclusion method. That is, the probability of the power transmission network being able to successfully transmit 6 units (MW) of electric power from the power plant to the targeted high voltage substation is 0.928546. This value 0.928546 provides the supervisor with intuitive information regarding the capability of the network to ensure the transmission of 6 units (MW) of electric power from the power plant to the targeted high voltage substation. If 0.928546 is above the supervisor's expectation, it means the operational state of the power transmission network is desirable. However, if 0.928546 is below the supervisor's expectation, it means the operational state of the power transmission network is undesirable, and then some improvement measures are needed to enhance the power transmission network.Table 3
Data of each arc (transmission line) of the power transmission network.
Arc Capacity (MW) 0 1 2 3 4 5 Capacity probability distribution a 1 0.005 0.008 0.012 0.016 0.022 0.937 a 2 0.006 0.023 0.971 - - - a 3 0.004 0.018 0.026 0.952 - - a 4 0.005 0.011 0.023 0.039 0.922 - a 5 0.006 0.029 0.965 - - - a 6 0.004 0.018 0.025 0.953 - - a 7 0.005 0.016 0.026 0.953 - - a 8 0.007 0.019 0.974 - - - a 9 0.006 0.015 0.979 - - - a 10 0.004 0.013 0.983 - - - a 11 0.008 0.013 0.026 0.953 - - a 12 0.007 0.026 0.967 - - - a 13 0.006 0.019 0.034 0.941 - - a 14 0.007 0.012 0.029 0.952 - - a 15 0.009 0.016 0.029 0.035 0.911 - a 16 0.003 0.008 0.012 0.016 0.022 0.939Figure 5
A power transmission network.


## 6. Conclusion

In this paper, an efficient algorithm is developed to search ford-minimal paths in reliability evaluation of multistate networks. Unlike the existing algorithms that enumerated-minimal paths in a larger search space, the proposed algorithm first determines a relatively smaller search space ofd-minimal paths by employing a concept of qualified state vector. A sufficient and necessary condition for a qualified state vector to bed-minimal path is derived. And, the search space is recursively divided into subspaces, so that the max-flow algorithm and the enumeration algorithm are integrated to search ford-minimal paths with the purpose of increasing the efficiency of enumeration. Furthermore, it is theoretically proven that the proposed algorithm compares favorably with the existing algorithms in terms of time complexity. Finally, numerical examples have shown the effectiveness and efficiency of the proposed algorithm.



---

*Source: 4561845-2019-03-21.xml*