# Assessing the Reliability of a Multistate Logistics Network under the Transportation Cost Constraint

Authors: Qi Zeng; Xiu-Zhen Xu
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

Reliability and transportation cost are two important indicators to measure the performance of logistics network. As a combination of reliability and transportation cost, the performance indexR
(
d
,
c
) of logistics network is defined as the probability that at least d units of flow demand can be successfully transmitted from the source to the destination with the total transportation cost less than or equal to c. In this paper, an algorithm is developed to calculate R
(
d
,
c
) in terms of (
d
,
c
)-minimal paths ((
d
,
c
)-MPs for short). The proposed algorithm employs a decomposition technique to divide the search space of (
d
,
c
)-MPs such that the search space of (
d
,
c
)-MPs can be dramatically reduced, and thereby (
d
,
c
)-MPs can be efficiently obtained. An example is provided to illustrate the proposed algorithm. Finally, computational experiments conducted on one benchmark network indicate that the proposed method has an advantage over the existing methods.


---

## Body

## 1. Introduction

With the swift development of E-commerce, express logistics in China is presenting a vigorous development trend. Meanwhile, most of enterprises begin to pay more attention to logistics performance for improving business efficiency. Logistics networks which provide the infrastructure for the storage and distribution of products undertake the mission of promoting the efficient and safe movement of goods over time and space and thus play an increasingly important part in sustaining the national economic and social development. It is widely accepted that an efficient, reliable, and cost-effective logistics network not only affects a firm’s short-term benefits but also influences a firm’s long-term development.The performance assessment of logistics networks is a popular issue in the field of logistics and supply chain management. In a real-world environment, the performance of logistics networks is always affected by various unexpected events, such that it is subject to degradation. Hence, it is of importance from the perspective of logistics management to assess the capability of logistics networks to ensure the delivery of required quantity of goods to the right demand point. In addition, the transportation cost is also a major concern for logistics providers. Therefore, combining capacity reliability and transportation cost for performance measure of logistics networks, in a sense, is of significance to possible improvement of logistics performance.Theoretically, logistics network can be represented as sets of both nodes and arcs, where each node stands for a supplier, a transfer center, or a market, and each arc connecting a pair of nodes stands for transportation medium (traffic tools, traffic routes, or both) [1]. In fact, the transportation medium, which is multistate due to the nature of the traffic tools (truck, railway, cargo ship, etc.), may be in a failure state, partial failure state, or maintenance state [1, 2]. That is, the number of available traffic tools is not fixed in some sense, and thus each arc has several possible capacities. Therefore, logistics network can be modeled as a multistate flow network in which arcs are associated with multiple integer capacities, operational reliability, and unit transportation cost. And, the goods transported through such logistics network are looked upon as a flow. The reliability index R
(
d
,
c
) of logistics network is defined as the probability that at least d units of flow demand can be successfully transmitted from the source to the destination with the total transportation cost less than or equal toc [3–9]. One of the general algorithms for computing R
(
d
,
c
) is using (
d
,
c
)-minimal paths ((
d
,
c
)-MPs) [4–9]. A (
d
,
c
)-MP,x, is a minimal state vector meeting the demand d and the cost constraintc, which means that, for any y
<
x, y does not meet the demand d or the cost constraint c [6]. If all (
d
,
c
)-MPs are known, the well-known Inclusion-Exclusion rule is available to calculate R
(
d
,
c
) [7–9]. So, the most important work is how to efficiently determine all (
d
,
c
)-MPs.A minimal path (MP) is a subset of arcs, such that if any arc is removed from this set, the remaining set is no longer a path [10]. Based on MPs, Lin [5] proposed a simple algorithm to search for all (
d
,
c
)-MPs. Lin’s algorithm first uses the enumeration algorithm to search for (
d
,
c
)-MP candidates. Then, all (
d
,
c
)-MP candidates are verified whether they are (
d
,
c
)-MPs via the comparison method. It is time consuming to check (
d
,
c
)-MP candidates by a comparison method due to the exponentially growing number of (
d
,
c
)-MP candidates [7]. Lin [6] extended the work to the case with unreliable nodes. The method of Lin uses MPs to assign the flow to each component (arc or node). All (
d
,
c
)-MPs can be obtained by the comparison algorithm. Instead of the comparison method, Yeh [7] proposed a cycle-checking method to verify (
d
,
c
)-MP candidates and demonstrated that his method is more efficient. Without requiring MPs information, Yeh [8] proposed an algorithm to search for (
d
,
c
)-MPs by solving a simple model and proved that his algorithm is more efficient than the MPs based algorithms [5–7]. And yet, the algorithm by Yeh [8] is an exhaustive enumeration method in itself, so its searching efficiency is low. By adding some constraints to the minimal capacities of arcs, Niu and Xu [9] proposed an algorithm to improve the searching efficiency of solving (
d
,
c
)-MPs.The above discussions indicate that the methods in [5–7] for solving (
d
,
c
)-MPs require all MPs information. However, it is a cumbersome task to find all MPs, because the MP problem is proven to be NP-hard [11]. Furthermore, the time complexity of the MPs based algorithms [5–7] is directly proportional to the number of MPs which grows exponentially with the scale of the network; thus, the computational efficiency of these algorithms in [5–7] is far from satisfactory. The methods in [8, 9] require no MPs information and thus are an improvement to the ones in [5–7]. But, one remarkable limitation of Yeh’s method [8] is that a huge number of state vectors need to be enumerated, which results in the lower searching efficiency. While Niu and Xu [9] have made some efforts to advance the searching efficiency, the method by Niu and Xu is even inferior to the one by Yeh when the demand level is low, and thus its searching efficiency is also not satisfactory. Hence, the purpose of this paper is to propose a new efficient algorithm for solving all (
d
,
c
)-MPs. The major contribution of this paper is that we develop a new approach to shorten the search space of (
d
,
c
)-MP. In particular, to decrease the number of enumerated state vectors, an effective decomposition technique is employed to divide the search space of (
d
,
c
)-MPs, such that the search subspace of (
d
,
c
)-MPs can be dramatically reduced; thereby (
d
,
c
)-MPs can be efficiently obtained. A real example is provided to illustrate the proposed algorithm. Moreover, the experimental results clearly indicate that the proposed algorithm is superior to the above-mentioned methods [5–9] in solving the (
d
,
c
)-MP problem.The rest of this paper is organized as follows. Section2 introduces the network model and basic results. In Section 3, the proposed algorithm is described in detail, and its time complexity is also analyzed. In Section 4, an illustrative example is provided to demonstrate the proposed algorithm. Computational experiments are conducted in Section 5 to compare the proposed algorithm with the existing methods. The final section presents the concluding remarks.


