# Performance Assessment of a Freight Network with Stochastic Capacities

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

---

## Abstract

This paper focuses on performance assessment of a freight network with stochastic capacities by using reliability analysis, in which a node denotes a supplier, a transfer center, a distribution center, or a market, while an arc denotes a logistics service provider offering the freight traffic service for a pair of nodes. Due to some uncertainties in real environment (for example, a proportion of vehicles owned by the provider may be reserved by other customers), the available capacity of the provider along each arc is stochastic. Thus, network reliability that at leastd units of commodity demand can be successfully delivered from the source to the destination denotes the operational performance of such a freight network. A d-minimal path–based method is developed to evaluate the freight network reliability. To advance the efficiency of solving d-minimal paths, an improved model is established by redefining capacity bounds of arcs and minimal paths. Furthermore, a new concept of expected capacity grounded on network reliability is presented to measure the service performance of the freight network. A practical case related to the coal delivery network is studied to demonstrate the implications of both network reliability and expected capacity.


---

## Body

## 1. Introduction

From the perspective of logistics operation and management, it is vitally important to design a robust freight network that runs as well as possible under normal conditions, while also running relatively well under unexpected situations. Performance assessment is an effective manner to capture the operational state of freight networks in a complex environment and thus plays a critical role in logistics management. Traditionally, most studies [1–5] have studied the performance of freight/logistics networks from several aspects, such as meeting customer needs, maximizing customer service levels, minimizing total costs, or ensuring timely delivery, in which market demand, service level, lead time, or distribution cost are the concerned factors directly effecting the performance of freight networks. However, the studied networks in the aforementioned literature are essentially deterministic. In reality, a freight network is always affected by various unexpected events, such that its capacity is subject to degradation. Therefore, whether the freight network is able to ensure the delivery of required quantity of goods from the supply point to the demand point is of utmost importance to both suppliers and customers. To guarantee an effective logistics performance, the key is to know the level of operation of the freight network both in stable and uncertain states [6].A freight network is composed of several nodes and arcs, where each node stands for a supplier, a transfer center, a distribution center, or a market, and each arc (route) linking a pair of nodes stands for a logistics service provider offering the freight traffic service. Since the capacity (the number of cars or trucks) of a provider may be reserved by other customers, its available capacity in the freight network is stochastic in nature. For example, it is assumed that the maximal capacity of a logistics service provider is three trucks. If all trucks are reserved by other customers, the available capacity is 0; if one truck is reserved, the available capacity is 2; if two trucks are reserved, the available capacity is 1. In this sense, the actual capacity of each provider in the freight network is looked upon as a random variable, following a specified probability distribution. Therefore, a freight network can be modeled as a typical stochastic-flow network, in which each arc has stochastic capacities, and the delivered commodities are considered as a flow [7–13].Reliability evaluation is a powerful tool for the demonstration of network performance. For a stochastic-flow network, the reliability indexRd is defined as the probability that at least d units of flow (i.e., commodity demand) can be successfully transmitted from the source to the destination through stochastic arc capacities [14–22]. To date, many studies [14–18, 21, 22] have evaluated the reliability Rd in terms of d-minimal paths. A d-minimal path x is a minimal capacity vector meeting the demand level d, which means that for any y<x,y does not meet the demand level d [14]. When all d-minimal paths are at hand, the inclusion-exclusion rule is available to calculate Rd [14, 15].There are two types of models reported to solved-minimal paths. One is first proposed by Lin et al. [14], and the other is originally proposed by Yeh [17]. Note that the model of Yeh [17] is built on the well-known max-flow mathematical programming model and is more applicable to directed networks (if it is used to solve undirected networks, an additional step of transforming undirected networks into directed networks is required [21]). Provided that all minimal paths are known, the model of Lin et al. [14] is based on the network structure and the flow-conservation law. A path is a sequence of arcs that connects the source node to the destination node, and a minimal path is such a path that removing any arc will make it no longer a path. The model by Lin et al. applicable to solving both directed networks and undirected networks is widely used by the existing algorithms [14–16, 22] to search for d-minimal paths. For example, Lin [15] proposed a method to solve d-minimal paths of a network with unreliable nodes; Yeh [16] proposed a cycle-checking method to verify whether a feasible solution to the model by Lin et al. is a d-MP; Chen and Lin [22] considered to utilize the fast enumeration method to solve d-minimal paths. To be worthy of attention, some constraints in the model of Lin et al. [14] are so relaxed that a large number of feasible solutions need to be checked in order to find all d-minimal paths, which to a large extent effects the computational efficiency.This paper concentrates on performance assessment of a freight network with stochastic capacity by using reliability analysis. Specifically, the major contributions of this paper are twofold. First, by redefining capacity bounds of arcs and minimal paths, we construct an improved model based on which an efficient algorithm is suggested to solved-minimal paths. Both complexity analysis and illustrative examples are provided to show the benefit of the proposed algorithm. As demonstrated through examples, the proposed algorithm compares favorably with the existing methods. Second, we propose a new concept of expected capacity grounded on network reliability to assess the service performance of a freight network. Thus, the performance level of a freight network with stochastic capacities can be evaluated in terms of either network reliability or expected capacity. A practical case study related to a coal delivery network is provided to illustrate the utility of the proposed algorithm and demonstrate the implications of both network reliability and expected capacity.The remainder of this paper is organized as follows. Section2 introduces the stochastic-flow network model and some basics for reliability evaluation. In Section 3, the fundamental model is first discussed, and then an improved model is constructed by redefining capacity bounds of arcs and minimal paths. An algorithm for solving d-minimal paths is presented in Section 4, along with discussions on its time complexity. A simple illustrative example and a numerical example are also provided in Section 4. A concept of expected capacity is put forward in Section 5. In Section 6, a practical case study is provided to explain the implications of both network reliability and expected capacity. Section 7 presents some concluding remarks.


## 2. Preliminaries

### 2.1. Stochastic-Flow Network

