# Reliable Path Selection Problem in Uncertain Traffic Network after Natural Disaster

Authors: Jing Wang; Jianming Zhu; Haoxiong Yang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

After natural disaster, especially for large-scale disasters and affected areas, vast relief materials are often needed. In the meantime, the traffic networks are always of uncertainty because of the disaster. In this paper, we assume that the edges in the network are either connected or blocked, and the connection probability of each edge is known. In order to ensure the arrival of these supplies at the affected areas, it is important to select a reliable path. A reliable path selection model is formulated, and two algorithms for solving this model are presented. Then, adjustable reliable path selection model is proposed when the edge of the selected reliable path is broken. And the corresponding algorithms are shown to be efficient both theoretically and numerically.


---

## Body

## 1. Introduction

After natural disaster, especially for large-scale disasters, such as earthquake, the roads are destroyed which makes the traffic network uncertain. Meanwhile the connectivity of the network is uncertain after natural disaster. The road (edge) may be blocked which is caused by damages such as road surface broken and bridge collapsed. Vast relief materials need to be transported to the affected areas, and a reliable path may ensure the arrival of these supplies. So it is practical and urgent for disaster managers to study the reliable path selection problem.Many research works on network reliability have been done both in communication networks and traffic networks. Lin [1] and Ball et al. [2] evaluate the reliability of communication networks including two terminal measures the all-terminal measure and the node set K measure based on the probability that there exists a path between two specified nodes. And Ball [3] showed that network reliability analysis was NP complete. The existing reliability studies of road networks are mainly limited to three aspects: connectivity reliability, travel time reliability and capacity reliability. Connectivity reliability is concerned with the probability that the network nodes remain connected. A special case is the terminal reliability which concerns the existence of a path between a specific origin-destination pair [4]. Another measure of network reliability is travel time reliability or the coefficient of variation of travel time [5]. This is concerned with the probability that a trip between a given OD pair can be made successful within a specified interval of time. This measure is useful to evaluate network performance under normal daily flow variations [6, 7]. Asakura [8] extended the travel time reliability to consider capacity degradation due to deteriorated roads. He defined travel time reliability as a function of the ratio of travel times under the degraded and nondegraded states. This type of reliability can be used as a criterion to define the level of service that should be maintained despite the deterioration of certain links in the network. Chen et al. [9] introduced capacity reliability as a new performance measure to evaluate the performance of a degradable road network. It is defined as the probability that the network can accommodate a certain traffic demand at a required service level, while accounting for drivers’ route choice behavior. More work was done in [10, 11].However in this paper, considering the transport of the relief materials, we choose a reliable path by maximizing the connectivity. Because the traffic network is uncertain in disasters and the edge may become unconnected, we choose the reliable path to ensure the arrival of the materials. But we have no choice except detour when an edge is broken in the path, so we defined detour vital edge and established a model to choose the adjustable reliable path which has higher connectivity reliability, and the detour distance is not far.The remaining of this paper is organized as follows. The definition of path reliability and the reliable path selection model is given in Section2 and two algorithms for solving the reliable path selection model are presented in Section 3. Section 4 describes another model which guarantees the adjustability of the path and the corresponding algorithm. Finally conclusions and recommendations for future work are presented.


## 2. Reliable Path Selection Model

### 2.1. Definition of Path Reliability

The reliability of a path can be defined in three different ways given the connectivity of each edge in the network. Denote that a pathR is composed of edges ei, i=1,2…,m and the connectivity of edge ei is P(ei=1)=pi. That is to say if ei=1, the edge is connected; otherwise, is blocked. Chen et al. [10] define the reliability of path R as
(1)P=∏i=1mP(ei=1)=∏i=1mpi.This is similar to the definition of the probability of meanwhile events. This definition is reasonable from a certain perspective, but it is conservative. Another definition was given under the hypothesis that the connectivity of each edge is irrelative. The reliability of pathR is defined as
(2)P=min(p1,p2,…,pm).It is obvious that there exist some relations between edgesi and path reliability. And it is true that ∏i=1mpi≤P≤min(p1,p2,…,pm). Many researchers concentrated on the work of the bounds estimation, which is famous as Ditlevsen problem. It is usual to take the meaning as P, so another definition for R was given that
(3)P=12(∏i=1mpi+min(p1,p2,…,pm)).In order to describe the disaster problems, we separate the network into two different parts: disaster areaD and affected area I. The edges in the same part are highly related, so we use (2) to define the path section’s reliability in one part and use (1) to define the path reliability in the whole. The path reliability can be defined as
(4)P=min{pe∣e∈D}*min{pe∣e∈I}.Based on definition (4), this paper proposed two different models for path selection and the corresponding algorithms.