## 2. Preliminaries

### 2.1. Multistate Network Model

A multistate network is represented byG
(
V
,
E
,
u
,
C
) with the source node s and the destination nodet, where V
=
{
s
,
1,2
,
…
,
n
,
t
} is the set of nodes with n denoting the number of nodes except s and t, E
=
{
e
1
,
e
2
,
…
,
e
m
} is the set of arcs with m denoting the number of arcs, u
=
(
u
1
,
u
2
,
…
,
u
m
) is the largest capacity vector, and C
=
(
C
1
,
C
2
,
…
,
C
m
) is the cost vector, where C
i is the unit transportation cost of e
i. The state of an arc e
i is denoted by x
i which takes integer values from 0 to u
i, where u
i denotes the largest capacity of arc e
i. A state vector x
=
(
x
1
,
x
2
,
…
,
x
m
) indicates the current state of each arc. Let X denote a set of state vectors, and the smallest and largest state vectors in set X are denoted by l
X
=
(
l
1
X
,
l
2
X
,
…
,
l
m
X
) and u
X
=
(
u
1
X
,
u
2
X
,
…
,
u
m
X
), respectively. Let M
(
x
) denote the max-flow of the network under x and f
i denote the flows through e
i for 1
≤
i
≤
m; then the total transportation cost of the network under x is C
(
x
)
=
∑
i
=
1
m
f
i
C
i. Specifically, if x is a feasible state vector (i.e., it satisfies the flow conservation law), then C
(
x
)
=
∑
i
=
1
m
x
i
C
i. The network model satisfies the following assumptions [7–9]: (
1
) the state of each arc is a random variable which takes integer values from 0 to u
i according to a given distribution; (
2
) the states of different arcs are statistically independent; (
3
) all flows in the network obey the conservation law: that is, total flows into and from a node (other than the source and destination nodes) are all equal.To facilitate the understanding, Figure1 and Table 1 are used to illustrate several notations. Figure 1 shows V
=
{
s
,
1,2
,
t
}, n
=
2, E
=
{
e
1
,
e
2
,
e
3
,
e
4
,
e
5
,
e
6
}, and m
=
6. Table 1 indicates u
=
(
3,2
,
1,1
,
2,2
) and C
=
(
3,1
,
1,1
,
1,3
). Given a state vector x
=
(
2,1
,
1,0
,
1,2
), which indicates that the current states of e
1, e
2, e
3, e
4, e
5, and e
6 are 2, 1, 1, 0, 1, and 2, respectively, the max-flow of the network under x is M
(
x
)
=
3. Obviously, x
=
(
2,1
,
1,0
,
1,2
) is a feasible state vector; then the total transportation cost of the network under x is C
(
x
)
= 2 × 3 + 1 × 1 + 1 × 1 + 0 × 1 + 1 × 1 + 2 × 3 =
15. Let X
=
{
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
)
∣
x
1
=
1, 0
≤
x
2
≤
1, 0
≤
x
3
≤
1, 0
≤
x
4
≤
1, 0
≤
c
5
≤
1, 1
≤
x
6
≤
2
}; then the smallest state vector in X is l
X
=
(
1,0
,
0,0
,
0,1
), and the largest state vector in X is u
X
=
(
1,1
,
1,1
,
1,2
). The max-flow of the network under l
X and u
X is M
(
l
X
) = 0 and M
(
u
X
) = 2.Table 1
The data of arcs for Figure1.
Arc
⁢State/capacities
⁢State/capacity probabilities
Distribution cost
e
1
0
1
2
3
0.05
0.10
0.25
0.60
3
e
2
0
1
2
—
0.10
0.30
0.60
—
1
e
3
0
1
—
—
0.10
0.90
—
—
1
e
4
0
1
—
—
0.10
0.90
—
—
1
e
5
0
1
2
—
0.10
0.10
0.80
—
1
e
6
0
1
2
—
0.05
0.25
0.70
—
3Figure 1


### 2.2. Evaluation ofR
(
d
,
c
) in terms of (
d
,
c
)-MPs

The Inclusion-Exclusion method is introduced to show how to calculateR
(
d
,
c
) in terms of (
d
,
c
)-MPs. Assume y
1
,
y
2
,
…
,
y
σ are all (
d
,
c
)-MPs, and let B
1
=
{
x
∣
x
≥
y
1
}, B
2
=
{
x
∣
x
≥
y
2
}
,
…
,
B
σ
=
{
x
∣
x
≥
y
σ
}, where x
=
(
x
1
,
x
2
,
…
,
x
m
), y
i
=
(
y
i
1
,
y
i
2
,
…
,
y
i
m), and x
≥
y
i means that x
j ≥ y
i
j for j
=
1,2
,
…
,
m [6]; then R
(
d
,
c
) can be evaluated via the Inclusion-Exclusion method as follows: (1)
R
d
,
c
=
P
r
B
1
∪
B
2
∪
⋯
∪
B
σ
=
∑
i
=
1
σ
Pr
⁡
B
i
-
∑
j
=
2
σ
∑
i
=
1
j
-
1
Pr
⁡
B
i
∩
B
j
+
⋯
+
-
1
σ
-
1
P
r
B
1
∩
B
2
∩
⋯
∩
B
σ
,where Pr
⁡
{
B
i
}
=
Pr
⁡
{
x
∣
x
≥
y
i
} = ∏
k
=
1
m
Pr
⁡
{
x
k
≥
y
i
k
}, Pr
⁡
{
B
i
∩
B
j
} = Pr
⁡
{
x
∣
x
≥
max
⁡
{
y
i
,
y
j
}
}
=
∏
k
=
1
m
Pr
⁡
{
x
k
≥
max
⁡
{
y
i
k
,
y
j
k
}
}
,
…, Pr
⁡
(
B
1
∩
B
2
∩
⋯
∩
B
σ
) = Pr
⁡
{
x
∣
x
≥
max
⁡
{
y
1
,
y
2
,
…
,
y
σ
}
} = ∏
k
=
1
m
Pr
⁡
{
x
k
≥
max
⁡
{
y
1
k
,
y
2
k
,
…
,
y
σ
k
}
}.


### 2.3. Fundamental Results on the(
d
,
c
)-MP Problem