Theoretically, a freight network with stochastic capacities can be regarded as a typical stochastic-flow network. LetGV,E,W represent a stochastic-flow network, where V=s,1,2,…,n,t is the set of nodes with s (source node) denoting the supply point, t (destination node) denoting the demand point, and n denoting the number of nodes except s and t, E=e1,e2,…,em is the set of arcs (routes) with m denoting the number of arcs, where ei1≤i≤m is the ith arc connecting a pair of nodes, and W=W1,W2,…,Wm is the largest capacity vector with Wi1≤i≤m being the largest capacity of arc ei. Along each arc, a contracted logistics service provider is responsible for freight traffic. The available capacity of each logistics service provider is a random variable notated by xi, and xi takes integer values from 0 to Wi according to a given probability distribution. Note that the data with respect to capacity and its probability distribution can be obtained from the database of logistics service providers.A capacity vectorx=x1,x2,…,xm indicates the current capacity of each arc, and Mx denotes the max-flow of the network under x, i.e., the capacity of the freight network under x. As with the existing literature [7–13], the following assumptions are considered:
(1)
All flows in the network satisfy the flow-conservation law, i.e., total flows into and from a node (other than the source and destination nodes) are all equal
(2)
The capacities of different arcs (logistics service providers) are statistically independent
(3)
Flow in the network is an integer value
(4)
Each node is perfectly reliable, which means no constraint is imposed on the capacities of nodes (transfer center or distribution center is responsible for the transshipment service only)For example, Figure1 that is cited from [21] presents a simple freight network with V=s,1,2,t, n=2, E=e1,e2,e3,e4,e5, and m=5. The capacity and capacity probability distribution of each arc are given in Table 1 indicating W=3,2,1,2,2. Given a capacity vector x=2,1,0,1,2 which indicates the current capacities of e1,e2,e3,e4, and e5 are 2, 1, 0, 1, and 2, respectively, the max-flow of the network under x is Mx=2.Figure 1
A simple freight network.Table 1
The data of arcs in Figure1.
Arc
Capacities
Capacity probabilities
e1
0
1
2
3
0.05
0.10
0.25
0.60
e2
0
1
2
—
0.10
0.30
0.60
—
e3
0
1
—
—
0.10
0.90
—
—
e4
0
1
2
—
0.05
0.25
0.70
—
e5
0
1
2
—
0.10
0.20
0.70
—


### 2.2. Reliability Evaluation in terms ofd-Minimal Paths

As stated previously, the reliabilityRd that serves as a performance index of a freight network is defined as the probability that at least d units of commodity demand can be successfully delivered from the source to the destination, then Rd=Prx∣Mx≥d. Obviously, it is extremely time-consuming to calculate Rd by directly checking Mx≥d for every capacity vector x due to the large number of capacity vectors. Alternatively, most studies have focused on the d-minimal path–based method. A capacity vector x=x1,x2,…,xm is a d-minimal path if and only if (1) Mx=d and (2) Mx–0ei<d for each xi>0, where 0ei=0,…,0,1,0,…,0, i.e., the capacity level is 1 for ei and 0 for other arcs [14]. The definition implicitly demonstrates that a d-minimal path is the minimal capacity vector satisfying the demand level d. If all d-minimal paths are found, Rd can be calculated by the well-known inclusion-exclusion method.Assumingy1,y2,…,yσ are all d-minimal paths and let B1=x∣x≥y1,B2=x∣x≥y2,…,Bσ=x∣x≥yσ, where x=x1,x2,…,xm, yi=y1i,y2i,…,ymi, and x≥yi means that xj≥yji for j=1,2,…,m, then Rd can be evaluated via the inclusion-exclusion method as follows:
(1)Rd=Prx∣Mx≥d=PrB1⋃B2⋃⋯⋃Bσ=∑i=1σPrBi–∑j=2σ∑i=1j−1PrBi⋂Bj+⋯+–1σ–1PrB1⋂B2⋂⋯⋂Bσ,where PrBi=Prx∣x≥yi=∏k=1mPrxk≥yki,PrBi∩Bj=Prx∣x≥maxyi,yj=∏k=1mPrxk≥maxyki,ykj,…,PrB1∩B2∩⋯∩Bσ=Prx∣x≥maxy1,y2,…,yσ=∏k=1mPrxk≥maxyk1,yk2,…,ykσ.Therefore, thed-minimal path problem plays the key role in the network reliability evaluation and will be the focus in the subsequent discussions.


## 2.1. Stochastic-Flow Network

Theoretically, a freight network with stochastic capacities can be regarded as a typical stochastic-flow network. LetGV,E,W represent a stochastic-flow network, where V=s,1,2,…,n,t is the set of nodes with s (source node) denoting the supply point, t (destination node) denoting the demand point, and n denoting the number of nodes except s and t, E=e1,e2,…,em is the set of arcs (routes) with m denoting the number of arcs, where ei1≤i≤m is the ith arc connecting a pair of nodes, and W=W1,W2,…,Wm is the largest capacity vector with Wi1≤i≤m being the largest capacity of arc ei. Along each arc, a contracted logistics service provider is responsible for freight traffic. The available capacity of each logistics service provider is a random variable notated by xi, and xi takes integer values from 0 to Wi according to a given probability distribution. Note that the data with respect to capacity and its probability distribution can be obtained from the database of logistics service providers.A capacity vectorx=x1,x2,…,xm indicates the current capacity of each arc, and Mx denotes the max-flow of the network under x, i.e., the capacity of the freight network under x. As with the existing literature [7–13], the following assumptions are considered:
(1)
All flows in the network satisfy the flow-conservation law, i.e., total flows into and from a node (other than the source and destination nodes) are all equal
(2)
The capacities of different arcs (logistics service providers) are statistically independent
(3)
Flow in the network is an integer value
(4)
Each node is perfectly reliable, which means no constraint is imposed on the capacities of nodes (transfer center or distribution center is responsible for the transshipment service only)For example, Figure1 that is cited from [21] presents a simple freight network with V=s,1,2,t, n=2, E=e1,e2,e3,e4,e5, and m=5. The capacity and capacity probability distribution of each arc are given in Table 1 indicating W=3,2,1,2,2. Given a capacity vector x=2,1,0,1,2 which indicates the current capacities of e1,e2,e3,e4, and e5 are 2, 1, 0, 1, and 2, respectively, the max-flow of the network under x is Mx=2.Figure 1
A simple freight network.Table 1
The data of arcs in Figure1.
Arc
Capacities
Capacity probabilities
e1
0
1
2
3
0.05
0.10
0.25
0.60
e2
0
1
2
—
0.10
0.30
0.60
—
e3
0
1
—
—
0.10
0.90
—
—
e4
0
1
2
—
0.05
0.25
0.70
—
e5
0
1
2
—
0.10
0.20
0.70
—


## 2.2. Reliability Evaluation in terms ofd-Minimal Paths

