Abstract: This study aims to adequately assign the limited available resources to appropriate degraded network components in order to enhance the network reliability. Allocating resources to degraded components would increase the level of performance of components and consequently improve the whole network reliability. Since the performance of the components/network and occurrence of disaster are scholastic, the probabilistic approach is applied to address components/network performance using suitable probability distribution functions. The risk analysis technique needs to be employed to investigate the impacts of investment/upgrading on the network reliability. On the other hand, because the budget is restricted, the best scenario of resource allocation should be chosen to optimally increase the reliability of the entire network utilizing an appropriate optimization method. This study proposes concurrent incorporation of simulation techniques and the dynamic programming method to execute the risk analysis and tackle the optimization problem in order to effectively and efficiently prioritize the limited resources among deteriorated components leading to a more reliable network. A hypothetical case study demonstrates the capability of this methodology.
INTRODUCTION
One of the most important social-economic development indices of every city or country is its transportation system and its functionality and accessibility. After every disastrous event, such as a hurricane, an earthquake, or a mass car accident, in the transportation network in a large and populated city the network capacity will considerably decrease at local or global level depending on the scale or size of the disaster. These stochastic events seriously may damage transportation infrastructure, such as roads and bridges and have long-term effects upon the transportation system. Undoubtedly, they would require days, weeks and months of hard work to return the damaged parts of the system to functioning. One type of such system which is highly vulnerable to damages would be urban transportation network. Regarding the damages occurred in various part of street network, for one thing and lack of alternative routes, for another, travelers pose an increased travel time and cost. This makes upgrading transportation components in the priority order against the disaster a tremendously vital problem (Dicleli and Mansour, 2003).
Transportation network components prioritization techniques: The concept of prioritization has been used by some researchers since early 90`s. Ranf and Eberhard (2007) developed a prioritization scheme after major bridge damage to inspect the bridges in order to conduct a retrofit operation. The prioritization strategy was developed incorporating ShakeMaps, the bridge inventory and newly developed fragility curves. This strategy might recognize 80% of the moderately damaged bridges for the Nisqually earthquake by only inspecting 481 (14%) of the 3,407 bridges within the boundaries of the ShakeMap. However, the conventional method would require 1,447 (42%) bridges to be inspected.
Zonta et al. (2007) developed a bridge prioritization plan for the Autonomous Province of Trento, Italy based on reliability concepts as a part of a Bridge Management System (BMS). The reliability of bridges was conservatively estimated for each bridge. If the condition of bridge was critical its reliability was investigated in a more formal manner using multi-step procedures. In order to prioritize the retrofit actions within a certain budget, they assigned the first rank to those actions that would minimize the risk of occurrence of an unacceptable event in the whole network.
Accessibility of transportation networks and economical approaches: Recently the accessibility and cost-benefit concepts have been also employed by researchers who have worked on transportation systems in disasters. Sohn (2006) evaluated the importance of highway network components in Maryland under flood damage. The author applied an accessibility index to incorporate both the distance-decay effect and the traffic volume influence on the transportation network. A hypothetical disruption of individual links within the floodplain was assumed and the accessibility level of each county and the state were checked before and after the disruption. The investigator reported that the results indicated critical links which were specified based on the distance-only. The distance-traffic volume criteria appeared to be different which resulted in a different prioritization scheme for retrofit actions depending on what criterion to choose. For instance, the percentage loss of accessibility due to the disruption of a link was generally greater in terms of the distance-traffic volume criteria. It is concluded that some links would be significant in both cases, particularly, if a specific link did not have an alternative route (e.g., bypass). The two criteria might obtain a similar outcome if counties connected by the link were low accessibility counties.
Chang and Nojima (2001) evaluated performance of the urban rail and highway transportation systems in terms of network coverage and transport accessibility in the Kobe, Japan, the region devastated by the 1995 Hyogoken-Nanbu earthquake. The authors reported that the performance degradation was much more critical for highways and railways than for other lifeline infrastructure systems. Service restoration proceeded much faster for rail. The restoration of highway system performance was highly dependent on recovery of highway traffic volumes. The study finally measured the subarea transport accessibility and applied this to Kobe`s constituent city wards.
The cost-benefit concept was used in earthquake disaster mitigation for urban transportation systems as an integrated methodology built on the Midwest states (Sohn et al., 2003). The authors considered two aspects of cost: final demand loss and transport cost increase. They applied 1812 New Madrid earthquake to develop a scenario for the analysis. The modeling system included a transportation network loss function, a final demand loss function and an integrated commodity flow model. The investigators indicated the most important link on the network in an economic sense as well as the link with the greatest physical disruption by running the earthquake scenario. The study concluded that the links with greater physical disruption would not be always the ones addressing the greater economic damage. Moreover, a cost-benefit analysis was carried. A decision-making process on the optimal retrofit priority of bridges and links on the transportation network was, also, executed.
Transportation network functionality: For conducting a prioritization scheme, it is necessary to evaluate the function of the network aftermath of a disaster, which can be performed based on defining some disaster scenarios for the probable future events in the corresponding area. Several researchers have worked on the evaluation of the transportation system functionality (Nicholson and Du, 1997). Some investigators have looked at the problem from a different prospective which was a reliability analysis of the system components (Keller, 2002). The stability of the network and the components, particularly bridges, has been also studied by Sanchez-Silva and Daniels (2004). In recent years, the probabilistic vulnerability of the network has been paid more attention. Several techniques such as graph theoretic, simulation and optimization-based techniques have played a significant role in examining potential network vulnerabilities which result in mitigating facility loss and prioritizing retrofit efforts (Grubesic et al., 2008).
Risk analysis of transportation network: Some researchers have taken a particular look at the evaluation and risk analysis of the transportation system exposed to seismic damage (D`Andrea et al., 2005) and proposed a methodology for evaluation of seismic risk of road infrastructures according to study of seismic hazard, investigation of the probability of presence of road users in various regions, analysis of distribution of the population and the infrastructures, evaluation of the functional vulnerability with respect to the potential replaceability of damaged assets and assessment of structural vulnerability of the assets corresponded to the characteristics of the different components.
Pitilakis et al. (2007) proposed the RISK-UE methodology for the risk analysis of lifelines with particular emphasis on transportation networks. The presented methodology might reduce the consequences of lifeline damage in urban areas and provide an efficient mitigation strategy and prioritization policies for pre-earthquake and post earthquake actions. In order to develop the methodology, the author incorporated a detailed inventory for every component at risk along with a reliable seismic hazard assessment, suitable selection of fragility models, estimation of the "global value" and economical influence of lifeline damage and losses.
Research need: It has been revealed that in spite of several researches on the investment prioritization, still few works have been conducted on the efficiency of the proposed prioritization techniques. This study aims to specify the vulnerable components of the system on the one hand by using their fragility curves (probability distribution functions) and to evaluate the functionality of the network on the other hand by defining various disaster scenarios. The basic idea is to use the risk analysis approach in combination with investment prioritization and it is believed that by this approach the reliability of the whole transportation network can be efficiently increased. The capability of the proposed approach is demonstrated by solving a numerical example analyzed by a program developed by the authors. In the following sections of the paper, firstly, the basic concepts and definitions are presented. Secondly, the network modeling and related formulation for investment prioritization are expressed. Then, the efficiency of the proposed method is shown by a numerical example. Finally, the obtained results are discussed.
THE BASIC CONCEPTS
For evaluation of the transportation network subjected to a disastrous event the problem is dealing with a network which has some extent of uncertainty in its various components. Therefore, the prioritized investment process for upgrading the functionality of the network subjected to a given disaster should be based on probability theory. On this basis, for prioritization of the investment various techniques used in the risk analysis can be employed. These include (Bell, 2000; Beale and Horard, 1995):
| • | The Markov chain |
| • | The fuzzy theory |
| • | The game theory |
| • | The decision tree |
| • | The dynamic programming |
| • | The simulation techniques |
Some of these methods could not be used as a direct method for this problem regarding its optimization nature (e.g., Decision Tree). Also, Most of these procedures (except simulation techniques) may represent a constant value as a network evaluation measure, while according to the probability nature of the problem; the probability distribution function should be presented as an evaluation measure. Simulation method would exhibit a distribution of relevant result which is compatible with problem entity although it is needed to consider a large number of probable network states in disaster period and simulation method could not reduce this huge number of states. Developing a procedure which can decrease the number of states (e.g., dynamic programming method), firstly and would demonstrate an evaluation measure as a probability distribution function (simulation techniques), secondly, might be the solution.
Dynamic programming is an optimization method which can directly give the best state from some possible states of investment by minimizing the cost and maximizing the performance of the system, so it can be very useful for the purpose of this study. On the other hand, simulation techniques, such as Monte Carlo or LHS (Latin Hypercube Simulation), are very effective tools for making virtual models of the system without any need to physical experiments. These techniques have been used in risk analysis problems by Chen et al. (2002) and can be used in this study as well for prediction of the network performance in the uncertain conditions like disastrous situations.
On this basis, the use of dynamic programming in combination with simulation techniques seems to provide an efficient method for investment prioritization, which can be conducted in the following stages:
| • | Identification of the network, its components and their fragility curves |
| • | Defining the disaster scenario based on its intensity and occurrence time |
| • | Predicting the states of the network and its critical components based on the defined scenario and the employed fragility curves |
| • | Evaluating the network functionality by appropriate indices (total travel time) |
| • | Prioritizing the mitigation investment by considering the functionality of the network critical component |
THE NETWORK MODELING AND EVALUATION FORMULATION
For each component of the network a specific fragility curve (probability distribution function) can be assumed in the case of any given disaster. Each component k can have a probabilistic stability function Pk which is affected by the investment amount and the type of the event, that is:
(1) |
where, Invk is the amount of investment for the component k and Intk is the intensity of the disaster in the location of component. It is possible that a driver face during his/her travel a component which seems impassible because of the event or congestion. Passengers would behave in two different ways. Firstly, by probability of μ he/she may return back to a location in the route, where it is possible to choose another path. Obviously, this will cause some delay in the travel. So, a delay coefficient β can be defined for every path. After returning to a previous location for choosing another path the driver will choose one of other existing paths. On this basis the average travel time for these paths (t0ij) in ij O-D pair can be defined as:
(2) |
In which is the travel time for the path r (of the paths remained intact) in ij O-D pair, let b the number of intact paths and γ is the travel time increase coefficient, which shows the effect of the transferred travels to the path r because of the impassibility of some other paths.
Secondly, he/she would make a detour by probability of (1-μ) to get to proposed destination. For sake of presentation simplicity the road network is assumed (Fig. 1). Generally, in the road network, drivers have more information about various routes (e.g., detour which has been shown on Fig. 1 by dash line). Namely, there are, usually, specific obvious sign for detour between to nodes in road network to guide passengers in emergency situations. Therefore, it is reasonably supposed that just one forth of drivers may not use the detour to access to their destination. It should be noted that detours have been exploited, only, when the main roads have been failed.
On the other hand, if all paths are blocked because of the high extent of the event all drivers have to wait till at least one path is opened. This delay time is shown by Dij, which is:
(3) |
where, m is the total number of paths in every ij origin and destination (O-D) pair, the θ is the travel time increase coefficient which indicates disutility for travelers in case of all paths blocked in one O-D pair. For travel assignment the Logit formula can be used, which is:
(4) |
where, is the choice probability of the path r from all available paths between O-D pair, considering the minimum travel time as the choosing measure. If the traffic volume in O-D pair is Vij the volume assigned to the path is given by:
(5) |
| Fig. 1: | Schematic presentation of the network model |
Now the network evaluation measure, which is the total travel time for all paths in a O-D pair, can be calculated by:
(6) |
In Eq. 6 m is the number of paths, is volume assigned to the path r,
n is the number of components existing in every O-D pair,
This model has some new advantages on which has been paid little attention, as follows:
| • | The multi O-D pairs are considered to calculate the network evaluation measure |
| • | The stability function is denoted as probability distribution instead of uniform value |
| • | Considering the end blockage of damaged component, re-routing and using detours |
| • | Exclude delays in severe disaster which makes all routes in one O-D pair impassible |
| • | Feasibility of evaluation of importance of information dissemination about failed links |
USING THE MODEL IN INVESTMENT PRIORITIZATION
An illustrative sample of the network is used for the vulnerability analysis of the transportation network and then for prediction of the direct economic losses and travel delays, as well as estimation the financial resources required for its retrofit is shown in Fig. 1. In this example the network consists of eight nodes, 11 links and four OD pairs (O1D1, O1D2, O2D1 and O2D2).
In this study seven levels of performance have been assumed for the network components, in which level 1 corresponds to the lowest or poorest performance and level 7 to highest or the best performance. It is assumed that 10 mega-units of currency have been decided to be invested on the example network upgrading and that each 2 mega-units can upgrade the performance level of each components of the network one level. The initial performance level and the average travel time of the network components have been shown in Table 1, also it has been assumed that 1200 and 500 veh h-1 is allocated to O1D1 and O1D2, respectively and, simultaneously, 300 and 1000 veh h-1 is dedicated to O2D1 and O2D2, respectively.
Using dynamic programming method: As it has been mentioned, dynamic programming is an efficient method for Linear Programming, which can be used of resource allocation. The authors have developed a program which gives the optimum amount of investment for each component of the network, provided that the network performance evaluation measure is specified, which is in this paper the total travel time in the network. It may be understood that link 8 is the most critical and effective component in the network performance (Table 2).
| Table 1: | The specification of the example network |
| Table 2: | Optimum amount of investment on network components by using dynamic programming |
| Fig. 2: | The Tornado graph for sensitivity analysis |
Using simulation technique: The simulation technique has been employed by using at the rate of Risk program. This program is capable of simulation in both Monte Carlo and LHS sampling methods. In both of these methods various states of network regarding components failure distribution would be observed in order to develop a probability distribution of network measure. To find the investment prioritization pattern the step by step simulation method is employed, so that after each step of simulation a sensitivity analysis is performed and the most critical component is determined by a Tornado graph as shown in Fig. 2, which shows that in the first step link 8 is the most critical one. Therefore, it catches the first 2 mega-units.
The calculation is repeated till all 10 mega-units of the investment is utilized. It is noteworthy that the pattern of assigned investment to the components is the same for both of the sampling methods. Also, the network measure calculated by LHS technique is more appropriate (roughly 0.5%) than that of Monte Carlo which is not meaningful (Table 3).
| Table 3: | The Results of investment prioritization by Monte Carlo and LHS techniques |
RESULTS AND DISCUSSION
The effectiveness of dynamic programming and simulation in resource allocation: After the determination of two mentioned methods for resource allocation among the other risk analysis methods, in order to improve the efficiency of investment prioritization procedure of these two techniques, the various states of founded network would be compared by their network measure.
It has been shown in Table 4 that the prioritized investment in both dynamic programming and simulation techniques results in much more improve in the network performance evaluation measure in comparison with uniform investment state (almost 7%) and no investment state (roughly 19%) which undoubtedly represent the high efficiency of investment prioritization in increasing the network reliability by these two techniques. In addition, Table 4 compares the results of two methods according to various states of investments.
Comparing the results of dynamic programming and simulation: As it has been implied, the dynamic programming and simulation methods would be the most appropriate solution for resource allocation, but now it should be discussed that which of them is more appropriate. Dynamic programming could be a powerful resource allocation method to reduce the numerous amounts of network failure states. Furthermore, it might be exploited to present a reasonable investment prioritization pattern, however the constant output (network measure) specified by this method is not match with probabilistic nature of this study. On the other hand, simulation technique is more appropriate for analysis of damaged network because of its probabilistic nature. In addition, the simulation technique can result in a probability distribution function as the output (Fig. 3) which would be more compatible with the probabilistic network evaluation measure entity, since the plenty number of network states may not be decreased by this method.
As a result, it has been indicated that each method has some advantages and a few disadvantages, due to omit the disadvantages the combined method shall be specified. The simulation technique should be used because of its probabilistic nature and the resource allocation pattern has to be obtained from dynamic programming in case of network states reduction and strong matching of this method with optimization problem.
| Table 4: | The results of network analysis with various states of investment by various technique |
| Fig. 3: | Distribution function of the network evaluation measure
by simulation method (LHS) |
In fact, the combined simulation and dynamic programming method is theoretically more reasonable than step by step simulation and dynamic programming solely.
Arbitrary in aforementioned illustrative sample, the results of both methods have been identical. Therefore, the result of combined method would be the same as simulation method on account of similar resource allocation patterns. But, generally, the result of combined method would be different from achieved output of simulation or DP methods. Indeed, since associated advantages and disadvantages, the combined method would be completely preferred.
To be more accurate, after developing the new combined simulation and dynamic programming technique, the optimum sampling method should be demonstrated. Table 3 obviously shows that the number of iterations for achieving 1.5% of convergence by LHS technique is around 20% less than the Monte Carlo technique. Therefore, LHS sampling method would be the efficient technique.
| Table 5: | The results of network analysis for various states of investment with and without information dissemination by different methods |
The effect of information dissemination on the network evaluation measure: To avoid the travels in the end-blocked paths in the network, which leads to time wasting and therefore, to increase in the total travel time of the network, it is possible to inform the drivers about the situation of various paths, specially the end-blocked ones. To find out how much this information dissemination affects the network performance evaluation measure the same three states of investment have been analyzed again by both the dynamic programming and the simulation techniques and the results are shown in Table 5. In so doing, the delay time which is obtained due to re-routing in each O-D pairs would be omitted from proposed model (Eq. 6).
As it is shown in Table 5, informing drivers about the damaged or end-blocked paths increases in average the network performance evaluation measure around 20% in the case of uniform investment and almost 23% in the case of prioritized investment. This leads to decrease in travel time, reduce in travel costs and increase in reliability of the network as well as increase in ease and satisfaction. Therefore, information dissemination has a very great role in the improvement of the network performance in the case of disastrous events. Table 5 compares the network evaluation measure without and with informing in the case of applying the Dynamic Programming (DP).
CONCLUSION
Based on the numerical results it can be said that:
| • | For one thing, by using prioritized assigned investment pattern determined by dynamic programming technique as the initial values the simulation technique gives a suitable probability distribution function as an output. On this basis it can be said that this combined technique based on LHS sampling method is the suitable way for solving the investment prioritization problems in degradable transportation network which has not been taken into consideration by other researcher yet. |
| • | For another, prioritized investment in both dynamic programming and simulation techniques results in much more improve in the network performance evaluation measure, where the simulation technique gives better results to some extent. |
| • | Ultimately, information dissemination has a very great role in the improvement of the network performance in the case of disastrous events. |
| • | To assure that the proposed approach is efficient in the case of large networks and various disastrous situations and difference fragility conditions of the network component performance some further studies are required, which are now being undertaken by the authors. |