A state vectorx = (x
1, x
2
,
…
,
x
m) is a (
d
,
c
)-MP if and only if (
1
)
M
(
x
)
=
d; (
2
)  M
(
x
-
0
(
e
i
)
)
<
d for each x
i > 0, where 0
(
e
i
)
=
(
0
,
…
,
0,1
,
0
,
…
,
0
): that is, state is 1 for e
i and 0 for other arcs; and (
3
)
C
(
x
)
=
∑
i
=
1
m
x
i
C
i
≤
c [8, 9]. The following lemma which is originated from the work of Niu and Xu [9] is a basis for searching for (
d
,
c
)-MPs.Lemma 1.
A state vectorx is a (
d
,
c
)-MP if and only if x satisfies the following conditions:(2)
∑
e
i
∈
s
,
·
x
i
=
∑
e
j
∈
·
,
t
x
j
=
d
,
(3)
∑
e
i
∈
·
,
v
x
i
=
∑
e
j
∈
v
,
·
x
j
f
o
r
e
v
e
r
y
n
o
d
e
v
∈
1,2
,
…
,
n
,
(4)
0
≤
x
i
≤
min
⁡
u
i
,
d
f
o
r
1
≤
i
≤
m
,
(5)
T
h
e
r
e
i
s
n
o
d
i
r
e
c
t
c
y
c
l
e
i
n
x
,
(6)
C
x
≤
c
,where (
v
,
·
) is the set of arcs emanating from node v and (
·
,
v
) is the set of arcs pointing to node v. It should be pointed out that (2)–(4) are established on the basis of the well-known flow conservation law [9]. By lemma, it is easy to obtain the following conclusion.Corollary 2.
For a state vectorx with M
(
x
)
=
d, if x satisfies conditions (3), (4), (5), and (6), then x is a (
d
,
c
)-MP.By Lemma1, the enumeration method can be used to search for (
d
,
c
)-MPs. Given a multistate network G
(
V
,
E
,
u
,
C
), (4) shows that the total number of state vectors contained in search space of (
d
,
c
)-MPs is ∏
i
=
1
m
(
m
i
n
{
u
i
,
d
}
+
1
) which is a pretty huge number. Thus, it is inefficient to search for (
d
,
c
)-MPs by Lemma 1. Below, we will introduce how to divide the search space into disjoint subspaces from which all (
d
,
c
)-MPs can be efficiently obtained.


## 2.1. Multistate Network Model

A multistate network is represented byG
(
V
,
E
,
u
,
C
) with the source node s and the destination nodet, where V
=
{
s
,
1,2
,
…
,
n
,
t
} is the set of nodes with n denoting the number of nodes except s and t, E
=
{
e
1
,
e
2
,
…
,
e
m
} is the set of arcs with m denoting the number of arcs, u
=
(
u
1
,
u
2
,
…
,
u
m
) is the largest capacity vector, and C
=
(
C
1
,
C
2
,
…
,
C
m
) is the cost vector, where C
i is the unit transportation cost of e
i. The state of an arc e
i is denoted by x
i which takes integer values from 0 to u
i, where u
i denotes the largest capacity of arc e
i. A state vector x
=
(
x
1
,
x
2
,
…
,
x
m
) indicates the current state of each arc. Let X denote a set of state vectors, and the smallest and largest state vectors in set X are denoted by l
X
=
(
l
1
X
,
l
2
X
,
…
,
l
m
X
) and u
X
=
(
u
1
X
,
u
2
X
,
…
,
u
m
X
), respectively. Let M
(
x
) denote the max-flow of the network under x and f
i denote the flows through e
i for 1
≤
i
≤
m; then the total transportation cost of the network under x is C
(
x
)
=
∑
i
=
1
m
f
i
C
i. Specifically, if x is a feasible state vector (i.e., it satisfies the flow conservation law), then C
(
x
)
=
∑
i
=
1
m
x
i
C
i. The network model satisfies the following assumptions [7–9]: (
1
) the state of each arc is a random variable which takes integer values from 0 to u
i according to a given distribution; (
2
) the states of different arcs are statistically independent; (
3
) all flows in the network obey the conservation law: that is, total flows into and from a node (other than the source and destination nodes) are all equal.To facilitate the understanding, Figure1 and Table 1 are used to illustrate several notations. Figure 1 shows V
=
{
s
,
1,2
,
t
}, n
=
2, E
=
{
e
1
,
e
2
,
e
3
,
e
4
,
e
5
,
e
6
}, and m
=
6. Table 1 indicates u
=
(
3,2
,
1,1
,
2,2
) and C
=
(
3,1
,
1,1
,
1,3
). Given a state vector x
=
(
2,1
,
1,0
,
1,2
), which indicates that the current states of e
1, e
2, e
3, e
4, e
5, and e
6 are 2, 1, 1, 0, 1, and 2, respectively, the max-flow of the network under x is M
(
x
)
=
3. Obviously, x
=
(
2,1
,
1,0
,
1,2
) is a feasible state vector; then the total transportation cost of the network under x is C
(
x
)
= 2 × 3 + 1 × 1 + 1 × 1 + 0 × 1 + 1 × 1 + 2 × 3 =
15. Let X
=
{
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
)
∣
x
1
=
1, 0
≤
x
2
≤
1, 0
≤
x
3
≤
1, 0
≤
x
4
≤
1, 0
≤
c
5
≤
1, 1
≤
x
6
≤
2
}; then the smallest state vector in X is l
X
=
(
1,0
,
0,0
,
0,1
), and the largest state vector in X is u
X
=
(
1,1
,
1,1
,
1,2
). The max-flow of the network under l
X and u
X is M
(
l
X
) = 0 and M
(
u
X
) = 2.Table 1
The data of arcs for Figure1.
Arc
⁢State/capacities
⁢State/capacity probabilities
Distribution cost
e
1
0
1
2
3
0.05
0.10
0.25
0.60
3
e
2
0
1
2
—
0.10
0.30
0.60
—
1
e
3
0
1
—
—
0.10
0.90
—
—
1
e
4
0
1
—
—
0.10
0.90
—
—
1
e
5
0
1
2
—
0.10
0.10
0.80
—
1
e
6
0
1
2
—
0.05
0.25
0.70
—
3Figure 1


## 2.2. Evaluation ofR
(
d
,
c
) in terms of (
d
,
c
)-MPs