As stated previously, the reliabilityRd that serves as a performance index of a freight network is defined as the probability that at least d units of commodity demand can be successfully delivered from the source to the destination, then Rd=Prx∣Mx≥d. Obviously, it is extremely time-consuming to calculate Rd by directly checking Mx≥d for every capacity vector x due to the large number of capacity vectors. Alternatively, most studies have focused on the d-minimal path–based method. A capacity vector x=x1,x2,…,xm is a d-minimal path if and only if (1) Mx=d and (2) Mx–0ei<d for each xi>0, where 0ei=0,…,0,1,0,…,0, i.e., the capacity level is 1 for ei and 0 for other arcs [14]. The definition implicitly demonstrates that a d-minimal path is the minimal capacity vector satisfying the demand level d. If all d-minimal paths are found, Rd can be calculated by the well-known inclusion-exclusion method.Assumingy1,y2,…,yσ are all d-minimal paths and let B1=x∣x≥y1,B2=x∣x≥y2,…,Bσ=x∣x≥yσ, where x=x1,x2,…,xm, yi=y1i,y2i,…,ymi, and x≥yi means that xj≥yji for j=1,2,…,m, then Rd can be evaluated via the inclusion-exclusion method as follows:
(1)Rd=Prx∣Mx≥d=PrB1⋃B2⋃⋯⋃Bσ=∑i=1σPrBi–∑j=2σ∑i=1j−1PrBi⋂Bj+⋯+–1σ–1PrB1⋂B2⋂⋯⋂Bσ,where PrBi=Prx∣x≥yi=∏k=1mPrxk≥yki,PrBi∩Bj=Prx∣x≥maxyi,yj=∏k=1mPrxk≥maxyki,ykj,…,PrB1∩B2∩⋯∩Bσ=Prx∣x≥maxy1,y2,…,yσ=∏k=1mPrxk≥maxyk1,yk2,…,ykσ.Therefore, thed-minimal path problem plays the key role in the network reliability evaluation and will be the focus in the subsequent discussions.


## 3. An Improved Model with respect tod-Minimal Paths

### 3.1. The Basic Model

As mentioned before, the model proposed by Lin et al. [14] is one of the two fundamental models adopted to solve d-minimal paths. In this section, we will make some efforts to improve the model by Lin et al. It is assumed that there are p minimal paths, say, P1,P2,…,Pp, from the source node to the destination node in the network. The flow through Pj1≤j≤p is denoted by Fj1≤j≤p. F=F1,F2,…,Fp that consists of flows through all minimal paths is called a flow vector. The model of Lin et al. is built on the following lemma [14–16, 22].Lemma 1.
Given the demand leveld, a capacity vector x=x1,x2,…,xm is called a d-minimal path candidate if it satisfies the following conditions:
(2)F1+F2+⋯+Fp=d,(3)0≤Fj≤CPjfor1≤j≤p,(4)0≤∑ei∈PjFj≤Wifor1≤i≤m,(5)xi=∑ei∈PjFjfor1≤i≤m,where CPj=minWi∣ei∈Pj is the capacity of minimal path Pj. Equation (2) shows that the summation of flows through all minimal paths must be equal to demand level d, condition (3) points out that the flow through Pj should not exceed the capacity of Pj, and condition (4) indicates that the flow through ei should not be above the largest capacity of ei. Equation (5) specifies the relationship between the current capacity of ei and the flow through ei. It should be noted that the feasible solution derived from Lemma 1 is a d-minimal path candidate [14]. Each d-minimal path is a d-minimal path candidate, but a d-minimal path candidate is not necessarily a d-minimal path. Therefore, a d-minimal path candidate needs to be checked to further determine whether it is a d-minimal path or not. The popular methods for checking d-minimal path candidates include the comparison method [14, 15] and the cycle-checking method [16]. The comparison method is easy to understand and is based on the following lemma [14, 15].Lemma 2.
For ad-minimal path candidate x, if there exists no d-minimal path candidate y such that x>y, where x>y means xi≥yi for i=1,2,…,m and xj>yj for at least one j1≤j≤m, then x is a d-minimal path.


### 3.2. The Improved Model

A flow vectorF=F1,F2,…,Fp satisfying conditions (2)–(4) is said to be a feasible flow vector. Lemma 1 shows that it first needs to find all of the feasible flow vectors, and then each feasible flow vector is transformed into its corresponding d-minimal path candidate by (5). Note that when the cost of solving feasible flow vectors is decreased, the efficiency of solving d-minimal paths would be improved. As can be seen below, the lower bounds in condition (4) have the potential to be raised, and the upper bounds in conditions (3) and (4) have the potential to be dropped.LetW0i denote a special capacity vector in which the capacity level is 0 for ei, and the capacity level is the largest capacity for other arcs, i.e., W0i=W1,W2,…,Wi−1,0,Wi+1,…,Wm and Li=max0,d–MW0i, then the following theorem clearly presents the necessary condition for a capacity vector to be a d-minimal path.Theorem 1.
Given the demand leveld, if a capacity vector x=x1,x2,…,xm is a d-minimal path, then xi≥Li for 1≤i≤m.Proof 1.
Clearly,Li≥0 holds. If Li=0, it is easy to have xi≥Li.
IfLi>0, it means Li=d–MW0i>0. First, it is noted that MW≥d. Thus, when d–MW0i>0, i.e., MW0i<d, it means that at least d–MW0i units of flow must travel through arc ei in order for d units of flow to be transmitted from the source node to the destination node. If x is a d-minimal path, Mx=d holds, i.e., d units of flow can be transmitted from the source node to the destination node under x. As a result, it is deduced that xi≥d–MW0i=Li.In Theorem1, Li can be looked upon as a new lower capacity bound of ei, and thus it is used in condition (4) to reduce the cost of solving feasible flow vectors. Because computing MW0i requires On3 time [23, 24], the time complexity of determining Li is also On3. Therefore, the total time complexity of finding all lower bounds in condition (4) is Omn3.Corollary 1.
The time complexity of finding all lower bounds in condition (4) is Omn3.It should be pointed out that the time complexityOmn3 of finding all lower bounds, i.e., Corollary 1, is far lower than the one for solving d-minimal path candidates, so it has no influence on the whole algorithm. Additionally, notice that F1+F2+⋯+Fp=d in condition (2) means Fj≤d for 1≤j≤p, and it is easy to know ∑ei∈PjFj≤F1+F2+⋯+Fp=d; hence, the upper bounds in conditions (3) and (4) can be replaced by minCPj,d and minWi,d, respectively. Grounding on Theorem 1 and the above analyses, the following improved model can be constructed to solve all d-minimal path candidates.Theorem 2.
Given the demand leveld, a capacity vector x=x1,x2,…,xm is called a d-minimal path candidate if it satisfies the following conditions:
(6)F1+F2+⋯+Fp=d,(7)0≤Fj≤minCPj,dfor1≤j≤p,(8)Li≤∑ei∈PjFj≤minWi,dfor1≤i≤m,(9)xi=∑ei∈PjFjfor1≤i≤m.Proof 2.
Directly from Theorem1 and Lemma 1.
Obviously, Theorem2 is an improvement to Lemma 1 in view of the tighter capacity constraints imposed on ei (corresponding to conditions (7) and (8)), and it is the foundation of the designed algorithm for solving d-minimal paths in this paper.


## 3.1. The Basic Model

