# Stochastic Simulation on System Reliability and Component Probabilistic Importance of Road Network

Authors: Xiangyu Zhao; Dongwei Wang; Yadan Yan; Ziyuan Gu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Because of the combination explosion problem, it is difficult to use probability analytical method to calculate the system reliability of large networks. The paper develops a stochastic simulation (Monte Carlo-based) method to study the system reliability and component probabilistic importance of the road network. The proposed method considers the characteristics of the practical road network as follows: both link (roadway segment) and node (intersection) components are emphasized in the road network; the reliability for a link or node component may be at the in-between state; namely, its reliability value is between 0 and 1. The method is then implemented using the object-oriented programming language C++ and integrated into a RARN-MGG (reliability analysis of road network using Monte Carlo, GIS, and grid) system. Finally, two numerical examples based on a simple road network and a large real road network, respectively, are carried out to characterize the feasibility and to demonstrate the strength of the stochastic simulation method.


---

## Body

## 1. Introduction

Reliability evaluation of a road network has been extensively studied in the literature. While the initial impetus appears to have been derived from the study of major natural events—such as earthquakes [1]—affecting the connectivity of a road network, it has had wider impacts on the way of thinking in which less severe but more frequency-occurring events may affect the operation of a road network [2]. A reliable road network should consider everyday disturbances, including minor accidents, on-street parking violations, snow, flooding, road maintenance, and traffic signal failures, all of which would lead to the performance deterioration of certain roadway segments or intersections in the network. Reliability of the road network reflects the quality of service that it would normally provide. Thus, the importance of a reliable road network cannot be overemphasized.Although there are some calculating methods [3–5] about the system reliability of the road network, the component probabilistic importance measure, which implies probabilistic contribution of improving component reliability to the system reliability [6], is neglected. Besides, most of the existing studies deal with the connectivity, capacity, or travel time reliability of the link, while node (intersection in the road network) reliability is not taken into account.Extending the definition of connectivity reliability, system reliability of a road network in this study is defined as a measure of network reliability, given the reliability values of each roadway (link) and intersection (node) component. Reliability describes the ability of a system or component to function under stated conditions for a specified period of time. A reliability value is theoretically defined as the probability of an item to perform its required or intended function under stated conditions for a specific period of time. The reliability of the road network reflects the ability of the road network in completing the traffic carrying function in specific time and conditions. Generally, its probability is used to measure the degree, known as road network system reliability.Objective of this paper is to develop a stochastic simulation (Monte Carlo-based) method to study the system reliability and component probabilistic importance of the road network. First of all, it introduces the concept of system reliability and the Monte Carlo-based algorithm to calculate the extended connectivity reliability for an O-D pair and the system reliability for the road network. Then the paper proposes the method to calculate the component probabilistic importance. Finally, two numerical examples (a small network and a large real network) are analyzed to illustrate the accuracy and feasibility of the proposed algorithms. The final section gives some concluding remarks and discussion of future research.


## 2. System Reliability Measurement

Consider a road network with links and nodes. Each link or node is regarded as a component of the road network. Letpii=1,2,…,n;0<pi<1 be the reliability value of a component, either a link or a node. n is the number of components in the road network. The state or reliability value of a component can be considered as the capacity under conditions of degradation because of certain disturbances.Letr=ri:i=1,2,…,n denote a random vector to group the random numbers. rii=1,2,…,n is a random variable with uniform distribution between 0 and 1. To calculate the system reliability, we first use the Monte Carlo simulation approach to generate L realizations of random variable r, denoted by rl,l=1,2,…,L. If ri>pi, component i fails; otherwise, component i is reliable. Since rii=1,2,…,n is uniformly distributed, the larger the pi is, the smaller the probability that ri>pi is, which indicates that there is a smaller probability that component i fails. Hence, larger pi denotes a more reliable component. This is the judgment criterion for further using Monte Carlo simulation to calculate the system reliability. According to the failure state of each component, a path search algorithm could be used to judge whether the O-D pair wkk=1,2,…,K is still connected [7].This process is repeatedL times. In each test, a set of random numbers is generated and the connectivity for each O-D pair wkk=1,2,…,K is judged. K is the number of O-D pairs in the road network. Denoting the number of times that the O-D pair wkm=1,2,…,K is connected by L′, the connectivity reliability can be calculated as follows:
(1)Pk=L′L,
when the sample size L approaches infinity. Mak et al. gave statistical analysis results on the relationship between quality of the approximated solution and sample size [8]. These results can guide us to take an appropriate sample size for a given instance.Then the system reliability of the road network could be defined as(2)PS=∑k=1KαkPk,
where αk is the weighting value for O-D pair wkk=1,2,…,K in the road network. The weighting value could be determined according to the degree of importance of each O-D pair and ∑k=1Kαk=1.