### 2.2. Reliable Path Selection Model

After natural disasters, relief materials should arrive at the disaster areas at a given time which is urgent. It is important to determine how to distribute materials and which path to select. A reliable path selection model (RPSM) between two nodes is given as(5)maxPlt(l)≤T,l∈l(s,t).The goal is maximizing the probability of the selected path between the origins and destination t; the constraint ensures that the materials arrive in the restrictive time. And the reliability P is calculated as defined in (4).


## 2.1. Definition of Path Reliability

The reliability of a path can be defined in three different ways given the connectivity of each edge in the network. Denote that a pathR is composed of edges ei, i=1,2…,m and the connectivity of edge ei is P(ei=1)=pi. That is to say if ei=1, the edge is connected; otherwise, is blocked. Chen et al. [10] define the reliability of path R as
(1)P=∏i=1mP(ei=1)=∏i=1mpi.This is similar to the definition of the probability of meanwhile events. This definition is reasonable from a certain perspective, but it is conservative. Another definition was given under the hypothesis that the connectivity of each edge is irrelative. The reliability of pathR is defined as
(2)P=min(p1,p2,…,pm).It is obvious that there exist some relations between edgesi and path reliability. And it is true that ∏i=1mpi≤P≤min(p1,p2,…,pm). Many researchers concentrated on the work of the bounds estimation, which is famous as Ditlevsen problem. It is usual to take the meaning as P, so another definition for R was given that
(3)P=12(∏i=1mpi+min(p1,p2,…,pm)).In order to describe the disaster problems, we separate the network into two different parts: disaster areaD and affected area I. The edges in the same part are highly related, so we use (2) to define the path section’s reliability in one part and use (1) to define the path reliability in the whole. The path reliability can be defined as
(4)P=min{pe∣e∈D}*min{pe∣e∈I}.Based on definition (4), this paper proposed two different models for path selection and the corresponding algorithms.


## 2.2. Reliable Path Selection Model

After natural disasters, relief materials should arrive at the disaster areas at a given time which is urgent. It is important to determine how to distribute materials and which path to select. A reliable path selection model (RPSM) between two nodes is given as(5)maxPlt(l)≤T,l∈l(s,t).The goal is maximizing the probability of the selected path between the origins and destination t; the constraint ensures that the materials arrive in the restrictive time. And the reliability P is calculated as defined in (4).


## 3. Algorithms for Reliable Path Selection Model

In this section two different algorithms are given and compared with each other. The first one is modified depth-first search to give the exact optimal solution, and the second one is a heuristic approximation algorithm.


### 3.1. Modified Depth-First Search Algorithm

Depth-first search is a common method in graphs which is usually used for graph traversing. The basic idea is to go in a branch until there are no vertices, and each vertex is visited only one time. We modified the method by returning to the last visited node if it arrives to the destination pointt. Repeat the search until all s-t paths are found, then calculate the length of each path, and delete those whose traveling time is beyond the limit. Calculate the reliability and choose the best one.It is describes as follows.Algorithm: M-DFSStep 1.
Input distance matrixC, transform the matrix to semi-adjacent matrix N, and initialize F(i)=0, for all i.Step 2.
Begin from the current node (origins for the first time), and choose the next attainable node i.Step 3.
If the vertexi has been visited, return to Step 2; else F(i)=1, and record the path; turn to Step 4.Step 4.
Determine whether we have arrived at t, if t is arrived, record the current path, and turn to Step5; else return to Step 2.Step 5.
If all thes-t paths are selected, go to Step 6; else go back to the last node and turn to Step 2.Step 6.
Calculate the travel time of all the selected paths and delete those beyond the time limit. Calculate the reliability of the remaining path and choose the one withmaxP as the reliable path.The M-DFS algorithm is different from the depth-first search, because whent is visited, it returns to the last node instead of terminating. So the complexity of the algorithm is δn, where δ is the biggest degree of G. Thus it is not efficient for large-scale network. The following section describes an approximate polynomial algorithm.


### 3.2. M-Dijkstra Algorithm