As mentioned before, the model proposed by Lin et al. [14] is one of the two fundamental models adopted to solve d-minimal paths. In this section, we will make some efforts to improve the model by Lin et al. It is assumed that there are p minimal paths, say, P1,P2,…,Pp, from the source node to the destination node in the network. The flow through Pj1≤j≤p is denoted by Fj1≤j≤p. F=F1,F2,…,Fp that consists of flows through all minimal paths is called a flow vector. The model of Lin et al. is built on the following lemma [14–16, 22].Lemma 1.
Given the demand leveld, a capacity vector x=x1,x2,…,xm is called a d-minimal path candidate if it satisfies the following conditions:
(2)F1+F2+⋯+Fp=d,(3)0≤Fj≤CPjfor1≤j≤p,(4)0≤∑ei∈PjFj≤Wifor1≤i≤m,(5)xi=∑ei∈PjFjfor1≤i≤m,where CPj=minWi∣ei∈Pj is the capacity of minimal path Pj. Equation (2) shows that the summation of flows through all minimal paths must be equal to demand level d, condition (3) points out that the flow through Pj should not exceed the capacity of Pj, and condition (4) indicates that the flow through ei should not be above the largest capacity of ei. Equation (5) specifies the relationship between the current capacity of ei and the flow through ei. It should be noted that the feasible solution derived from Lemma 1 is a d-minimal path candidate [14]. Each d-minimal path is a d-minimal path candidate, but a d-minimal path candidate is not necessarily a d-minimal path. Therefore, a d-minimal path candidate needs to be checked to further determine whether it is a d-minimal path or not. The popular methods for checking d-minimal path candidates include the comparison method [14, 15] and the cycle-checking method [16]. The comparison method is easy to understand and is based on the following lemma [14, 15].Lemma 2.
For ad-minimal path candidate x, if there exists no d-minimal path candidate y such that x>y, where x>y means xi≥yi for i=1,2,…,m and xj>yj for at least one j1≤j≤m, then x is a d-minimal path.


## 3.2. The Improved Model

A flow vectorF=F1,F2,…,Fp satisfying conditions (2)–(4) is said to be a feasible flow vector. Lemma 1 shows that it first needs to find all of the feasible flow vectors, and then each feasible flow vector is transformed into its corresponding d-minimal path candidate by (5). Note that when the cost of solving feasible flow vectors is decreased, the efficiency of solving d-minimal paths would be improved. As can be seen below, the lower bounds in condition (4) have the potential to be raised, and the upper bounds in conditions (3) and (4) have the potential to be dropped.LetW0i denote a special capacity vector in which the capacity level is 0 for ei, and the capacity level is the largest capacity for other arcs, i.e., W0i=W1,W2,…,Wi−1,0,Wi+1,…,Wm and Li=max0,d–MW0i, then the following theorem clearly presents the necessary condition for a capacity vector to be a d-minimal path.Theorem 1.
Given the demand leveld, if a capacity vector x=x1,x2,…,xm is a d-minimal path, then xi≥Li for 1≤i≤m.Proof 1.
Clearly,Li≥0 holds. If Li=0, it is easy to have xi≥Li.
IfLi>0, it means Li=d–MW0i>0. First, it is noted that MW≥d. Thus, when d–MW0i>0, i.e., MW0i<d, it means that at least d–MW0i units of flow must travel through arc ei in order for d units of flow to be transmitted from the source node to the destination node. If x is a d-minimal path, Mx=d holds, i.e., d units of flow can be transmitted from the source node to the destination node under x. As a result, it is deduced that xi≥d–MW0i=Li.In Theorem1, Li can be looked upon as a new lower capacity bound of ei, and thus it is used in condition (4) to reduce the cost of solving feasible flow vectors. Because computing MW0i requires On3 time [23, 24], the time complexity of determining Li is also On3. Therefore, the total time complexity of finding all lower bounds in condition (4) is Omn3.Corollary 1.
The time complexity of finding all lower bounds in condition (4) is Omn3.It should be pointed out that the time complexityOmn3 of finding all lower bounds, i.e., Corollary 1, is far lower than the one for solving d-minimal path candidates, so it has no influence on the whole algorithm. Additionally, notice that F1+F2+⋯+Fp=d in condition (2) means Fj≤d for 1≤j≤p, and it is easy to know ∑ei∈PjFj≤F1+F2+⋯+Fp=d; hence, the upper bounds in conditions (3) and (4) can be replaced by minCPj,d and minWi,d, respectively. Grounding on Theorem 1 and the above analyses, the following improved model can be constructed to solve all d-minimal path candidates.Theorem 2.
Given the demand leveld, a capacity vector x=x1,x2,…,xm is called a d-minimal path candidate if it satisfies the following conditions:
(6)F1+F2+⋯+Fp=d,(7)0≤Fj≤minCPj,dfor1≤j≤p,(8)Li≤∑ei∈PjFj≤minWi,dfor1≤i≤m,(9)xi=∑ei∈PjFjfor1≤i≤m.Proof 2.
Directly from Theorem1 and Lemma 1.
Obviously, Theorem2 is an improvement to Lemma 1 in view of the tighter capacity constraints imposed on ei (corresponding to conditions (7) and (8)), and it is the foundation of the designed algorithm for solving d-minimal paths in this paper.


## 4. An Algorithm for Solvingd-Minimal Paths

### 4.1. The Developed Algorithm