The Inclusion-Exclusion method is introduced to show how to calculateR
(
d
,
c
) in terms of (
d
,
c
)-MPs. Assume y
1
,
y
2
,
…
,
y
σ are all (
d
,
c
)-MPs, and let B
1
=
{
x
∣
x
≥
y
1
}, B
2
=
{
x
∣
x
≥
y
2
}
,
…
,
B
σ
=
{
x
∣
x
≥
y
σ
}, where x
=
(
x
1
,
x
2
,
…
,
x
m
), y
i
=
(
y
i
1
,
y
i
2
,
…
,
y
i
m), and x
≥
y
i means that x
j ≥ y
i
j for j
=
1,2
,
…
,
m [6]; then R
(
d
,
c
) can be evaluated via the Inclusion-Exclusion method as follows: (1)
R
d
,
c
=
P
r
B
1
∪
B
2
∪
⋯
∪
B
σ
=
∑
i
=
1
σ
Pr
⁡
B
i
-
∑
j
=
2
σ
∑
i
=
1
j
-
1
Pr
⁡
B
i
∩
B
j
+
⋯
+
-
1
σ
-
1
P
r
B
1
∩
B
2
∩
⋯
∩
B
σ
,where Pr
⁡
{
B
i
}
=
Pr
⁡
{
x
∣
x
≥
y
i
} = ∏
k
=
1
m
Pr
⁡
{
x
k
≥
y
i
k
}, Pr
⁡
{
B
i
∩
B
j
} = Pr
⁡
{
x
∣
x
≥
max
⁡
{
y
i
,
y
j
}
}
=
∏
k
=
1
m
Pr
⁡
{
x
k
≥
max
⁡
{
y
i
k
,
y
j
k
}
}
,
…, Pr
⁡
(
B
1
∩
B
2
∩
⋯
∩
B
σ
) = Pr
⁡
{
x
∣
x
≥
max
⁡
{
y
1
,
y
2
,
…
,
y
σ
}
} = ∏
k
=
1
m
Pr
⁡
{
x
k
≥
max
⁡
{
y
1
k
,
y
2
k
,
…
,
y
σ
k
}
}.


## 2.3. Fundamental Results on the(
d
,
c
)-MP Problem

A state vectorx = (x
1, x
2
,
…
,
x
m) is a (
d
,
c
)-MP if and only if (
1
)
M
(
x
)
=
d; (
2
)  M
(
x
-
0
(
e
i
)
)
<
d for each x
i > 0, where 0
(
e
i
)
=
(
0
,
…
,
0,1
,
0
,
…
,
0
): that is, state is 1 for e
i and 0 for other arcs; and (
3
)
C
(
x
)
=
∑
i
=
1
m
x
i
C
i
≤
c [8, 9]. The following lemma which is originated from the work of Niu and Xu [9] is a basis for searching for (
d
,
c
)-MPs.Lemma 1.
A state vectorx is a (
d
,
c
)-MP if and only if x satisfies the following conditions:(2)
∑
e
i
∈
s
,
·
x
i
=
∑
e
j
∈
·
,
t
x
j
=
d
,
(3)
∑
e
i
∈
·
,
v
x
i
=
∑
e
j
∈
v
,
·
x
j
f
o
r
e
v
e
r
y
n
o
d
e
v
∈
1,2
,
…
,
n
,
(4)
0
≤
x
i
≤
min
⁡
u
i
,
d
f
o
r
1
≤
i
≤
m
,
(5)
T
h
e
r
e
i
s
n
o
d
i
r
e
c
t
c
y
c
l
e
i
n
x
,
(6)
C
x
≤
c
,where (
v
,
·
) is the set of arcs emanating from node v and (
·
,
v
) is the set of arcs pointing to node v. It should be pointed out that (2)–(4) are established on the basis of the well-known flow conservation law [9]. By lemma, it is easy to obtain the following conclusion.Corollary 2.
For a state vectorx with M
(
x
)
=
d, if x satisfies conditions (3), (4), (5), and (6), then x is a (
d
,
c
)-MP.By Lemma1, the enumeration method can be used to search for (
d
,
c
)-MPs. Given a multistate network G
(
V
,
E
,
u
,
C
), (4) shows that the total number of state vectors contained in search space of (
d
,
c
)-MPs is ∏
i
=
1
m
(
m
i
n
{
u
i
,
d
}
+
1
) which is a pretty huge number. Thus, it is inefficient to search for (
d
,
c
)-MPs by Lemma 1. Below, we will introduce how to divide the search space into disjoint subspaces from which all (
d
,
c
)-MPs can be efficiently obtained.


## 3. The Proposed Algorithm