This algorithm uses the greedy method to obtain the satisfaction path with high reliability. According to the descending order of the edges reliability, add one edge to the network each time; then find the shortest path betweens and t in the current network. If the shortest path is beyond the time limit, keep adding edges until finding the satisfied solution.Algorithm: M-DijkstraStep 1.
Get the biggest connectivityPmax from the reliable matrix, set the step size Δp for the iteration, and initialize p=Pmax and G as null edges with all the vertices.Step 2.
p
=
p
-
Δ
p; add the edges with connectivity pe≥p to G.Step 3.
Find the shortest pathl between s and t in the Dijkstra method; if it exists, calculate the travel time of the path; if the time is beyond the limit, go to Step 2; else calculate the reliability p* of the path l; go to Step 4.Step 4.
Add all the edges with connectivity bigger thanp* to G, use Dijkstra method to find the shortest s-t path denoted as l′, and calculate the reliability of l′ as p′. If p′>p*, then l′ is the best solution; else l is the best solution.Attention. The last step in the algorithm is to check the solution to make sure that what we get is the most satisfied solution.Theorem 1.
M-Dijkstra algorithm is a polynomial algorithm with the approximate ratiopend/Pmax, where Pmax is the biggest edge connectivity and pend is the threshold of p when the algorithm terminates.Proof.
Firstly, we show that the algorithm is polynomial. It is known that dijkstra algorithm is polynomial with complexityO(n2); that is to say Step 3 is O(n2), and the algorithm iterates at most M=Pmax/pend times; then the complexity of the algorithm is O(M*n2)=O(n2).
Now let us show the correctness of approximate rate. Assume the network in the last step isG and the best solution we got by the algorithm is lalg and lopt is the optimal solution. Then lopt must appear in G for the first time. If lopt can be found in the former iteration in G′, according to Step 3, we know the shortest s-t path ls in G′; it is obvious that t(lopt)≥t(ls)≥T; this contradicts with lopt as the best solution. It means that lopt include at least one edge e satisfying pend≤pe≤pend+Δp. By definition (4), we got P(lalg)/P(lopt)≥pend/Pmax.


### 3.3. Numerical Results

A small example is calculated by the former two algorithms in this part. Firstly, we showed the definition of semiadjacent matrix and showed an example.In the M-DFS algorithm we use the semi-adjacent matrix in order to improve the efficiency. The matrixNn×n with element nij means the ith row and the jth columns, and if j is larger than the number of nodes adjacent to i, then nij=0 is called the semi-adjacent matrix. As an example showed in Figure 1, the distance matrix of the network is C we can get the semiadjacent matrix N shown in Figure 1.Figure 1
Network of instance.As showed in Figure1, the left side of the red line is affected area I while the right side is disaster area D. It is supposed that the relief materials are transported from 1 to 7 and the time limit T=20, run in MATLAB 7 on PC with Intel 1.73 G, 2 G RAM, the computing time is 0.01194 s, and the results are showed in Table 1. All the 9 different paths are found out and the travel time is computed. It is easy to get that the best path is 1-4-6-7 from 1 to 7, the travel time is 17, and the reliability is 0.820 (Table 1).Table 1
The result of reliable path selection model.
Path
Travel time
Reliability
1-2-7
14
0.760
1-3-4-6-7
20
0.792
1-3-5-7
18
0.765
1-4-3-5-7
22
—
1-4-6-7
17
0.820**
1-3-4-6-5-7
29
—
1-3-5-6-7
25
—
1-4-3-5-6-7
30
—
1-4-6-5-7
26
—
**The best path.Run the M-Dijkstra algorithm in MATLAB with the same PC; we got the solution 1-4-6-7, the same as M-DFS. The time is 0.007884 s, which is shorter than M-DFS. When we need to find the reliable path after disaster in large traffic network, it is strongly recommended to use M-Dijkstra algorithm. As a matter of fact, the rescue decisions are always complex after large-scale disasters.


## 3.1. Modified Depth-First Search Algorithm

Depth-first search is a common method in graphs which is usually used for graph traversing. The basic idea is to go in a branch until there are no vertices, and each vertex is visited only one time. We modified the method by returning to the last visited node if it arrives to the destination pointt. Repeat the search until all s-t paths are found, then calculate the length of each path, and delete those whose traveling time is beyond the limit. Calculate the reliability and choose the best one.It is describes as follows.Algorithm: M-DFSStep 1.
Input distance matrixC, transform the matrix to semi-adjacent matrix N, and initialize F(i)=0, for all i.Step 2.
Begin from the current node (origins for the first time), and choose the next attainable node i.Step 3.
If the vertexi has been visited, return to Step 2; else F(i)=1, and record the path; turn to Step 4.Step 4.
Determine whether we have arrived at t, if t is arrived, record the current path, and turn to Step5; else return to Step 2.Step 5.
If all thes-t paths are selected, go to Step 6; else go back to the last node and turn to Step 2.Step 6.
Calculate the travel time of all the selected paths and delete those beyond the time limit. Calculate the reliability of the remaining path and choose the one withmaxP as the reliable path.The M-DFS algorithm is different from the depth-first search, because whent is visited, it returns to the last node instead of terminating. So the complexity of the algorithm is δn, where δ is the biggest degree of G. Thus it is not efficient for large-scale network. The following section describes an approximate polynomial algorithm.