Like the algorithms in [14–16, 22], it is assumed that all minimal paths are known in advance. Actually, there have already been many efficient methods to find minimal paths, such as Chen and Lin [25], Bai et al. [26], and Yeh [27]. The proposed algorithm for solving d-minimal paths consists of three steps as in Algorithm 1.Algorithm 1
Input: A stochastic-flow network GV,E,W with demand level d.
Output: All d-minimal paths.
Step 0. Compute min CPj,d for 1≤j≤p, min Wi,d and Li=max0,d–MW0i for 1≤i≤m.
Step 1. Use the enumeration algorithm to solve all of the feasible flow vectors satisfying conditions (6)-(8), and transform each feasible flow vector into its corresponding d-minimal path candidate by Equation (9). Suppose x1,x2,…,xλ are all the obtained d-minimal path candidates.
Step 2. Use the comparison method to check whether xi1≤i≤λ is a d-minimal path or not.
(2.1) I =Φ (stores the index of each non d-minimal path after checking).
(2.2) Fori = 1 to λ and i∉I.
(2.3) Forj = 2 to λ and j∉I.
(2.4) Ifxj < xi, xi is not a d-minimal path, I = I ⋃ i and go to (2.7); if xj ≥ xi, xj is not a d-minimal path, I = I ⋃ j and go to (2.7).
(2.5)j = j + 1.
(2.6)xi is a d-minimal path.
(2.7)i = i + 1.Step 0 is a preprocessing step for computing lower and upper bounds in conditions (7) and (8). Step 1 is the most important step for solving d-minimal path candidates. As the fast enumeration method proposed by Chen [28] has proven to be more efficient than the traditional enumeration method, it is suggested to solve all of the feasible flow vectors in Step 1. The detailed procedure of the fast enumeration method can be found in [22]. Step 2 is to check whether the derived d-minimal path candidates are indeed d-minimal paths. The time complexity of every step is discussed as follows. In Step 0, it takes Omp time and Om time to compute all minCPj,d1≤j≤p and all minWi,d1≤i≤m, respectively. Computing all Li=max0,d–MW0i 1≤i≤m requires Omn3 time. For a general connected network, Op=O2n [29] means Omn3<Omp; thus, Step 0 totally requires Omp time. According to Chen and Lin [22], it takes O∏i=1πqk time to generate all feasible flow vectors where π is the number of groups of alternative orders arranged by the fast enumeration method and qk is the total number of enumerations in the ith group. It takes Omλp to transform all feasible flow vectors into d-minimal path candidates where λ is the number of d-minimal paths. As a result, the time complexity of Step 1 for solving d-minimal path candidates is O∏i=1πqk+Omλp. Step 2 requires Omλ2 time to check d-minimal path candidates in the worst case.To demonstrate the advantage of the proposed algorithm, there is a need to compare with the existing methods. Given that the method recently reported by Chen and Lin [22] is considered to be efficient in solving d-minimal paths, we compare the proposed algorithm with it. Of particular note is that the step of solving d-minimal path candidates is the primary difference between the proposed algorithm and the method by Chen and Lin, i.e., the proposed algorithm and the method by Chen and Lin utilize Theorem 2 and Lemma 1, respectively, to solve d-minimal path candidates. Also, the burden of solving d-minimal path candidates is the bottleneck of the d-minimal path algorithm [22]. Therefore, we compare both algorithms in terms of the time complexity of solving d-minimal path candidates. According to the solution procedure of the fast enumeration method [22, 28], the number of enumerations qk implemented by the proposed algorithm is dependent on the capacity ranges in conditions (7) and (8), whereas the number of enumerations qk∗ implemented by Chen and Lin’s method is dependent on the capacity ranges in conditions (3) and (4). Because the capacity ranges in conditions (7) and (8) are smaller or equal to the ones in conditions (3) and (4), we have qk≤qk∗, which means O∏i=1πqk≤O∏i=1πqk∗ holds. Consequently, the time complexity of the proposed algorithm is upper bounded by that of Chen and Lin’s method [22] in solving d-minimal path candidates.


### 4.2. An Illustrative Example

The network in Figure1 is adopted to demonstrate how the proposed algorithm works to compute the network reliability. Figure 1 has four minimal paths from s to t: P1=e1,e2,P2=e1,e3,e5,P3=e4,e5,P4=e4,e3,e2. Given the demand level d=3, the reliability R3, i.e., the probability of 3 units of commodity demand being successfully delivered from s to t, can be calculated using all 3-minimal paths that are obtained as follows.Step 0.
minCP1,d=min2,3=2, similarly, minCP2,d=1, minCP3,d=2, minCP4,d=1; minW1,d=min3,3=3, similarly, minW2,d=2, minW3,d=1, minW4,d=2, minW5,d=2; L1=max0,d–MW0i=max0,1=1, similarly, L2=1, L3=0, L4=0, L5=1.Step 1.
Use the fast enumeration method to solve all of the feasible flow vectors satisfying the following conditions:(10)F1+F2+F3+F4=3,(11)0≤F1≤2,(12)0≤F2≤1,(13)0≤F3≤2,(14)0≤F4≤1,(15)1≤F1+F2≤3,(16)1≤F1+F4≤2,(17)0≤F2+F4≤1,(18)0≤F3+F4≤2,(19)1≤F2+F3≤2.And the solution results areF1=1,0,1,1, F2=1,0,2,0, F3=1,1,1,0, F4=2,0,1,0, and F5=2,1,0,0. Therefore, by (9), the corresponding d-minimal path candidates are x1=1,2,1,2,1, x2=1,1,0,2,2, x3=2,1,1,1,2, x4=2,2,0,1,1, and x5=3,2,1,0,1.Step 2.
Use the comparison method to check whetherxi1≤i≤4 is a d-minimal path or not.
(2.1)I=Φ.
(2.2)i=1 and i∉I.
(2.3)j=2 and j∉I.
(2.4)x2=1,1,0,2,2<x1=1,2,1,2,1 is false, x2≥x1 is false.
(2.5)j=3 and j∉I.Finally, there are five 3-minimal paths obtained as follows:x1=1,2,1,2,1, x2=1,1,0,2,2, x3=2,1,1,1,2, x4=2,2,0,1,1, and x5=3,2,1,0,1. Let B1=x∣x≥x1, B2=x∣x≥x2, B3=x∣x≥x3, B4=x∣x≥x4, and B5=x∣x≥x5, then it is trivial to derive R3=0.6674025 by Equation (1).Furthermore, it is calculated that the proposed algorithm needs to perform 21 enumerations during the solution of 3-minimal path candidates, i.e., solving conditions (10)–(19). By contrast, if the method by Chen and Lin [22] is used to solve 3-minimal path candidates of the network, it needs to perform a total of 28 enumerations. Hence, the suggested algorithm implements a smaller number of enumerations in comparison with Chen and Lin’s method, as already illustrated by theoretical analyses in Section 3.1.


### 4.3. A Numerical Example

In this section, the efficiency of the proposed algorithm is further explored through a numerical example. As stated previously, the major difference between the proposed algorithm and the method by Chen and Lin [22] is the step for solving d-minimal path candidates; therefore, it is only necessary to compare both algorithms in terms of the efficiency of solving d-minimal path candidates. Both algorithms coded in a MATLAB program run on a PC with Intel (R) Core (TM) i5-3210M 2.50 GHz CPU.A medium-sized network shown in Figure2 is adopted to conduct numerical experiments. The capacities of all arcs in Figure 2 are set to 8, then the largest network capacity is D=16. All of the d-minimal path candidates corresponding to eight demand levels ranging from d=9 to d=16 are solved. We focus on the required computational time for solving d-minimal path candidates for each demand level. The overall results are summarized in Table 2. From Table 2, it can be observed that the suggested algorithm displays an advantage over the method by Chen and Lin [22]. Meanwhile, note that the efficiency difference of both algorithms is negligible when demand level d ranges from d=9 to d=12, but it becomes prominent when the demand level d is above 12.Figure 2
A benchmark network for the numerical example.Table 2
Computational times of both algorithms.
Demand leveld
9
10
11
12
13
14
15
16
Average
Tnew
18.893
19.728
19.878
18.597
15.396
10.996
6.716
3.622
14.228
TCL
18.964
19.802
20.445
19.173
20.442
19.714
18.781
18.216
19.442
Note:TCL and Tnew are the computational times (in CPU seconds) consumed by Chen and Lin’s algorithm [22] and the proposed algorithm, respectively.


