# Delivery Time Reliability Model of Logistics Network

Authors: Liusan Wu; Qingmei Tan; Yuehui Zhang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Natural disasters like earthquake and flood will surely destroy the existing traffic network, usually accompanied by delivery delay or even network collapse. A logistics-network-related delivery time reliability model defined by a shortest-time entropy is proposed as a means to estimate the actual delivery time reliability. The less the entropy is, the stronger the delivery time reliability remains, and vice versa. The shortest delivery time is computed separately based on two different assumptions. If a path is concerned without capacity restriction, the shortest delivery time is positively related to the length of the shortest path, and if a path is concerned with capacity restriction, a minimax programming model is built to figure up the shortest delivery time. Finally, an example is utilized to confirm the validity and practicality of the proposed approach.


---

## Body

## 1. Introduction

The “graph theory,” a mathematical approach born as soon as Ola solved “Seven Bridges” in 1736, has laid a solid foundation for the development of network theories. In several decades, with a variety of models such as random network, small-world network, and scale-free network proposed, more attention has been paid to network study [1–3]. As well known, networks exist in every corner of human’s real life, for example, traffic network, communication network, and logistics network. In recent years, many emergency events (such as New York’s Power Outage in 2003, Wenchuan Earthquake in 2008) occur frequently in the world wide, which had caused enormous economic loss and casualties. Since materials and information are transported and transmitted via networks, it is of vital importance to deliver them to the right demand point as soon as possible when an unexpected event occurs for any delay may result in loss of or damage to people’s lives and properties. In this sense, the study or research dealing with the reliability of networks is significant in theory and in practice.The network reliability may be defined as an ability or probability that a network system has to completely fulfill customer-tailored communications tasks during the stipulated successive operation procedure. Currently, the reliability-network-related research mainly concentrates on the invulnerability of complex networks, that is, their endurance to attacks [4–8]. The literature concerning network reliability has prospered, ranging from the network connectivity reliability, network capacity reliability, to network performance reliability, and the like [9]. Among them, the network connectivity reliability merely considers network topology and introduces the “probability of connectivity achieved by network” as a reliability measurement criterion; the network capacity reliability adopts the “probability of existence of paths that satisfies a certain flow demand” as the measurement standard by considering the capacity of links and nodes within the network; the network performance reliability refers to the impact of network performance’s dynamic change on its reliability, mainly characterized by the “probability of certain performance parameters not exceeding the stipulated threshold.”Entropy was originally introduced as a thermodynamic concept and widely used to measure an unordered system. Then entropy had begun to draw much attention in the field of complex systems research since it served as a physical device capable of describing the structure of a complex system. From the macroscopic viewpoint, entropy is reckoned as a metric of energy distribution uniformity in a system, and it is able to indicate whether the current situation is stable as well as the system’s change trend. The more uniform the energy distribution is, the greater the entropy achieves. Otherwise, the smaller the entropy achieves. Qiu and her team has brought entropy in management decision-making procedure and then proposed the management entropy theory [10–12]. In recent years, many scholars use generalized entropy to describe the reliability of a network [13–15]. Based on previous research results, this paper puts forward the concept of shortest delivery time entropy involved in logistics networks. Moreover, the entropy is used to represent delivery time reliability of a logistics network, featured by a negative relationship with the shortest delivery time reliability.


## 2. Shortest Delivery Time Entropy of Logistics Networks

### 2.1. Model Assumptions and Symbols Description

The assumptions are made as follows(1)
Vehicles move at a fixed speed when delivering goods and materials.(2)
Vehicles are infinite in quantity, of which each delivers once and departs from the present network immediately to save time.(3)
The materials are allowed to be mixed and loaded, with the total weight considered, regardless of their classification.(4)
The time of loading and unloading is ignored.For a directed networkG=(V,E,C,D) with n nodes involved, V={vi∣i=1,2,…,n} is the vertices set, and E={eij} is arcs set. Additionally, cij denotes the capacity restriction of arc eij,  dij denotes the length of arc eij, f denotes the length of the shortest path for G, fij denotes the length of the shortest path when eij is attacked and fails, q denotes the quantity of required materials, v denotes the vehicle’s traveling speed, and G′ denotes the impaired network when eij is attacked and fails.