Given a set of state vectorsX
=
{
x
∣
x
=
(
x
1
,
x
2
,
…
,
x
m
), x
i
∈
K
i
X for 1
≤
i
≤
m
}, where K
i
X is the set of states of e
i with respect to X, that is, K
i
X
=
{
x
i
∣
l
i
X
≤
x
i
≤
u
i
X
f
o
r
1
≤
i
≤
m
}, if we limit the search space of (
d
,
c
)-MP in set X, it is apparent that Lemma 1 can be transformed into the following conclusion.Corollary 3.
A state vectorx is a (
d
,
c
)-MP in set X if and only if x satisfies the following conditions:(7)
∑
e
i
∈
s
,
·
x
i
=
∑
e
j
∈
·
,
t
x
j
=
d
,
(8)
∑
e
i
∈
·
,
v
x
i
=
∑
e
j
∈
v
,
·
x
j
f
o
r
e
v
e
r
y
n
o
d
e
v
∈
1,2
,
…
,
n
,
(9)
l
i
X
≤
x
i
≤
min
⁡
u
i
X
,
d
f
o
r
1
≤
i
≤
m
,
(10)
T
h
e
r
e
i
s
n
o
d
i
r
e
c
t
c
y
c
l
e
i
n
x
,
(11)
C
x
≤
c
.It should be noted that the only difference between Lemma1 and Corollary 3 is the state range of e
i. Next, we will consider a special state vector in setX: the smallest state vector l
X. It is clear that there are three cases with respect to M
(
l
X
)
:  (
1
) Case 1: M
(
l
X
)
>
d; (
2
) Case 2: M
(
l
X
)
=
d; and (
3
) Case 3: M
(
l
X
)
<
d.Case 1 (M
(
l
X
)
>
d).
IfM
(
l
X
) >d, we have the following statement.Theorem 4.
For setX, if M
(
l
X
)
>
d, there is no (
d
,
c
)-MP in X.Proof.
Sincel
X is the smallest state vector in X, we have x
≥
l
X for any vector x
∈
X. If M
(
l
X
)
>
d, then M
(
x
)
≥
M
(
l
X
)
>
d for any x
∈
X. That is, M
(
x
)
>
d for any x
∈
X; then, by the definition of (
d
,
c
)-MP, there is no (
d
,
c
)-MP in X.According to Theorem4, once we have verified that M
(
l
X
)
>
d holds, set X will be discarded (no (
d
,
c
)-MP exists in X). Thus, the search space of (
d
,
c
)-MPs will be reduced, which is extremely beneficial in solving (
d
,
c
)-MPs.Case 2 (M
(
l
X
)
=
d).
In such case, we can claim that the following theorem holds.Theorem 5.
For setX, if M
(
l
X
)
=
d, there exists no more than one (
d
,
c
)-MP in set X. Moreover, if there exists one (
d
,
c
)-MP, l
X is the unique (
d
,
c
)-MP in setX.Proof.
Suppose vectorx
(
≠
l
X
) is a (
d
,
c
)-MP in setX; thenM(x) =d. Note that x
>
l
X, and M
(
x
)
=
M
(
l
X
)
=
d, which is contrary to the definition of (
d
,
c
)-MP. Therefore, only l
X has the chance to be a (
d
,
c
)-MP inX.Theorem5 provides an effective method to search for (
d
,
c
)-MPs in set X. If M
(
l
X
) =d holds, we only need to check whether l
X is a (
d
,
c
)-MP by Corollary 3. If l
X is a (
d
,
c
)-MP, it is the unique (
d
,
c
)-MP in set X. Otherwise, there is no (
d
,
c
)-MP in setX.Case 3 (M
(
l
X
)
<
d).
In such case, we need to analyze the largest state vectoru
X in set X. If M
(
u
X
)
<
d, we have the following statement.Theorem 6.
For setX, if M
(
u
X
)
<
d, there is no (
d
,
c
)-MP in setX.Proof.
Sinceu
X is the largest state vector in setX, we have x
≤
u
X for any x
∈
X. If M
(
u
X
)
<
d, it is clear to derive M
(
x
)
≤
M
(
u
X
)
<
d for any x
∈
X. That is, M
(
x
)
<
d for any x
∈
X; then, by the definition of (
d
,
c
)-MP, there is nod-MP in setX.It is noteworthy that all of the three theorems contribute to reducing the search space of(
d
,
c
)-MPs. If M
(
u
X
)
≥
d, then we have M
(
l
X
)
<
d
≤
M
(
u
X
). In such case, the enumeration algorithm can be used to search for (
d
,
c
)-MPs in set X by Corollary 3. Now we consider a special case wherein set X satisfies l
X
=
(
0,0
,
…
,
0
) and M
(
u
X
)
≥
d simultaneously. The following theorem shows that ad-flow (f
1
d,f
2
d
,
…
,
f
m
d) can be derived from X using the max-flow algorithm, whered-flow (f
1
d,f
2
d
,
…
,
f
m
d) consists of flowsf
i
d through each arc e
i for 1
≤
i
≤
m when the max-flow of the network from s to t isd.Theorem 7.
For setX, if l
X
=
(
0
,
0
,
…
,
0
) and M
(
u
X
)
≥
d, then there exists at least oned-flow (
f
1
d,f
2
d
,
…
,
f
m
d
) such that (
f
1
d,f
2
d
,
…
,
f
m
d
)
∈
X.Proof.
SinceM
(
u
X
)
≥
d, at least d units of flow can be transmitted from the source to the destination when the network is under u
X. Also, such a d-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
) can be obtained by the following steps [10, 12, 13]:(a)
Add a fictitious nodet
∗, and add an arc with a fixed state d from t to t
∗.
(b)
The state of each arce
i
∈
E is defined by u
i
X.
(c)
Determine the max-flow froms to t
∗. Since M
(
u
X
)
≥
d, and the state of the arc from t to t
∗ isd, the max-flow from s to t
∗ isd.
(d)
For eache
i
∈
E, the flows f
i
d through e
i constitute ad-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
) whenever the max-flow d from s to t
∗ is determined.
Since the flowsf
i
d through e
i are upper bounded by u
i
X, we have f
i
d
≤
u
i
X for all e
i
∈
E. Meanwhile, it is apparent that f
i
d
≥
0 for all e
i
∈
E. Thus, we have 0
≤
f
i
d
≤
u
i
X for all e
i
∈
E; that is, l
i
X
≤
f
i
d
≤
u
i
X for all e
i
∈
E. Consequently, we haved-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
)
∈
X.The definition ofd-flow indicates that ad-flow satisfies the flow conservation law; thus, it satisfies (7)–(9). Accordingly, for such ad-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
) derived from X by Theorem 7, if there is no directed cycle in it and ∑
i
=
1
m
C
i
f
i
d
≤
c, it is a (
d
,
c
)-MP. Otherwise, it is not a (
d
,
c
)-MP. Grounded on the obtainedd-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
), set X can be decomposed into disjoint subsets from which other (
d
,
c
)-MPs can be derived. The decomposition technique which is proposed by Jane and Laih [13] will be described below.LetE
d
(
X
)
=
{
e
i
∣
e
i
∈
E
&
f
i
d
>
0
}; then it is obvious that E
d
(
X
) is nonempty. Suppose E
d
(
X
)
=
{
e
z
1
,
e
z
2
,
…
,
e
z
q
}, by pivoting on arcs e
z
1, e
z
2
,
…, e
z
qone by one; X is decomposed into q
+
1 nonempty disjoint subsets X
1, X
2
,
…, X
q, and X
0 as follows:(1)
Pivot on arce
z
1
:
(12)
X
1
=
x
1
,
x
2
,
…
,
x
m
0
≤
x
z
1
≤
f
z
1
d
-
1
,
x
i
∈
K
i
X
for
e
i
∈
E
∖
e
z
1
.
(2)
Pivot on arce
z
2
:
(13)
X
2
=
x
1
,
x
2
,
…
,
x
m
f
z
1
d
≤
x
z
1
≤
u
z
1
X
,
0
≤
x
z
2
≤
f
z
2
d
-
1
,
x
i
∈
K
i
X
for
e
i
∈
E
∖
e
z
1
,
e
z
2
.
(3)
⋮
(q)
Pivot on arce
z
q
:
X
q
=
{
x
1
,
x
2
,
…
,
x
m
∣
f
i
d
≤
x
i
≤
u
i
X
f
o
r
e
i
∈
e
z
1
,
e
z
2
,
…
,
e
z
q
-
1, 0
≤
x
z
q
≤
f
z
q
d
-
1, x
i
∈
K
i
X
f
o
r
e
i
∈
E
∖
E
d
(
X
)
}
(q + 1)
X
0 = {
(
x
1
,
x
2
,
…
,
x
m
)
∣
f
i
d
≤
x
i
≤
u
i
X
f
o
r
e
i
∈
E
d
(
X
), x
i
∈
K
i
X for e
i
∈
E
∖
E
d
(
X
)
}.Theorem 8.
(i)X
=
X
1
∪
X
2
∪
⋯
∪
X
q
∪
X
0; (ii) subsets X
1, X
2
,
…, X
q, and X
0 are nonempty and disjoint; (iii)d-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
) is the smallest state vector in X
0.Readers may refer to the work of Jane and Laih [13] for the proofs. Now, we first consider subset X
0. Since thed-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
) derived from Theorem 7 is the smallest state vector in set X
0, if it is a (
d
,
c
)-MP, it is the unique (
d
,
c
)-MP in set X
0; otherwise, there is no (
d
,
c
)-MP in set X
0. As a result, there is no need to check other state vectors in X
0; that is, X
0 can be discarded as soon asd-flow (f
1
d
,
f
2
d
,
…
,
f
m
d) has been checked, which will reduce the number of enumerated state vectors to a large extent.Then, we discuss subsetsX
i
(
2
≤
i
≤
q
). For each  X
i
(
2
≤
i
≤
q
), if M
(
u
X
i
)
<
d or M
(
l
X
i
)
>
d for subset X
i
(
2
≤
i
≤
q
), there is no (
d
,
c
)-MP in X
i by Theorem 6 or Theorem 4. Then X
i is discarded, which will also cut down the search space of (
d
,
c
)-MPs. If M
(
l
X
i
)
=
d, we only need to check whether l
X
iis a (
d
,
c
)-MP by Theorem 5. Otherwise, we have M
(
l
X
i
)
<
d
≤
M
(
u
X
i
), and thus the enumeration algorithm can be employed to search for (
d
,
c
)-MPs in X
i by Corollary 3.Finally, we discuss subsetX
1. It is noted that l
X
1
=
(
0
,
0
,
…
,
0
). If M
(
u
X
1
)
<
d, X
1 is also discarded. Otherwise, subset X
1 satisfies l
X
=
(
0,0
,
…
,
0
) and M
(
u
X
1
)
≥
d simultaneously. Consequently, Theorem 7 can be applied to obtain ad-flow from X
1. Based on the derivedd-flow, X
1 is decomposed into nonempty disjoint subsets in the same manner. As discussed earlier, all of these subsets can be handled similarly. The decomposition procedure will be terminated when no subset,  X
_, satisfies l
X
_
=
(
0,0
,
…
,
0
) and M
(
u
X
_
)
≥
d simultaneously.Based on the above discussions, all(
d
,
c
)-MPs can be found using the following steps.Step
0
. Let X
=
{
x
∣
x
=
(
x
1
,
x
2
,
…
,
x
m
), 0
≤
x
i
≤
m
i
n
{
u
i
,
d
} for 1
≤
i
≤
m
}.Step
1
. Compute M
(
u
X
). If M
(
u
X
)
<
d, there is no (
d
,
c
)-MP in X (by Theorem 6), and halt.Step
2
. Seek ad-flow (
f
1
d
,
f
2
d
,
…
,
f
m
d
) by Theorem 7 and compute E
d
(
X
).Step
3
. For e
i
∈
E
d
(
X
), X is decomposed into X
1, X
2
,
…, X
q, and X
0 by Theorem 8.Step
4
. For X
0, if there is no directed cycle in it and ∑
i
=
1
m
C
i
f
i
d
≤
c, it is a (
d
,
c
)-MP; otherwise, it is not a (
d
,
c
)-MP.Step
5
. Fori = 2 toq,(5.1)
computeM
(
u
X
i
); if M
(
u
X
i
)
<
d, there is no (
d
,
c
)-MP in X
i (by Theorem 6), and go to (5.4);
(5.2)
computeM
(
l
X
i
); if M
(
l
X
i
)
>
d, there is no (
d
,
c
)-MP in X
i (by Theorem 4); if M
(
l
X
i
)
=
d, check if l
X
iis a (
d
,
c
)-MP by Corollary 3, and go to (5.4);
(5.3)
use the enumeration algorithm to search for(
d
,
c
)-MPs in X
i by Corollary 3;
(5.4)
i
=
i
+
1.Step
6
. Let X
=
X
1, and go to Step 1.The time complexity of the proposed method is discussed below. Either Step0 or Step 6 takes O
(
m
) time. Step 1 takes O
(
n
3
) to evaluate M
(
u
X
) [14]. Ad-flow can be found in O
(
n
3
) time by the max-flow algorithm. It requires O
(
m
) time to obtain E
d
(
X
) [13]. Then, Step 2 requires O
(
n
3
) time in total. Step 3 takes O
(
m
) time to decompose X. Step 4 requires O
(
m
+
n
) time. Therefore, the algorithm totally takes O
(
n
3
) time from Steps 0 to 4. It is apparent that the time complexity of Step 5 is determined by the number of enumerated state vectors. The number of state vectors in Step 5 is less than ∏
i
=
1
m
(
m
i
n
{
u
i
,
d
}
+
1
); thus, the time complexity of Step 5 is less than O
(
(
m
+
n
)
∏
i
=
1
m
(
m
i
n
{
u
i
,
d
}
+
1
)). Therefore, the time complexity of the proposed algorithm is less than O
(
(
m
+
n
)
∏
i
=
1
m
(
m
i
n
{
u
i
,
d
}
+
1
)).