## 4.1. The Developed Algorithm

Like the algorithms in [14–16, 22], it is assumed that all minimal paths are known in advance. Actually, there have already been many efficient methods to find minimal paths, such as Chen and Lin [25], Bai et al. [26], and Yeh [27]. The proposed algorithm for solving d-minimal paths consists of three steps as in Algorithm 1.Algorithm 1
Input: A stochastic-flow network GV,E,W with demand level d.
Output: All d-minimal paths.
Step 0. Compute min CPj,d for 1≤j≤p, min Wi,d and Li=max0,d–MW0i for 1≤i≤m.
Step 1. Use the enumeration algorithm to solve all of the feasible flow vectors satisfying conditions (6)-(8), and transform each feasible flow vector into its corresponding d-minimal path candidate by Equation (9). Suppose x1,x2,…,xλ are all the obtained d-minimal path candidates.
Step 2. Use the comparison method to check whether xi1≤i≤λ is a d-minimal path or not.
(2.1) I =Φ (stores the index of each non d-minimal path after checking).
(2.2) Fori = 1 to λ and i∉I.
(2.3) Forj = 2 to λ and j∉I.
(2.4) Ifxj < xi, xi is not a d-minimal path, I = I ⋃ i and go to (2.7); if xj ≥ xi, xj is not a d-minimal path, I = I ⋃ j and go to (2.7).
(2.5)j = j + 1.
(2.6)xi is a d-minimal path.
(2.7)i = i + 1.Step 0 is a preprocessing step for computing lower and upper bounds in conditions (7) and (8). Step 1 is the most important step for solving d-minimal path candidates. As the fast enumeration method proposed by Chen [28] has proven to be more efficient than the traditional enumeration method, it is suggested to solve all of the feasible flow vectors in Step 1. The detailed procedure of the fast enumeration method can be found in [22]. Step 2 is to check whether the derived d-minimal path candidates are indeed d-minimal paths. The time complexity of every step is discussed as follows. In Step 0, it takes Omp time and Om time to compute all minCPj,d1≤j≤p and all minWi,d1≤i≤m, respectively. Computing all Li=max0,d–MW0i 1≤i≤m requires Omn3 time. For a general connected network, Op=O2n [29] means Omn3<Omp; thus, Step 0 totally requires Omp time. According to Chen and Lin [22], it takes O∏i=1πqk time to generate all feasible flow vectors where π is the number of groups of alternative orders arranged by the fast enumeration method and qk is the total number of enumerations in the ith group. It takes Omλp to transform all feasible flow vectors into d-minimal path candidates where λ is the number of d-minimal paths. As a result, the time complexity of Step 1 for solving d-minimal path candidates is O∏i=1πqk+Omλp. Step 2 requires Omλ2 time to check d-minimal path candidates in the worst case.To demonstrate the advantage of the proposed algorithm, there is a need to compare with the existing methods. Given that the method recently reported by Chen and Lin [22] is considered to be efficient in solving d-minimal paths, we compare the proposed algorithm with it. Of particular note is that the step of solving d-minimal path candidates is the primary difference between the proposed algorithm and the method by Chen and Lin, i.e., the proposed algorithm and the method by Chen and Lin utilize Theorem 2 and Lemma 1, respectively, to solve d-minimal path candidates. Also, the burden of solving d-minimal path candidates is the bottleneck of the d-minimal path algorithm [22]. Therefore, we compare both algorithms in terms of the time complexity of solving d-minimal path candidates. According to the solution procedure of the fast enumeration method [22, 28], the number of enumerations qk implemented by the proposed algorithm is dependent on the capacity ranges in conditions (7) and (8), whereas the number of enumerations qk∗ implemented by Chen and Lin’s method is dependent on the capacity ranges in conditions (3) and (4). Because the capacity ranges in conditions (7) and (8) are smaller or equal to the ones in conditions (3) and (4), we have qk≤qk∗, which means O∏i=1πqk≤O∏i=1πqk∗ holds. Consequently, the time complexity of the proposed algorithm is upper bounded by that of Chen and Lin’s method [22] in solving d-minimal path candidates.


## 4.2. An Illustrative Example

The network in Figure1 is adopted to demonstrate how the proposed algorithm works to compute the network reliability. Figure 1 has four minimal paths from s to t: P1=e1,e2,P2=e1,e3,e5,P3=e4,e5,P4=e4,e3,e2. Given the demand level d=3, the reliability R3, i.e., the probability of 3 units of commodity demand being successfully delivered from s to t, can be calculated using all 3-minimal paths that are obtained as follows.Step 0.
minCP1,d=min2,3=2, similarly, minCP2,d=1, minCP3,d=2, minCP4,d=1; minW1,d=min3,3=3, similarly, minW2,d=2, minW3,d=1, minW4,d=2, minW5,d=2; L1=max0,d–MW0i=max0,1=1, similarly, L2=1, L3=0, L4=0, L5=1.Step 1.
Use the fast enumeration method to solve all of the feasible flow vectors satisfying the following conditions:(10)F1+F2+F3+F4=3,(11)0≤F1≤2,(12)0≤F2≤1,(13)0≤F3≤2,(14)0≤F4≤1,(15)1≤F1+F2≤3,(16)1≤F1+F4≤2,(17)0≤F2+F4≤1,(18)0≤F3+F4≤2,(19)1≤F2+F3≤2.And the solution results areF1=1,0,1,1, F2=1,0,2,0, F3=1,1,1,0, F4=2,0,1,0, and F5=2,1,0,0. Therefore, by (9), the corresponding d-minimal path candidates are x1=1,2,1,2,1, x2=1,1,0,2,2, x3=2,1,1,1,2, x4=2,2,0,1,1, and x5=3,2,1,0,1.Step 2.
Use the comparison method to check whetherxi1≤i≤4 is a d-minimal path or not.
(2.1)I=Φ.
(2.2)i=1 and i∉I.
(2.3)j=2 and j∉I.
(2.4)x2=1,1,0,2,2<x1=1,2,1,2,1 is false, x2≥x1 is false.
(2.5)j=3 and j∉I.Finally, there are five 3-minimal paths obtained as follows:x1=1,2,1,2,1, x2=1,1,0,2,2, x3=2,1,1,1,2, x4=2,2,0,1,1, and x5=3,2,1,0,1. Let B1=x∣x≥x1, B2=x∣x≥x2, B3=x∣x≥x3, B4=x∣x≥x4, and B5=x∣x≥x5, then it is trivial to derive R3=0.6674025 by Equation (1).Furthermore, it is calculated that the proposed algorithm needs to perform 21 enumerations during the solution of 3-minimal path candidates, i.e., solving conditions (10)–(19). By contrast, if the method by Chen and Lin [22] is used to solve 3-minimal path candidates of the network, it needs to perform a total of 28 enumerations. Hence, the suggested algorithm implements a smaller number of enumerations in comparison with Chen and Lin’s method, as already illustrated by theoretical analyses in Section 3.1.