### 2.2. Shortest Delivery Time Entropy of Logistics Network

When the path ofvivj is attacked and becomes invalid, our research will focus on two timing points as follows:(1)
t0, the shortest time of delivering materials on condition that all paths are in good condition;(2)
tij, the shortest time of delivering materials on condition that eij is attacked and loses effectiveness.Under the circumstances,t0/tij is utilized to describe the network reliability in case that the path vivj suffers attack and thus fails. Definitely, the longer the length of the arc, the higher the probability of the arc being invalid after an attack. Thus, the probability may be expressed by dij/∑vivj∈Edij. As we all know, the entropy can be applied to illustrate a system’s reliability. Therefore, we put forward the concept of shortest delivery time entropy of logistics network based on the network’s maximum flow entropy and shortest path entropy, expressed by
(1)H=-∑vivj∈Edij∑vivj∈Edijlnt0tij.
Seen from the formula, the shortest delivery time entropy of logistics network is generalized entropy; so the value of H may be very large and even can go to infinite. The smaller the value of H, the stronger the delivery time reliability of the logistics network; otherwise, the weaker the delivery time reliability of the logistics network.


### 2.3. Shortest Delivery Time Entropy of Logistics Network without Flow Restriction

When the path is unrestricted by flow capacity, the shortest delivery time is positively related to the shortest path length. Referring to its definitions in previous literature, it is available(2)t0=fv,tij=fijv.
Substituting the above equation into the formula of shortest delivery time entropy of logistics network, we get the following:
(3)H=-∑vivj∈Edij∑vivj∈Edijlnt0tij=-∑vivj∈Edij∑vivj∈Edijlnf/vfij/v=-∑vivj∈Edij∑vivj∈Edijlnffij.
Obviously, the smaller the value of H, the stronger the delivery time reliability of logistics network. However, the larger the value of H, the weaker the delivery time reliability of logistics network.


### 2.4. Shortest Delivery Time Entropy of Logistics Network with Flow Restriction