## 4. An Illustrative Example

In this section, we use a simple logistics network to demonstrate the proposed algorithm step by step. The network, as shown in Figure1, is cited from the literature in [6–9]. The data of each arc is given in Table 1. If the manager is assigned a budget of 14 (c = 14) to transport 3 units of commodity (demand leveld = 3) from s tot, the reliability indexR
(3,14) can be obtained as follows (for convenience, the set of state vectors X is denoted by its smallest and largest state vectors as [l
X, u
X]).Step
0
. Let X
=
[
(
0,0
,
0,0
,
0,0
)
,
(
3,2
,
1,1
,
2,2
)
].Step
1
.
M
(
u
X
)
=
4
>
3.Step
2
. Seek a 3-flow (3, 2, 1, 0, 0, 1), and compute E
3
(
X
)
=
{
e
1
,
e
2
,
e
3
,
e
6
}.Step
3
. X is decomposed into X
1, X
2, X
3, X
4, and X
0, where X
1
=
[
(
0,0
,
0,0
,
0,0
)
,
(
2,2
,
1,1
,
2,2
)
], X
2
=
[
(
3,0
,
0,0
,
0,0
)
,
(
3,1
,
1,1
,
2,2
)
], X
3
=
[
(
3,2
,
0,0
,
0,0
)
,
(
3,2
,
0,1
,
2,2
)
], X
4
=
[
(
3,2
,
1,0
,
0,0
),(
3,2
,
1,1
,
2,0
)
], and X
0
=
[
(
3,2
,
1,0
,
0,1
)
,
(
3,2
,
1,1
,
2,2
)
].Step
4
. Since C
(
l
X
0
)
=
15
>
14, l
X
0
=
(
3
,
2,1
,
0,0
,
1
) is not a (3, 14)-MP.Step
5
.
i
=
2.(5.1)
X
2
=
[
(
3,0
,
0,0
,
0,0
)
,
(
3,1
,
1,1
,
2,2
)
], and M
(
u
X
2
)
=
3.
(5.2)
M
(
l
X
2
)
=
0.
(5.3)
Use the enumeration algorithm to search for (3, 14)-MPs inX
2, but there is no (3, 14)-MP.
(5.4)
i
=
3.
(5.1)
X
3
=
[
(
3,2
,
0,0
,
0,0
)
,
(
3,2
,
0,1
,
2,2
)
], and M
(
u
X
3
)
=
4.
(5.2)
M
(
l
X
3
)
=
2.
(5.3)
Use the enumeration algorithm to search for (3, 14)-MPs inX
3, but there is no (3, 14)-MP.
(5.4)
i
=
4.
(5.1)
X
4
=
[
(
3,2
,
1,0
,
0,0
)
,
(
3,2
,
1,1
,
2,0
)
], and M
(
u
X
4
)
=
2
<
3; then there is no (3, 14)-MP in X
4.Step
6
. Let X
=
X
1
=
[
(
0,0
,
0,0
,
0,0
)
,
(
2,2
,
1,1
,
2,2
)
], and go to Step 1.Step
1
.
M
(
u
X
)
=
4
>
3.Step
2
. Seek a 3-flow (2, 2, 0, 0, 1, 1), E
3
(
X
)
=
{
e
1
,
e
2
,
e
5
,
e
6
}.Step
3
. X is decomposed into X
1
-
1, X
1
-
2, X
1
-
3, X
1
-
4, and X
1
-
0, where X
1
-
1 = [(0, 0, 0, 0, 0, 0), (1, 2, 1, 1, 2, 2)], X
1
-
2 = [(2, 0, 0, 0, 0, 0), (2, 1, 1, 1, 2, 2)], X
1
-
3 = [(2, 2, 0, 0, 0, 0), (2, 2, 1, 1, 0, 2)], X
1
-
4 = [(2, 2, 0, 0, 1, 0), (2, 2, 1, 1, 2, 0)], and X
1
-
0 = [(2, 2, 0, 0, 1, 1), (2, 2, 1, 1, 2, 2)].⫽ the disjoint sets of state vectors are denoted here as X
1
-
1, X
1
-
2, X
1
-
3, X
1
-
4, and X
1
-
0
⫽Step
4
. Since there is no directed cycle in (2, 2, 0, 0, 1, 1), andC(l
X
1
-
0) = 12 < 14, l
X
1
-
0= (2,2,0,0,1,1) is a (3, 14)-MP.Step
5
.
i
=
2.(5.1)
X
1
-
2
=
[
(
2,0
,
0,0
,
0,0
)
,
(
2,1
,
1,1
,
2,2
)
], andM(u
X
1
-
2) = 3.
(5.2)
M
(
l
X
1
-
2
)
=
0.
(5.3)
Use the enumeration algorithm to search for (3, 14)-MPs inX
1
-
2, but there is no (3, 14)-MP.
(5.4)
i
=
3.
(5.1)
X
1
-
3 = [(2, 2, 0, 0, 0, 0), (2, 2, 1, 1, 0, 2)], and M
(
u
X
1
-
3
)
=
2
<
3, then there is no (3, 14)-MP in X
1
-
3, and go to (5.4).
(5.4)
i
=
4.
(5.1)
X
1
-
4
=
[
(
2,2
,
0,0
,
1,0
)
,
(
2,2
,
1,1
,
2,0
)
], and M
(
u
X
1
-
4
)
=
2
<
3; then there is no (3, 14)-MP in X
1
-
4.Step
6
. LetX = X
1
-
1 = [(0, 0, 0, 0, 0, 0), (1, 2, 1, 1, 2, 2)], and go to Step 1.Step
1
.
M
(
u
X
)
=
3.Step
2
. Seek a 3-flow (1, 1, 0, 0, 2, 2), E
3
(
X
)
=
{
e
1
,
e
2
,
e
5
,
e
6
}.Step
3
.
X is decomposed into X
1
-
1
-
1, X
1
-
1
-
2, X
1
-
1
-
3, X
1
-
1
-
4, and X
1
-
1
-
0, where X
1
-
1
-
1
=
[
(
0,0
,
0,0
,
0,0
)
,
(
0,2
,
1,1
,
2,2
)
], X
1
-
1
-
2
=
[
(
1,0
,
0,0
,
0,0
)
,
(
1,0
,
1,1
,
2,2
)
], X
1
-
1
-
3
=
[
(
1,1
,
0,0
,
0,0
)
,
(
1,2
,
1,1
,
1,2
)
], X
1
-
1
-
4
=
[
(
1,1
,
0,0
,
2,0
)
,
(
1,2
,
1,1
,
2,1
)
], and X
1
-
1
-
0
=
[
(
1,1
,
0,0
,
2,2
)
,
(
1,2
,
1,1
,
2,2
)
].⫽the disjoint sets of state vectors are denoted here as X
1
-
1
-
1, X
1
-
1
-
2, X
1
-
1
-
3, X
1
-
1
-
4, and X
1
-
1
-
0
⫽Step
4
. Since there is no directed cycle in (1, 1, 0, 0, 2, 2), andC(l
X
1
-
1
-
0) = 12 < 14, l
X
1
-
1
-
0
=
(
1
,
1
,
0
,
0
,
2
,
2
) is a (3, 14)-MP.Step
5
.
i
=
2.(5.1)
X
1
-
1
-
2
=
[
(
1,0
,
0,0
,
0,0
)
,
(
1,0
,
1,1
,
2,2
)
], and M
(
u
X
1
-
1
=
2
)
=
2, then there is no (3, 14)-MP in X
1
-
1
-
2, and go to (5.4).
(5.4)
i = 3.
(5.1)
X
1
-
1
-
3
=
[
(
1,1
,
0,0
,
0,0
)
,
(
1,2
,
1,1
,
1,2
)
], and M
(
u
X
1
-
1
=
3
)
=
2, then there is no (3, 14)-MP in X
1
-
1
-
3, and go to (5.4).
(5.4)
i
=
4.
(5.1)
X
1
-
1
-
4
=
[
(
1,1
,
0,0
,
2,0
)
,
(
1,2
,
1,1
,
2,1
)
], and M
(
u
X
1
-
1
-
4
)
=
3.
(5.2)
M(l
X
1
-
1
-
4) = 1.
(5.3)
Use the enumeration algorithm to search for (3, 14)-MPs inX
1
-
1
-
4, and (1,2,0,1,2,1) is a (3, 14)-MP.Step
6
. LetX = X
1
-
1
-
1
=
[
(
0,0
,
0,0
,
0,0
)
,
(
0,2
,
1,1
,
2,2
)
], and go to Step 1.Step
1
.
M
(
u
X
)
=
2
<
3, and halt.Consequently, (2, 2, 0, 0, 1, 1), (1, 1, 0, 0, 2, 2), and (1, 2, 0, 1, 2, 1) are all (3, 14)-MPs. LetB
1
=
{
x
∣
x
≥
(
2,2
,
0,0
,
1,1
)
}, B
2
=
{
x
∣
x
≥
(
1,2
,
0,1
,
2,1
)
}, and B
3
=
{
x
∣
x
≥
(
1,1
,
0,0
,
2,2
)
}; then, according to (1), R
(
3,14
)
=
P
r
{
B
1
∪
B
2
∪
B
3
} = P
r
{
B
1
}
+
P
r
{
B
2
}
+
P
r
{
B
3
} − P
r
{
B
1
∩
B
2
}
-
P
r
{
B
1
∩
B
3
} − P
r
{
B
2
∩
B
3
}
+
P
r
{
B
1
∩
B
2
∩
B
3
} = P
r
{
x
∣
x
≥
(
2,2
,
0,0
,
1,1
)
}
+
P
r
{
x
∣
x
≥
(
1,2
,
0,1
,
2,1
)
} + P
r
{
x
∣
x
≥
(
1,1
,
0,0
,
2,2
)
}
-
P
r
{
x
∣
x
≥
(
2,2
,
0,1
,
2,1
)
} − P
r
{
x
∣
x
≥
(
2,2
,
0,0
,
2,2
)
}
-
P
r
{
x
∣
x
≥
(
1,2
,
0,1
,
2,2
)
} + P
r
{
x
∣
x
≥
(
2,2
,
0,1
,
2,2
)
}
=
0.64005
.That is, the probability of transmitting 3 units of commodity demand froms to t with the total transportation cost less than or equal to 14 is 0.64005 (note that the final result R
(
3,14
)
=
0.66861 in [7, 9] is incorrect). The value, 0.64005, gives the manager information on the capability of the network to ensure the shipment of 3 units of commodity within the budget 14 from s to t. If this value is below the threshold set by the manager, more investments are needed to improve the logistics network. Otherwise, the performance of the logistics network is desirable.