## 4.3. A Numerical Example

In this section, the efficiency of the proposed algorithm is further explored through a numerical example. As stated previously, the major difference between the proposed algorithm and the method by Chen and Lin [22] is the step for solving d-minimal path candidates; therefore, it is only necessary to compare both algorithms in terms of the efficiency of solving d-minimal path candidates. Both algorithms coded in a MATLAB program run on a PC with Intel (R) Core (TM) i5-3210M 2.50 GHz CPU.A medium-sized network shown in Figure2 is adopted to conduct numerical experiments. The capacities of all arcs in Figure 2 are set to 8, then the largest network capacity is D=16. All of the d-minimal path candidates corresponding to eight demand levels ranging from d=9 to d=16 are solved. We focus on the required computational time for solving d-minimal path candidates for each demand level. The overall results are summarized in Table 2. From Table 2, it can be observed that the suggested algorithm displays an advantage over the method by Chen and Lin [22]. Meanwhile, note that the efficiency difference of both algorithms is negligible when demand level d ranges from d=9 to d=12, but it becomes prominent when the demand level d is above 12.Figure 2
A benchmark network for the numerical example.Table 2
Computational times of both algorithms.
Demand leveld
9
10
11
12
13
14
15
16
Average
Tnew
18.893
19.728
19.878
18.597
15.396
10.996
6.716
3.622
14.228
TCL
18.964
19.802
20.445
19.173
20.442
19.714
18.781
18.216
19.442
Note:TCL and Tnew are the computational times (in CPU seconds) consumed by Chen and Lin’s algorithm [22] and the proposed algorithm, respectively.


## 5. Expected Capacity

It is evident that network reliability is a probabilistic performance index for characterizing the capability of a freight network to ensure the accurate delivery of required quantity of commodity from the source to the destination. In this section, a new performance indicator will be presented to evaluate a freight network. Because the network capacity of a freight network is a random variable whose value ranges from the smallest capacity 0 to the largest capacityMW, i.e., 0,1,…,MW, we define a concept of expected capacity from the perspective of mathematical expectation to measure the service performance of the freight network. Expected capacity notated as EC represents the average network capacity level and is defined as follows:
(20)EC=∑d=1DPrx∣Mx=d×d,where D=MW is the largest network capacity and Prx∣Mx=d is the probability that network capacity is equal to d. Note that d=0 does not contribute to expected capacity, so the value of d ranges from 1 to D.Obviously, computingPrx∣Mx=d is the key to obtaining EC. Given the demand level d, reliability index Rd is the probability that network capacity is greater than or equal to d, i.e., Rd=Prx∣Mx≥d; hence, a clear relationship between expected capacity and network reliability can be readily determined by the following theorem.Theorem 3.
The expected capacity can be calculated asEC=∑d=1DRd−Rd+1×d.Proof 3.
(21)Prx∣Mx=d=Prx∣Mx≥d–Prx∣Mx>d=Prx∣Mx≥d–Prx∣Mx≥d+1=Rd–Rd+1.
Thus,(22)EC=∑d=1DPrx∣Mx=d×d=∑d=1DRd−Rd+1×d.
In addition, it is noted that whend=D,Rd+1=RD+1=0. Theorem 3 indicates that calculating EC is equivalent to the computation of Rd for all possible d values. Hence, the proposed d-minimal path algorithm is required to run multiple times for obtaining EC.


## 6. A Case Study of a Coal Delivery Network

Network reliability and expected capacity are two performance indicators for measuring the level of service of a freight network in a complex environment. In this section, we take a practical coal delivery network shown in Figure3 as a case study to demonstrate the implications of both network reliability and expected capacity.Figure 3
The coal delivery network from Datong to Lianyungang.


### 6.1. Performance Assessment in terms of Network Reliability

It is well known that coal is the largest source of energy in China and is used to generate a significant chunk of the nation’s electricity. Every year, thousands of million tons of coal is transported from the producing area to the consumption area, so the efficient and safe movement of coal over space plays an extremely important part in sustaining the national economic development. Datong City in Shanxi Province that produces about 400 million tons of coal every year is a famous coal-producing area in China, and a large proportion of the produced coal is transported and sold all over the country. A producer owning a coal enterprise located at Datong City produces thermal coal. Thermal coal is usually used in power industry to generate electricity. Owing to price advantage, the producer has been one of the chief thermal coal suppliers for many Chinese power enterprises. One of its customers is a large power enterprise located at Lianyungang City in Jiangsu Province that is one of the richest provinces in China. Figure3 describes the coal delivery network from Datong to Lianyungang, in which the coal commodity can pass through several transfer centers in different cities.Coal is transported by train or ship. The capacity data on routes derived from the database of logistics service providers are provided in Table3. That is, each route has multiple possible carrying capacities, such as 0,1,…,5 (unit: 104 tons), following a given probability distribution. Supposing that the amount of coal ordered by the power enterprise at Lianyungang is 6 × 104 tons, i.e., demand level d=6 units of coal. The proposed algorithm is utilized to evaluate the network reliability R6.Table 3
Capacity data of each arc (route) in Figure3.
Routeei
Available capacity (unit: 104 tons)
0
1
2
3
4
5
Probability
e1
0.005
0.012
0.017
0.021
0.032
0.913
e2
0.011
0.043
0.946
—
—
—
e3
0.005
0.011
0.023
0.039
0.922
e4
0.012
0.029
0.959
—
—
e5
0.011
0.018
0.025
0.946
—
e6
0.012
0.026
0.034
0.928
—
e7
0.007
0.019
0.974
—
—
e8
0.006
0.015
0.979
—
—
e9
0.011
0.043
0.946
—
—
e10
0.008
0.013
0.026
0.953
—
e11
0.012
0.046
0.942
—
—
e12
0.006
0.019
0.034
0.941
—
e13
0.007
0.012
0.029
0.952
—
—
e14
0.009
0.016
0.029
0.035
0.911
e15
0.006
0.011
0.015
0.022
0.034
0.912First, a total number of 41 6-minimal paths are obtained by using the proposed algorithm. Then, based on all 6-minimal paths and (1), the value of the performance index R6 is calculated as 0.820714. Therefore, the probability that the freight network in Figure 3 can successfully deliver 6 × 104 tons of coal commodities from Datong to Lianyungang is 0.820714. Undoubtedly, the reliability value 0.820714 reveals valuable knowledge on the operational performance of the delivery network and can be regarded as a decision criterion. For example, if the value 0.820714 is below the expectation of the manager, it means that the service performance of the network does not meet the requirement; otherwise, the service performance of the network is acceptable.