## 3.2. M-Dijkstra Algorithm

This algorithm uses the greedy method to obtain the satisfaction path with high reliability. According to the descending order of the edges reliability, add one edge to the network each time; then find the shortest path betweens and t in the current network. If the shortest path is beyond the time limit, keep adding edges until finding the satisfied solution.Algorithm: M-DijkstraStep 1.
Get the biggest connectivityPmax from the reliable matrix, set the step size Δp for the iteration, and initialize p=Pmax and G as null edges with all the vertices.Step 2.
p
=
p
-
Δ
p; add the edges with connectivity pe≥p to G.Step 3.
Find the shortest pathl between s and t in the Dijkstra method; if it exists, calculate the travel time of the path; if the time is beyond the limit, go to Step 2; else calculate the reliability p* of the path l; go to Step 4.Step 4.
Add all the edges with connectivity bigger thanp* to G, use Dijkstra method to find the shortest s-t path denoted as l′, and calculate the reliability of l′ as p′. If p′>p*, then l′ is the best solution; else l is the best solution.Attention. The last step in the algorithm is to check the solution to make sure that what we get is the most satisfied solution.Theorem 1.
M-Dijkstra algorithm is a polynomial algorithm with the approximate ratiopend/Pmax, where Pmax is the biggest edge connectivity and pend is the threshold of p when the algorithm terminates.Proof.
Firstly, we show that the algorithm is polynomial. It is known that dijkstra algorithm is polynomial with complexityO(n2); that is to say Step 3 is O(n2), and the algorithm iterates at most M=Pmax/pend times; then the complexity of the algorithm is O(M*n2)=O(n2).
Now let us show the correctness of approximate rate. Assume the network in the last step isG and the best solution we got by the algorithm is lalg and lopt is the optimal solution. Then lopt must appear in G for the first time. If lopt can be found in the former iteration in G′, according to Step 3, we know the shortest s-t path ls in G′; it is obvious that t(lopt)≥t(ls)≥T; this contradicts with lopt as the best solution. It means that lopt include at least one edge e satisfying pend≤pe≤pend+Δp. By definition (4), we got P(lalg)/P(lopt)≥pend/Pmax.


## 3.3. Numerical Results

A small example is calculated by the former two algorithms in this part. Firstly, we showed the definition of semiadjacent matrix and showed an example.In the M-DFS algorithm we use the semi-adjacent matrix in order to improve the efficiency. The matrixNn×n with element nij means the ith row and the jth columns, and if j is larger than the number of nodes adjacent to i, then nij=0 is called the semi-adjacent matrix. As an example showed in Figure 1, the distance matrix of the network is C we can get the semiadjacent matrix N shown in Figure 1.Figure 1
Network of instance.As showed in Figure1, the left side of the red line is affected area I while the right side is disaster area D. It is supposed that the relief materials are transported from 1 to 7 and the time limit T=20, run in MATLAB 7 on PC with Intel 1.73 G, 2 G RAM, the computing time is 0.01194 s, and the results are showed in Table 1. All the 9 different paths are found out and the travel time is computed. It is easy to get that the best path is 1-4-6-7 from 1 to 7, the travel time is 17, and the reliability is 0.820 (Table 1).Table 1
The result of reliable path selection model.
Path
Travel time
Reliability
1-2-7
14
0.760
1-3-4-6-7
20
0.792
1-3-5-7
18
0.765
1-4-3-5-7
22
—
1-4-6-7
17
0.820**
1-3-4-6-5-7
29
—
1-3-5-6-7
25
—
1-4-3-5-6-7
30
—
1-4-6-5-7
26
—
**The best path.Run the M-Dijkstra algorithm in MATLAB with the same PC; we got the solution 1-4-6-7, the same as M-DFS. The time is 0.007884 s, which is shorter than M-DFS. When we need to find the reliable path after disaster in large traffic network, it is strongly recommended to use M-Dijkstra algorithm. As a matter of fact, the rescue decisions are always complex after large-scale disasters.


## 4. Adjustable Reliable Path Selection Model and Algorithm