## 3. Component Probabilistic Importance Analysis

In the road network system, contribution of each component to the system reliability is different. Variation of the reliability value of some components may significantly affect the system reliability; while some others may just have small or even few impacts. The component probabilistic importance could be used to evaluate probabilistic contribution of improving component reliability to the system reliability. This measure might be helpful for better understanding the mechanism of system reliability of road networks and thus gives more hints such as the upgrading of a roadway and the strengthening of traffic management to minimize the performance deterioration.Denote the component probabilistic importance of componenti by Iprob,i. Δpi is the variation of the reliability value of component i; ΔPs is the variation of the system reliability due to the variation of the reliability value of component i.Therefore,Iprob,i can be calculated using the Monte Carlo simulation. Assume the reliability value of component i is 1, and the new road network under this condition is denoted by Si. Then
(3)Iprob,i=ΔPSΔpi=PSi-PS1-pi=∑k=1mαkpki-∑k=1mαkpk1-pi=∑k=1mαkpki-pk1-pi,
where Pki is the connectivity of O-D pair wk when the reliability value of component i is 1; pk is the connectivity of O-D pair wk in the original network S.Δ
p
k is defined as follows:
(4)Δpk=pki-pk=1N∑l=1NRki,l-Rk,l,
where Rki,l=1, if the O-D pair wk is connected in the lth test in network Si; otherwise, Rki,l=0. Similarly, Rk,l=1, if the O-D pair wk is connected in network S; otherwise, Rk,l=0. Both Rki,l and Rk,l are binary variables.Besides, in thelth test, component i in the network Si is reliable, because the reliability value has been assumed to be 1. Assume S′ is the sample network for S in the lth test, and Si′ is the sample network for Si in the lth test. Then the difference between networks S′ and Si′ only depends on component i. Hence, if, in the lth test, component i in network S′ is reliable, S′ and Si′ will become identical:
(5)Rki,l-Rk,l=0.
And if wk is connected in the lth test in network S′, wk is certainly connected in the lth test in network Si′:
(6)Rki,l-Rk,l=1-1=0;
if wk is disconnected in the lth test in network S′ and wk is disconnected in the lth test in network Si′:
(7)Rki,l-Rk,l=0-0=0;
if wk is disconnected in the lth test in network S′ while wk is connected in the lth test in network Si′:
(8)Rki,l-Rk,l=1-0=1.
According to (5)–(8), we can have
(9)Rki,l-Rk,l=1ifinthelthtest,componentiinnetworkS′fails,wkisdisconnectedinS′,andwkisconnectedinSi′0otherwise.
According to (4) and (9),
(10)Iprob,i=∑k=1mαkpki-pk1-pi=∑k=1mαk1/N∑l=1NRki,l-Rk,l1-pi=∑k=1mαkNk,nN1-pi,
where Nk,n denotes the number of times when component i in network S′ fails, wk is connected in network Si′, and wk is disconnected in network S′.Besides, under the condition thatpi=1, there has been no possibility for reliability improvement of component i; namely, Iprob,i=0. Moreover, pi is the reliability value of a component (i.e., a link or an intersection) in the road network. It is an indicator to measure ability of component i to complete the traffic carrying function in specific time and conditions, which is the result of many traffic supply and demand factors. Hence, rounding the component reliability pi to three or four decimals is always accurate enough in practical research, which ensures that formulation (3) is valid.


## 4. Numerical Examples