### 6.2. Performance Assessment in terms of Expected Capacity

By Equation (22), it needs to compute network reliabilities at different demand levels in order to obtain expected capacity EC. Obviously, the largest network capacity is D=7. Thus, the proposed algorithm is utilized to compute network reliabilities at different demand levels from 1 to 7. The results are summarized in Table 4. Moreover, the reliability difference between two neighboring demand levels is calculated and adopted to compute EC. The final computational results are also presented in Table 4 by which we make the following observations:
(1)
As expected, network reliability declines as the demand leveld rises. In addition, the reliability difference between two neighboring demand levels Rd–Rd+1 increases as the demand level d increases
(2)
For the demand leveld=6, it is noteworthy that the expected capacity EC=6.312942 is larger than demand level d=6, which means the service performance of the network is relatively desirable from the perspective of the average network capacity levelTable 4
Network reliabilities at different demand levels and expected capacity.
Demand leveld
1
2
3
4
5
6
7
Rd
0.999721
0.998355
0.985891
0.960840
0.919381
0.820714
0.628040
Rd−Rd+1
0.001366
0.012464
0.025051
0.041459
0.098667
0.192674
0.628040
Rd−Rd+1×d
0.001366
0.024928
0.075153
0.165836
0.493335
1.156044
4.39628
Expected capacity
EC=6.312942In summary, both network reliability and expected capacity can be adopted to assess the performance level of a freight network from different aspects, which provides managers useful tools for making reasonable evaluation on the operational state of their freight network.


## 6.1. Performance Assessment in terms of Network Reliability

It is well known that coal is the largest source of energy in China and is used to generate a significant chunk of the nation’s electricity. Every year, thousands of million tons of coal is transported from the producing area to the consumption area, so the efficient and safe movement of coal over space plays an extremely important part in sustaining the national economic development. Datong City in Shanxi Province that produces about 400 million tons of coal every year is a famous coal-producing area in China, and a large proportion of the produced coal is transported and sold all over the country. A producer owning a coal enterprise located at Datong City produces thermal coal. Thermal coal is usually used in power industry to generate electricity. Owing to price advantage, the producer has been one of the chief thermal coal suppliers for many Chinese power enterprises. One of its customers is a large power enterprise located at Lianyungang City in Jiangsu Province that is one of the richest provinces in China. Figure3 describes the coal delivery network from Datong to Lianyungang, in which the coal commodity can pass through several transfer centers in different cities.Coal is transported by train or ship. The capacity data on routes derived from the database of logistics service providers are provided in Table3. That is, each route has multiple possible carrying capacities, such as 0,1,…,5 (unit: 104 tons), following a given probability distribution. Supposing that the amount of coal ordered by the power enterprise at Lianyungang is 6 × 104 tons, i.e., demand level d=6 units of coal. The proposed algorithm is utilized to evaluate the network reliability R6.Table 3
Capacity data of each arc (route) in Figure3.
Routeei
Available capacity (unit: 104 tons)
0
1
2
3
4
5
Probability
e1
0.005
0.012
0.017
0.021
0.032
0.913
e2
0.011
0.043
0.946
—
—
—
e3
0.005
0.011
0.023
0.039
0.922
e4
0.012
0.029
0.959
—
—
e5
0.011
0.018
0.025
0.946
—
e6
0.012
0.026
0.034
0.928
—
e7
0.007
0.019
0.974
—
—
e8
0.006
0.015
0.979
—
—
e9
0.011
0.043
0.946
—
—
e10
0.008
0.013
0.026
0.953
—
e11
0.012
0.046
0.942
—
—
e12
0.006
0.019
0.034
0.941
—
e13
0.007
0.012
0.029
0.952
—
—
e14
0.009
0.016
0.029
0.035
0.911
e15
0.006
0.011
0.015
0.022
0.034
0.912First, a total number of 41 6-minimal paths are obtained by using the proposed algorithm. Then, based on all 6-minimal paths and (1), the value of the performance index R6 is calculated as 0.820714. Therefore, the probability that the freight network in Figure 3 can successfully deliver 6 × 104 tons of coal commodities from Datong to Lianyungang is 0.820714. Undoubtedly, the reliability value 0.820714 reveals valuable knowledge on the operational performance of the delivery network and can be regarded as a decision criterion. For example, if the value 0.820714 is below the expectation of the manager, it means that the service performance of the network does not meet the requirement; otherwise, the service performance of the network is acceptable.


## 6.2. Performance Assessment in terms of Expected Capacity

By Equation (22), it needs to compute network reliabilities at different demand levels in order to obtain expected capacity EC. Obviously, the largest network capacity is D=7. Thus, the proposed algorithm is utilized to compute network reliabilities at different demand levels from 1 to 7. The results are summarized in Table 4. Moreover, the reliability difference between two neighboring demand levels is calculated and adopted to compute EC. The final computational results are also presented in Table 4 by which we make the following observations:
(1)
As expected, network reliability declines as the demand leveld rises. In addition, the reliability difference between two neighboring demand levels Rd–Rd+1 increases as the demand level d increases
(2)
For the demand leveld=6, it is noteworthy that the expected capacity EC=6.312942 is larger than demand level d=6, which means the service performance of the network is relatively desirable from the perspective of the average network capacity levelTable 4
Network reliabilities at different demand levels and expected capacity.
Demand leveld
1
2
3
4
5
6
7
Rd
0.999721
0.998355
0.985891
0.960840
0.919381
0.820714
0.628040
Rd−Rd+1
0.001366
0.012464
0.025051
0.041459
0.098667
0.192674
0.628040
Rd−Rd+1×d
0.001366
0.024928
0.075153
0.165836
0.493335
1.156044
4.39628
Expected capacity
EC=6.312942In summary, both network reliability and expected capacity can be adopted to assess the performance level of a freight network from different aspects, which provides managers useful tools for making reasonable evaluation on the operational state of their freight network.


## 7. Conclusions

Reliability evaluation assists supervisors in understanding network service performance. This paper is devoted to performance assessment of a freight network in the light of reliability analysis. On one hand, this paper presents an efficientd-minimal path–based algorithm to evaluate the freight network reliability that at least d units of commodity demand can be successfully delivered from the source to the destination. An improved model is constructed by redefining capacity bounds of arcs and minimal paths to enhance the efficiency of solving d-minimal paths. On the other hand, this paper puts forward a new concept of expected capacity to assess the service performance of a freight network. In addition, a practical case study regarding a coal delivery network is provided to demonstrate the implications of both network reliability and expected capacity.For future research, there is still potential for developing a new reliability model to meet practical needs. For example, we only consider the transmission of a single type of commodity in the freight network, and yet, it is much more valuable to assess the performance of multicommodity freight networks in which multiple types of cargoes are delivered from the source to the destination simultaneously.



---

*Source: 9142542-2018-09-18.xml*