When the path is restricted by flow capacity, with assumption of totalm different paths departing from v1 to vn to deliver goods and materials, the kth path is denoted by pk, and the flow of pk from eij is denoted by Cijk. Because pk may not pass eij, we introduce δij as
(4)δij={0pknotpasseij1pkpasseij,
where the flow of pk is denoted by Ck, then
(5)Cijk=δij·Ck.
The flow of each path may not be unique, Example 1 will clarify it.Example 1.
In order to illustrate the fact that the flow of each path may not be unique, we design an original delivery network (see Figure1), where each point pair (x,y) of the given arc means the length of x and the capacity restriction of y, respectively.Figure 1
The original delivery network.p
1 means the path v1→v2→v3→v4 and p2 means the path v1→v3→v4. Therefore,
(6)0≤C1≤20≤C2≤20≤C1+C2≤3.
So C1 and C2 may not be unique.Assuming thatTk  is the length of  pk and  Rk   is the delivery times of the k-th path. Since the flow of arc eij assigned to all m paths is not allowed to exceed the capacity restriction of arc eij, we have the following:
(7)∑k=1mCijk≤cij.
Besides, the total number of the materials delivered is not less than q, thus
(8)∑k=1m(Ck×Rk)≥q.
The total time spent in delivering materials is as follows
(9)max{Tkv×Rk}.
Accordingly, when max{(Tk/v)×Rk} reaches minimum value, the time spent on materials delivery via the network is the shortest, thereby we have the following minimax programming model:
(10)t0=minmax{Tkv×Rk}s.t.∑k=1m(Ck×Rk)≥q∑k=1mCijk≤cij,Rk∈N.
At present, there emerged a lot of algorithms solving minimax models, which is unnecessarily repeated here [16–20].Note that when arceij is attacked and fails, other nodes and arcs constitute a new network  G′. By using model (10), we can obtain tij. Similarly, by substituting t0 and tij into the formula of shortest delivery time entropy of  logistics network, we get the time reliability of delivering materials. The smaller the value of H, the stronger the delivery time reliability of the logistics network; otherwise, the larger the value of H, the weaker the delivery time reliability of the logistics network.


## 2.1. Model Assumptions and Symbols Description

The assumptions are made as follows(1)
Vehicles move at a fixed speed when delivering goods and materials.(2)
Vehicles are infinite in quantity, of which each delivers once and departs from the present network immediately to save time.(3)
The materials are allowed to be mixed and loaded, with the total weight considered, regardless of their classification.(4)
The time of loading and unloading is ignored.For a directed networkG=(V,E,C,D) with n nodes involved, V={vi∣i=1,2,…,n} is the vertices set, and E={eij} is arcs set. Additionally, cij denotes the capacity restriction of arc eij,  dij denotes the length of arc eij, f denotes the length of the shortest path for G, fij denotes the length of the shortest path when eij is attacked and fails, q denotes the quantity of required materials, v denotes the vehicle’s traveling speed, and G′ denotes the impaired network when eij is attacked and fails.


## 2.2. Shortest Delivery Time Entropy of Logistics Network

When the path ofvivj is attacked and becomes invalid, our research will focus on two timing points as follows:(1)
t0, the shortest time of delivering materials on condition that all paths are in good condition;(2)
tij, the shortest time of delivering materials on condition that eij is attacked and loses effectiveness.Under the circumstances,t0/tij is utilized to describe the network reliability in case that the path vivj suffers attack and thus fails. Definitely, the longer the length of the arc, the higher the probability of the arc being invalid after an attack. Thus, the probability may be expressed by dij/∑vivj∈Edij. As we all know, the entropy can be applied to illustrate a system’s reliability. Therefore, we put forward the concept of shortest delivery time entropy of logistics network based on the network’s maximum flow entropy and shortest path entropy, expressed by
(1)H=-∑vivj∈Edij∑vivj∈Edijlnt0tij.
Seen from the formula, the shortest delivery time entropy of logistics network is generalized entropy; so the value of H may be very large and even can go to infinite. The smaller the value of H, the stronger the delivery time reliability of the logistics network; otherwise, the weaker the delivery time reliability of the logistics network.


## 2.3. Shortest Delivery Time Entropy of Logistics Network without Flow Restriction

When the path is unrestricted by flow capacity, the shortest delivery time is positively related to the shortest path length. Referring to its definitions in previous literature, it is available(2)t0=fv,tij=fijv.
Substituting the above equation into the formula of shortest delivery time entropy of logistics network, we get the following:
(3)H=-∑vivj∈Edij∑vivj∈Edijlnt0tij=-∑vivj∈Edij∑vivj∈Edijlnf/vfij/v=-∑vivj∈Edij∑vivj∈Edijlnffij.
Obviously, the smaller the value of H, the stronger the delivery time reliability of logistics network. However, the larger the value of H, the weaker the delivery time reliability of logistics network.


## 2.4. Shortest Delivery Time Entropy of Logistics Network with Flow Restriction

When the path is restricted by flow capacity, with assumption of totalm different paths departing from v1 to vn to deliver goods and materials, the kth path is denoted by pk, and the flow of pk from eij is denoted by Cijk. Because pk may not pass eij, we introduce δij as
(4)δij={0pknotpasseij1pkpasseij,
where the flow of pk is denoted by Ck, then
(5)Cijk=δij·Ck.
The flow of each path may not be unique, Example 1 will clarify it.Example 1.
In order to illustrate the fact that the flow of each path may not be unique, we design an original delivery network (see Figure1), where each point pair (x,y) of the given arc means the length of x and the capacity restriction of y, respectively.Figure 1
The original delivery network.p
1 means the path v1→v2→v3→v4 and p2 means the path v1→v3→v4. Therefore,
(6)0≤C1≤20≤C2≤20≤C1+C2≤3.
So C1 and C2 may not be unique.Assuming thatTk  is the length of  pk and  Rk   is the delivery times of the k-th path. Since the flow of arc eij assigned to all m paths is not allowed to exceed the capacity restriction of arc eij, we have the following:
(7)∑k=1mCijk≤cij.
Besides, the total number of the materials delivered is not less than q, thus
(8)∑k=1m(Ck×Rk)≥q.
The total time spent in delivering materials is as follows
(9)max{Tkv×Rk}.
Accordingly, when max{(Tk/v)×Rk} reaches minimum value, the time spent on materials delivery via the network is the shortest, thereby we have the following minimax programming model:
(10)t0=minmax{Tkv×Rk}s.t.∑k=1m(Ck×Rk)≥q∑k=1mCijk≤cij,Rk∈N.
At present, there emerged a lot of algorithms solving minimax models, which is unnecessarily repeated here [16–20].Note that when arceij is attacked and fails, other nodes and arcs constitute a new network  G′. By using model (10), we can obtain tij. Similarly, by substituting t0 and tij into the formula of shortest delivery time entropy of  logistics network, we get the time reliability of delivering materials. The smaller the value of H, the stronger the delivery time reliability of the logistics network; otherwise, the larger the value of H, the weaker the delivery time reliability of the logistics network.


## 3. Case Study

Example 2.
To illustrate the validity and practicality of our research, we design two original delivery networksG(1) and G(2) (see Figures 2 and 3), and then we compute the shortest delivery time entropy of logistics network, respectively. q(1)=17 and q(2)=16 represent the quantity of materials to be delivered, and v(1)=4 and v(2)=3 denote the delivery speed of a vehicle, respectively.Figure 2
The original delivery networkG(1).Figure 3
The original delivery networkG(2).From model (10) we learn t0(1)=8.75 and t0(2)=8. The probability of the arc to be attacked and tij are obtained and shown in Tables 1 and 2.Table 1
The probability of the arc being invalid after an attack ofG(1) and the delivery time.
Impaired path
e
12
e
13
e
23
e
24
e
34
e
35
e
45
t
i
j
(
1
)
15.75
18
8.75
10.5
8.75
12
15.75
d
i
j
(
1
)
/
∑
v
i
v
j
∈
E
d
i
j
(
1
)
2
/
21
3
/
21
3
/
21
3
/
21
3
/
21
4
/
21
3
/
21Table 2
The probability of the arc being invalid after an attack ofG(2) and the delivery time.
Impaired path
e
12
e
13
e
23
e
24
e
34
t
i
j
(
2
)
12
21
28
/
3
8
112
/
3
d
i
j
(
2
)
/
∑
v
i
v
j
∈
E
d
i
j
(
2
)
2
/
16
3
/
16
3
/
16
5
/
16
3
/
16Addt0(1),  t0(2),  tij(1),  tij(2),  dij(1)/∑vivj∈Edij(1)  and dij(2)/∑vivj∈Edij(2) into the formula of shortest delivery time entropy of logistics network, we get the following:
(11)H(1)=-∑vivj∈Edij(1)∑vivj∈Edij(1)lnt0(1)tij(1)=-(221ln8.7515.75+321ln8.7518+321ln8.758.75+321ln8.7510.5+321ln8.758.75+421ln8.7512+321ln8.7515.75)=0.3292,H(2)=-∑vivj∈Edij(2)∑vivj∈Edij(2)lnt0(2)tij(2)=-(216ln812+316ln821+316ln8×328+516ln88+316ln8×3112)=0.5494.According to entropy value ofH, the delivery time reliability of logistics network is estimated. That is, the smaller the value of H, the stronger the delivery time reliability of logistics network; otherwise, the larger the value of H, the weaker the delivery time reliability of logistics network. Since H(1)<H(2), the delivery time reliability of G(1) is stronger than G(2).


## 4. Conclusion

The objective of this research is to develop a heuristic approach that can be used to evaluate the reliability of a logistics network in emergency context. A vehicle, however, has to choose circumvention in case a certain path ceases to be effective once attacked by an unexpected event, which actually extends delivery time. Therefore, further in-depth study is needed to take into account ineffective path repairing problems and to develop a more representative method applicable for the specific condition where an arc suffers attacks and becomes invalid.



---

*Source: 879472-2013-04-10.xml*