## 5. Computational Experiments

As pointed out in Section2, the algorithms of Yeh [8] and Niu and Xu [9] solve the (
d
,
c
)-MP problem without knowing all MPs in advance. Therefore, we conduct numerical experiments to check the performance of the proposed algorithm by comparing it with the algorithms of Yeh and Niu and Xu. A multistate network, as shown in Figure 2, is cited from the literature in [9]. The largest state vector and the cost vector are u
=
(
2,4
,
2,2
,
1,3
,
2,3
,
1,2
,
2,2
,
4
) and C
=
(
3,2
,
1,2
,
1,2
,
3,2
,
1,3
,
1,2
,
3
), respectively. All of the three algorithms are implemented in a MATLAB program with a PC (AMD Athlon (tm) 64 X2 1.71 GHz C PU). To comprehensively embody the performance of the three algorithms, six different combinations of demand level and cost constraint are randomly chosen. The computational results are listed in Table 2.Table 2
The computational time of different algorithms.
(d, c)-MP
Computational time (s)
Relative ratio
T
Y
e
h
T
N
i
u
&
X
u
T
N
e
w
T
Y
e
h/T
N
e
w
T
N
i
u
&
X
u/T
N
e
w
(1, 10)-MP
0.142
0.721
0.138
1.029
5.225
(2, 17)-MP
5.103
5.799
0.669
7.628
8.668
(3, 27)-MP
14.275
9.705
1.101
12.965
8.815
(4, 36)-MP
20.841
5.752
1.197
17.411
4.805
(5, 49)-MP
20.319
0.831
0.814
24.451
1.021
(6, 60)-MP
19.409
0.627
0.472
41.121
1.328Figure 2It is observed from Table2 that the proposed algorithm spends less time than Yeh’s [8] in searching for different (
d
,
c
)-MPs. In particular, the proposed algorithm has a better searching efficiency as the demand level d grows. This is as expected, because Yeh’s algorithm is an exhaustive enumeration method in nature, whereas the proposed algorithm utilizes a decomposition technique to divide the search space, such that the search space of (
d
,
c
)-MPs can be dramatically reduced, and thereby (
d
,
c
)-MPs can be efficiently obtained. Furthermore, Table 2 shows that the proposed algorithm displays an advantage over the algorithm of Niu and Xu [9]. Both of them are partial-enumeration methods, but the proposed technique is more effective in shortening the search space of (
d
,
c
)-MPs. Therefore, the proposed algorithm outperforms the two methods in solving (
d
,
c
)-MPs.