Based on the proposed Monte Carlo-based algorithms for calculating the system reliability and component probabilistic importance, a simulation system called RARN-MGG (reliability analysis of road network using Monte Carlo, GIS, and grid) is developed. The system uses the object-oriented programming language C++ and includes three main modules: preprocessing module, calculation module, and postprocessing module (shown in Figure1). It applies to any road network for calculating the system reliability and component probabilistic importance. The calculation module, which is the core of the system, is based on the proposed Monte Carlo-based algorithms and the grid computing technology.Figure 1
Modules of the RARN-MGG system.In the proposed Monte Carlo-based simulation method, the problem about how to judge whether an O-D pair is connected or disconnected is very important. Hence, bidirectional search is designed in the RARN-MGG system. Path search is from the Origin node and Destination node simultaneously. When the O-D pair is connected, bidirectional search could significantly reduce the search time. When the O-D pair is disconnected, bidirectional search could obtain a set of nodes connected to the Origin node and a set of nodes connected to the Destination node. Hence, when a new component (either a link or a node) is added into the road network, the problem will just become judging whether the new component will make the O-D pair connected. This search algorithm will greatly reduce the complexity and improve the efficiency.We applied the method to a simple road network given in Figure2. The network consists of six nodes, nine links, and one O-D pair. Reliability values for links 1, 2, 3, 4, 5, 6, 7, 8, and 9 are 0.95, 0.95, 0.80, 0.90, 0.90, 0.90, 0.80, 0.90, and 0.95, respectively. Reliability values for nodes 1, 2, 3, 4, 5, and 6 are 0.99, 0.95, 0.90, 0.90, 0.85, and 0.95, respectively.Figure 2
RARN-MGG system interface with a simple network.Table1 shows the comparison between results of the developed RARN-MGG simulation system and results calculated using the probability analytical method [5]. Rs is the system reliability; Iii=1,2,…,6 is the component probabilistic importance of node i; and Ijj=1,2,…,9 is the component probabilistic importance of link j. From Table 1, we can find that results based on Monte Carlo simulation proposed by this paper and results based on the probability analytical method match very well, which furthermore testifies the feasibility applicability of the simulation method.Table 1
Comparison between calculation results of two methods.
Index
R
s
I
(
1
)
I
(
2
)
I
(
3
)
I
(
4
)
I
(
5
)
I
(
6
)
I
[
1
]
Analytical method
0.8690
0.8777
0.2786
0.0850
0.1533
0.2681
0.9147
0.1516
Monte Carlo
0.8692
0.8786
0.2785
0.0850
0.1533
0.2682
0.9147
0.1515
Index
I
[
2
]
I
[
3
]
I
[
4
]
I
[
5
]
I
[
6
]
I
[
7
]
I
[
8
]
I
[
9
]
Analytical method
0.0707
0.0081
0.1256
0.0290
0.0533
0.0056
0.1433
0.1650
Monte Carlo
0.0707
0.0081
0.1256
0.0290
0.0532
0.0056
0.1433
0.1648Moreover, the method is applied to a large road network of Zhengzhou City, China (shown in Figure3). The network consists of 475 links, 280 nodes, and 78120 O-D pairs. Assume that the reliability value for each link in the road network is 0.5 and the reliability value for each node in the road network is 0.9. The weighting value for each O-D pair is identical. Each link and node is encoded with a number.Figure 3
Real road network and land use of Zhengzhou City.The number of simulations or tests is set to be 200000. Using the RARN-MGG method, system reliability value of this road network is 0.05681. Figures4 and 5 suggest the location of the top 60 links and nodes with the highest component probabilistic importance in the road network, respectively. The redder the color is, the greater the importance is.Figure 4
Location of nodes with the highest 60-component probabilistic importance.Figure 5
Location of links with the highest 60-component probabilistic importance.According to Figure4, with the increase of the number of links connected to a node, component probabilistic importance of this node increases, such as node 121 and node 110. The main political, economic, and cultural activities are concentrated in the northeast and southwest parts of Zhengzhou City. However, due to the separation effects of the railway lines (i.e., wide lines in black and white in Figure 3), there are only six roads (links 261, 227, 322, and 379) connecting these two parts. From Figure 5, we can find that links 227 and 322 are among the set of top 30 links with the highest component probabilistic importance. Besides, most of the top 30 links and nodes with the highest component probabilistic importance distribute around the railway station, highway terminal, and hospital regions, which are usually crowded in everyday life. To a large extent, calculation results could reflect the actual road traffic conditions.


## 5. Conclusions

This paper investigated the system reliability and component probabilistic importance of a road network. Characteristics of the practical road network are taken into account. With these considerations, the stochastic simulation methods based on Monte Carlo are proposed. A RARN-MGG system, which incorporates this proposed method, is then developed. The system can be employed as a useful and practical quantitative analysis tool to assist the decision-making for the road management departments, such as evaluating the system reliability of different road network planning schemes, finding the key components that need to be upgraded or improved, or predicting the increased system reliability of a road network when it adds a new link.



---

*Source: 456485-2015-01-21.xml*