Because of the uncertainty of the road network after disasters, it is possible that the selected path is blocked although its reliability is very high and travel time is short. In such cases we can do nothing but to adjust the path which is blocked. So another model is proposed for the adjustability of the path. This ensures that when the selected road is blocked, we do not have to circle. Some research work has been done in [12–14] about vital edge or detour-critical edges. So we introduce detour-vital edge of a path to ensure the reliability.Definition 2.
In ann-edge connected (n≥2) graph G(V,E), e(ij) is an arbitrary edge in s-t path l, and i is closer to s, when e(ij) is taken from G, round to t. e*(i*,j*) makes that dG-e*(s,t)≥dG-e(s,t), where dG-e*(s,t)=dG(s,i*)+dG-e*(i*,t) and dG(s,i*) means the distance between s and i* while dG-e*(i*,t) means the length of the shortest path between i* and t. We call e*(i*,j*) as the detour-vital edge of path l.
When detour-vital edge is blocked, it is the worst case for the selected pathl, if we make sure that the rounded distance is not too large in the worst case. Then the selected path will not be too bad. And this is just robust.Definition 3.
We define the length of the rounded path after the corresponding detour-vital edge collapsed of pathl as l’s weight w(l); that is to say w(l)=d(s,i*)+dG-e*(i*,t),  d(s,i*) is the distance between s and i* along path l, and dG-e*(i*,t) means the length of the shortest path between i* and t in graph G-e*(i*,j*):
(6)maxPlT2t(l)w(l),t(l)≤T,w(l)≤T+η,l∈l(s,t).
In model (6), the goal function is g=Pl(T2/t(l)w(l)), and ∂g/∂p>0, ∂g/∂t<0, ∂g/∂w<0 which means that for the reliability the higher the better, and for the time and weight the smaller the better. And the first constraint ensures that the travel time does not go beyond the time limit; the second constraint bounds the time of the path of rounding within T+η.
To solve (6), we must calculate the weight of each path defined in Definition 3 first. Start from the first edge to the last one of path l, suppose the current edge is blocked and find the shortest path between the vertex of the blocked edge and t in the new network, and calculate the length of the round path. Then compare all the length, and get the biggest one as w(l), and the corresponding edge is l’s vital edge. The algorithm operates as follow.Algorithm: Mark  w(l)Step 1.
Calculate the shortest path betweent and other nodes and record the distance vector.Step 2.
k
=
1, w(l)=0, e=e1, E={e∣e∈l}.Step 3.
Suppose the current edgee in path l is blocked; the network becomes G′=G-e; separate the nodes into two parts:
(7)M={i∣i∈G,eisnotincludedinshortestpathbetweeniandt},N={i∣i∈G,eisincludedinshortestpathbetweeniandt}.
CalculatedG-ei(t,u)=minx∈N,y∈M{dG(t,x)-dG(t,u)+dG(t,y)+c(x,y)}, and d=dG-ei(t,u)+d(s,u) as the length of the round path. If d>w(l), then w(l)=d and e*=ek. Turn to Step 4.Step 4.
E
=
E
-
e, if E=Φ, stop and output w(l) and e*; else k=k+1, and go to Step 2.The algorithm Markw(l) is polynomial. In a network with n nodes, a path l has n edges at most; therefore the algorithm iterates n times at most, and in Step 3 the comparison is n2at most. So the algorithm for computing the weight of a path l is O(n3).We insert Markw(l) to the M-Dijkstra algorithm and modify the goal of the algorithm; then we can get the solution for model (6) by the combined algorithm.By the combined algorithm, solving model (6) where T=20, η=10, we can get the following result as in Table 2. And it is easy to get the best result which is R:1→4→6→7.Table 2
The result of adjustable reliable path selection model.
Path
Detour-vital edge
Reliability
Length (l)
w (l)
Goal
1
→
2
→
7
(1, 2)
0.760
14
33
0.640
1
→
3
→
5
→
7
(3, 5)
0.765
18
30
0.560
1
→
4
→
6
→
7
(4, 6)
0.8272
17
29
1.040


## 5. Conclusions

The problem of choosing reliable path after disasters is discussed in the paper. And three different models and algorithms were given. The simple examples were given to show the feasibility and correctness of the models and algorithms. However the traffic work is more complicated and the real problem may be more difficult after real disasters. How to take advantage of the GIS∖GS∖GPS information, describe the reliability of a path accurately and concisely, and give a more stable and reliable path to guarantee the rescue activities is the future research.



---

*Source: 413034-2013-05-12.xml*