## 6. Conclusions

Reliability analysis is a fundamental tool for understanding the operational level of logistics networks. Logistics network can be modeled as a typical multistate flow network in which arcs are associated with multiple integer capacities, operational reliability, and unit transportation cost. The reliability indexR
(
d
,
c
) which takes into account both reliability and transportation cost can serve as a comprehensive performance assessment of logistics networks. This paper is devoted to proposing a new efficient algorithm for solving all (
d
,
c
)-MPs. A major contribution of this paper is that we develop a new approach to shorten the search space of (
d
,
c
)-MP. Specifically, the proposed algorithm employs an effective decomposition technique to divide the search space of (
d
,
c
)-MPs such that the search space of (
d
,
c
)-MPs can be dramatically reduced. A real example is used to illustrate the applicability of the proposed algorithm. Also, to check the performance of the proposed algorithm, computational experiments on a medium-sized logistics network are conducted, and the results show that the proposed algorithm has an advantage over the existing methods [5–9].For future research, there is still a room for developing efficient methods forR
(
d
,
c
). For example, as with the existing algorithms [4–9], the proposed algorithm is also an enumeration method in nature, and thus it still needs to perform the enumeration of state vectors. Therefore, it is more desirable to develop new methods which are not grounded on the enumeration of state vectors. Furthermore, we only consider the transmission of single type of commodity in the network. Thus, it is more practical to extend the proposed algorithm to the reliability evaluation of multicommodity multistate networks under cost constraint in which multiple types of commodity are transmitting from the source to the destination.



---

*Source: 2628950-2016-08-28.xml*