Sage Journals: Discover world-class research

Abstract

In transportation planning works, critical links identification is helpful to evaluate the vulnerable parts of the designed network schemes. A new capacity-based network robustness index is presented for identifying critical links and evaluating the transportation system performance. It uses the change of the total network capacity as an evaluation measure. The advanced practical network capacity model is employed to estimate the throughput of transportation system. A sensitivity analysis based algorithm is also developed to solve the practical capacity model efficiently. The capacity-based network robustness index identifies the links which play critical roles in the transportation capacity of the whole network. The capacity-based network robustness index is an effective supplementary to the existing network evaluation indices. The experiments demonstrate the differences between the capacity-based network robustness index and the efficiency-based network robustness index. The capacity-based network robustness index can be used as a practical measure in the situations where the network robustness index is not significant.

Keywords

Transportation network network evaluation network robustness index critical links network capacity sensitivity analysis based

Introduction

In the studies of transportation systems, the disruption of transportation network has been drawing much attention of researchers because of natural disasters, terrorist attacks, and traffic accidents during the past two decades. The transportation system is vital to people’s health, safety, comfort, and economic activities as lifelines nowadays.¹ As a result, a large number of literatures sprang up, which focus on network disruption when network components are degraded or blocked. As experience shows, the blockages or failures of the network links that are heavily traveled or those containing bridges could have serious impacts on the whole transportation network. But there are many potential ordinary road segments whose losses of function also create system-wide influence. Hence, various measures for network performance evaluation have been developed in previous research.

Network vulnerability analysis finds the vulnerable components in a transportation network. It is applied to identify the critical links or nodes in the system to maintain its robustness. The approaches generally evaluate the impact on the system-wide performance as the degradation or removal of a single link. The evaluation indicators can be total travel time (TTT),^2,3 connectivity,^4,5 and accessibility.^1,6

In practical transportation planning, the localized level of service is an often-used indicator for measuring link-level vulnerability. It utilizes the volume-to-capacity (V/C) ratio to reflect the network congestion. Although the V/C ratio has been used to address some complex decision-making in transportation management, it may not enable the traffic engineers to identify the most critical components in system-wide.⁷ Similar link-based indicators can be found in Knoop et al.⁸

The network robustness index (NRI) is a direct measure to reflect how vulnerable a single link is if it was completely removed. The NRI takes into account the spatial relationships and rerouting possibilities associated with the network’s topology, the origin and destination (OD) demand, and the capacity of individual highway segments.⁷ The NRI employs the TTT in system-wide as a measurement, so as to reflect the change in transportation efficiency of the network. Using this indicator, the most critical links in the transportation network can be ranked by their effect to the system-wide efficiency. Nevertheless, this indicator based on travel time is not significant to reflect the throughput capacity of the transportation system. In the following section, we present a counter-example to show the insufficiency of the travel-time-based indicator.

Network reliability also reflects the system-wide performance when the supply or the capacity of system components is uncertain. The reliability indices are generally expressed as a multiplier of the probability that a specific event and the consequence of that event may occur. These include the following: network connectivity reliability, which is the probability that network nodes are connected; travel time reliability, which is the probability that a trip between a given OD pair can be made successfully within a given time interval and a specified level of service; and capacity reliability, which is the probability that the network capacity can accommodate a certain level of traffic demand.^9–11 The reliability provides a probabilistic assessment of transportation networks under uncertainty. However, reliability is a user-oriented quality of the transportation system, while robustness, however, is a characteristic of the system itself. Thus, the robustness is more effective for network vulnerability analysis.

Furthermore, the concept of road network capacity is conducted to reflect how many travel demand can be allocated by a given road network. Wong and Yang¹² first proposed the reserve capacity model. Since the network capacity plays an important role in transportation infrastructure planning and evaluating, it is still now a hot topic in transportation network modeling and widely used. On the basis of the reserve capacity, Wang et al.¹³ conducted a model incorporated with the stochastic user equilibrium, in order to determine the optimal investment strategy to improve the total road network capacity. Xu et al.¹⁴ employed the reserve capacity with multi-mode to discuss the redundancy of the urban transport network. Although the reserve capacity model is easy to use, its assumption that all OD demands increase in the same rate is rather impractical. Beyond the reserve capacity model, Gao and Song¹⁵ extended the reserve capacity model by considering OD-specific demand multipliers. Also, the concepts of ultimate capacity and practical capacity are proposed to conquer the drawbacks of the reserve capacity model.^16,17

Hence, a new evaluation index is proposed in this article, that is, capacity-based network robustness index (CNRI). We defined the CNRI as the change in the total capacity of the network when a single link loses its own capacity. This new measure showed several merits according to the comparative experiments with the NRI. The reminder of this article is organized as follows. Section “Index for transportation network robustness” describes the formulation of the NRI. In section “Overview of network capacity models,” the network capacity model is introduced along with an efficient solution algorithm, following a simple case that illustrates the limitation of the NRI. The concept of CNRI is defined and formulated in section “CNRI.” In section “Numerical results,” the numerical experiments show the special features of the CNRI compared to the NRI. Finally, a short conclusion is summarized in section “Conclusion.”

Index for transportation network robustness

NRI

The original formulation of the NRI is proposed by Scott et al.⁷ The NRI evaluates how critical a given link is to the overall transportation network. A link is more critical if its removal results in a relatively high increase in the TTT in system-wide. The NRI provides the transportation planners with objective information beyond anecdotal observations and is straightforward to be calculated using the traffic assignment tools.¹⁸

The NRI is defined as the change in the TTT resulted from the reassignment of the travel demand in the network when a specific link is removed. It was presented as an alternative to both the V/C ratio and the network-wide gamma index for network connectivity.⁷

The NRI is produced in two steps. First, the TTT is calculated when all links in the network are present. The TTT is given by the sum of the product of the travel time and traffic flow on each link in the network

s = \sum_{a \in A} t_{a} v_{a}

(1)

where s is the TTT of the transportation network; t_a is the travel time through link a at current traffic level, v_a; and A is the set of all links in the network. In applications, it is more realistic to represent the link travel time as a function of the flow on it, that is, t_a = t_a(v_a).⁷

In the second step, the TTT is derived for each link a in the network when the individual link a is completely removed. It is obtained by

s_{a} = \sum_{b \neq a, b \in A} t_{b} v_{b}, \forall a \in A

(2)

where s_a is the TTT of the rerouted traffic flow after the removal of link a. Thereby, the NRI for link a is calculated as the change of the TTT by removing link a

NR I_{a} = s_{a} - s

(3)

To demonstrate the traffic flow change in system-wide, the user equilibrium assignment is employed for the evaluation of the NRI. It is also shown that the TTT is not always increased by removing a single link, so the value of NRI can be either positive or negative. The presence of the network robustness provided a novel approach to identify the critical links in a transportation network. The comparative experiments showed that the evaluation of a network using the NRI gives a better planning solution than those obtained using the traditional localized V/C ratio.⁷ This approach is able to help with decision-making for emergency preparedness, supply-chain logistics, and network robustness. The NRI was further extended for the situation that the link capacity degrades in different levels.¹⁸

A counter-example of NRI application

When the NRI was proposed, it was stated to have a better performance than the traditional V/C ratio. However, the NRI maybe not always reliable for the transportation network where complex OD relationships exist. A potential problem is illustrated in Figure 1 with two OD pairs. The travel demand from node 1 to node 2 is set to three, and the demand from node 1 to node 3 is one. Suppose that the link performance functions of all links is given by $t_{a} = t_{a}^{0} [1 + 0.15 (v_{a} / C_{a})^{4}]$ , where $t_{a}^{0}$ is the free-flow travel time on link a. Thus, the TTT is calculated as 21.014.

Figure 1.

Example of critical links using NRI.

In this case, there is no traffic flow traverses in links 3 and 4. Obviously, the V/C ratios suggest that link 2 is the most critical link. Furthermore, the values of the NRI (NRI₁ = 4.276 and NRI₂ = 17.023) also indicate that link 2 is more critical. However, link 1 carries the most traffic demand in the transportation system. If link 1 was removed, the traffic from node 1 to node 2 would reroute to links 2 and 4. Thus, the flow in link 2 will exceed its capacity, which causes the failure of link 2 by traffic congestion. However, if link 2 was eliminated, rerouted traffic can be easily accommodated by links 1 and 3. Hence, link 1 is actually more critical to the network than the other links. In the above case, neither V/C ratio nor NRI is effective to represent the importance of links to the transportation network.

In summary, the TTT with the framework of equation (1) reflects the efficiency of the total travels. Although only a small number of drivers increase their travel time significantly (such as the counter-example), the TTT could be increased further. Another drawback of the efficiency-based evaluation is that the results allow traffic volumes exceeding links’ capacity, which results in a situation that the links have been blocked by traffic jams.

Overview of network capacity models

Models

The most popular framework of the network capacity problem in passenger transportation system is the bi-level model, in which the traffic flows are maximized under both the capacity constraints and the equilibrium constraints. Wong and Yang¹² first incorporated the reserve capacity concept into a signal-controlled road network. The reserve capacity is defined as the largest multiplier applied to a given OD demand matrix that can be allocated to a network, so the solution is significantly affected by the predetermined OD matrix.

However, it is unrealistic to assume that all OD flows increase in the same rate, especially for the areas under rapid changing. Another concept of ultimate capacity also turned up as an improvement of the reserve capacity model.¹⁷ But it assumes that the OD distribution is totally variable, which may produce extreme results that cause the trip productions at some origins even below the current levels. Consequently, Yang et al.¹⁶ suggested that the new increased OD demand pattern should be variable both in level and distribution, while the OD travel demands of the current trips are remained. Thereby, they introduced the equilibrium trip distribution-assignment model with variable destination costs (ETDA-VDC) to capture this characteristic when evaluating the capacity of transportation networks.¹⁹ Yang’s model was also referred as the practical capacity in later research by Kasikitwiwat and Chen.¹⁷ On the basis of the practical capacity model, Chen and Kasikitwiwat²⁰ discussed the limited flexibility of transportation networks. Then, Chen et al.¹¹ further employed the model for the network reliability analysis. Considering the aforementioned advantages of the practical capacity model, this study will extend it to evaluate the robustness of the transportation network.

The practical network capacity problem is defined over a network with a number of nodes, N, and directed links, A. Let $a \in A$ be a link in the network, which has an upper limit for traffic flow that is referred as link capacity, C_a. The travel time, t_a, through link a is assumed to be an increasing function of its link flow, v_a. $Z \subset N$ is the set of traffic zones where the travel demand is generated. Let $p \in Z$ and $q \in Z$ represent the origin node and the destination node, respectively. The numbers of trip production at origin p is represented by ${\bar{O}}_{p}$ and O_p, and the trip attraction at destination q is ${\bar{D}}_{q}$ and D_q, which are respectively associated with the existing and additional demand. Since two types of travel demand are taken into consideration, the demand variables are defined in pairs. Thus, the amounts of the existing and additional traffic demand from p to q are denoted by ${\tilde{d}}_{pq}$ and d_pq, respectively. Let R_pq represent the set of acyclic routes between OD pair pq. For each route $r \in R_{pq}$ , the route flow consists of the existing route flow, $h_{r}^{pq}$ , and additional route flow, $f_{r}^{pq}$ , which are produced by the two types of travel demand.

The practical network capacity assumes that the additional flow between each OD is changeable in terms of the travel utility. The utility could include the destination attractiveness, the cost along traveling route, and other factors. The attractiveness of destination is determined by the congestion at the destination zone and the expenses for the activity in that area. In network capacity model, the utility from origin p to destination q is formulated as U_pq = –(M_q + τ_pq), in which τ_pq is the minimum travel cost from p to q, and M_q denotes the destination cost which could be an increasing function of the additional trip attraction, D_q, at destination q. Besides, the destination choices of travelers at each origin p are assumed to have certain randomness. Thus, the conditional probability that an individual will choose destination p is given by the standard logit function. So, the additional travel demand d_pq is given by

d_{pq} = O_{p} \frac{\exp {- θ (τ_{pq} + M_{q})}}{\sum_{k \in Z} \exp {- θ (τ_{pk} + M_{q})}}, \forall p \in Z, q \in Z_{p}

where θ is the impedance parameter for trip distribution and reflects the sensitivity of the travelers to the cost from p to q. Z_p is the set of destination nodes associated with origin p.

Following the choice behavior, the practical capacity model for road networks is formulated as the following MPEC (mathematical programming with equilibrium constraints) problem.

Upper-level problem

\underset{O}{Max} \sum_{p \in Z} O_{p}

(4)

s . t . v_{a} (O) \leq C_{a}, \forall a \in A

(5)

O_{p} = \sum_{q \in Z_{p}} d_{pq} (O) \leq O_{p}^{max} - {\bar{O}}_{p}, \forall p \in Z

(6)

D_{q} = \sum_{p \in Z_{q}} d_{pq} (O) \leq D_{q}^{max} - {\bar{D}}_{q}, \forall q \in Z

(7)

O_{p} \geq 0, \forall p \in Z

(8)

where $d_{pq} (O)$ and $v_{a} (O)$ are obtained by solving the ETDA-VDC problem in lower level.

Lower-level problem: ETDA-VDC model

\underset{(f, h, d)}{Min} \sum_{a} \int_{0}^{v_{a}} t_{a} (x) dx + \frac{1}{θ} \sum_{p \in Z} \sum_{q \in Z_{p}} d_{pq} (\ln d_{pq} - 1) + \sum_{q \in Z} \int_{0}^{D_{q}} M_{q} (y) dy

(9)

s . t . \sum_{q \in Z_{p}} d_{pq} = O_{p}, \forall p \in Z

(10)

\sum_{r \in R_{pq}} h_{r}^{pq} = {\tilde{d}}_{pq}, \forall p \in Z, q \in Z_{p}

(11)

\sum_{r \in R_{pq}} f_{r}^{pq} = d_{pq}, \forall p \in Z, q \in Z_{p}

(12)

v_{a} = \sum_{p} \sum_{q} \sum_{r} (f_{r}^{pq} + h_{r}^{pq}) δ_{a, r}^{pq}, \forall a \in A

(13)

d_{pq} \geq 0, \forall p \in Z, q \in Z_{p}

(14)

f_{r}^{pq} \geq 0, \forall p \in Z, q \in Z_{p}, r \in R_{pq}

(15)

h_{r}^{pq} \geq 0, \forall p \in Z, q \in Z_{p}, r \in R_{pq}

(16)

The upper-level problem defines a maximum trip production model. The objective is to maximize the summation of the additional trip production at origins. Equation (5) represents that the traffic flow on every link should not exceed its capacity. Constraints (6) and (7) are the limitation of the zonal trip production and attraction. This means the number of trips generated and attracted at each traffic zone should be limited by some upper bounds, namely $O_{p}^{max}$ and $D_{q}^{max}$ , respectively. O, f, h, and d represent the corresponding variables in vector form.

The lower-level problem is the ETDA-VDC model. The objective function (9) indicates the choice behavior of both the existing and additional travel demand. Constraint (11) shows that the amount of the existing flows are fixed for each OD, while constraints (10) and (12) show that the additional flows are only restrained by the origin productions. The relationship between the link flow and route flow is represented in equation (13), where $δ_{a, r}^{pq}$ represents the link-route incidence indicator, which equals 1 if link a is on route r from p to q and 0 otherwise. All the variables must be nonnegative, that is, constraints (14)–(16).

An sensitivity analysis based solution algorithm

Several solution methods can be used for the network capacity problems. In this study, we present a modified procedure based on the original sensitivity analysis based (SAB) algorithm.²¹ The steps of the modified SAB algorithm are given as follows:

Step 0: initialization. Determine an initial value of trip production pattern O⁽⁰⁾. Set k := 0.

Step 1: solving lower-level problem. Solve the ETDA-VDC model in lower level for the given O^(k), by which the equilibrium link flows v^(k) and OD demand d^(k) are obtained (v denotes the link flows in vector form).

Step 2: sensitivity analysis. Calculate the partial derivatives, $\partial v_{a} / \partial O_{p}$ and $\partial d_{pq} / \partial O_{p}$ , using the sensitivity method for the ETDA-VDC model.²²

Step 3: local linear approximation. Formulate local linear approximations of the upper-level capacity constraints using the derivative information, and solve the approximate linear programming problem to produce an auxiliary trip production ${\hat{O}}^{(k)}$ .

Step 4: updating solution. Let $O^{(k + 1)} : = O^{(k)} + α \cdot ({\hat{O}}^{(k)} - O^{(k)})$ , where α is a feasible step size.

Step 5: convergence criterion. If the convergence criterion is satisfied or the maximum number of iteration is reached, then stop; otherwise, return to Step 1, and set k := k + 1.

Step 1: Route-based algorithm for the ETDA-VDC model

Initialization

Set n := 0, determine the initial link cost ${t_{a}^{0}}$ and destination cost ${M_{q}^{0}}$ by setting v_a = 0, $\forall a \in A$ and d_pq = 0, $\forall p \in Z, q \in Z_{p}$ , respectively. For each origin, $p \in Z$ .

Find the tree of minimum-cost routes rooting from p. For each minimum-cost route $\bar{r}$ to destination $q \in Z_{p}$ , denote the minimum cost by $τ_{pq}^{0}$ , and let $R_{pq}^{0} : = R_{pq}^{0} \cup {\bar{r}}$ .

Compute the initial variable OD demands by

d_{pq}^{0} = O_{p} \frac{\exp [- θ (τ_{pq}^{0} + M_{q}^{0})]}{\sum_{k} \exp [- θ (τ_{pk}^{0} + M_{k}^{0})]}, \forall q \in Z_{p}

For $q \in Z_{p}$ , assign the entire OD demand ${\tilde{d}}_{pq}$ and $d_{pq}^{0}$ to the minimum-cost route $\bar{r}$ from p to q, and obtain the initial route flow $F_{r}^{pq}$ and route flow proportions { $γ_{pqr}^{0} = 1$ }, as well as the initial link flows.

Update the link costs using the initial link flows.

Main loop

For n = 1 to the number of main iterations (I_Main):

1. Equilibrate route flows and retain the additional trip demands. Given the current additional OD demand ${d_{pq}^{n}}$ and route flow ${F_{r}^{pq}}$ , obtain (n−1)th iteration.

For each origin $p \in Z$ , generate the minimum route tree rooted at p. For each destination $q \in Z_{p}$ , retrieve the minimum route $\bar{r}$ of the minimal cost $τ_{pq}$ , and equilibrate the route set $R_{pq}$ between OD pair pq as follows.

1.1. Column generation. Update the route cost $c_{pqr}, \forall r \in R_{pq}$

If \bar{r} \notin R_{pq}, let R_{pq} : = R_{pq} \cup {\bar{r}}

Otherwise, tag the minimum route among the routes in $R_{pq}$ as $\bar{r}$ .

1.2. Shift flow from non-minimum routes to minimum route

(a) Compute the route flow shift

Δ F_{r} = \frac{c_{pqr} - τ_{pq}}{\sum_{a \in A_{r, \bar{r}}} (\partial t_{a} / \partial v_{a})}, \forall r \in R_{pq}, r \neq \bar{r}

where $A_{r, \bar{r}}$ is the set of links that belong either to non-minimum route r or minimum route $\bar{r}$ but not to both of them.

(b) Update the route flows and project it onto the feasible set

Non - minimum routes : F_{r}^{pq} : = F_{r}^{pq} - min {Δ F_{r}, F_{r}^{pq}}, \forall r \in R_{pq}, r \neq \bar{r}

Minimum route : F_{\bar{r}}^{pq} : = d_{pq} - \sum_{r \in R_{pq}^{+}, r \neq \bar{r}} F_{r}^{pq}

If $F_{r}^{pq} = 0$ , then eliminate the route r, that is $R_{pq} : = R_{pq} / r$ .

1.3. Compute the new route flow proportions

γ_{pqr} = \frac{F_{r}^{pq}}{({\tilde{d}}_{pq} + d_{pq})}, \forall r \in R_{pq}, p \in Z, q \in Z_{p}

2. Update OD flows and retain the route flow proportions. Given the route flow proportions ${γ_{pqr}^{n}}$ , link flow ${v_{a}^{n}}$ and route cost ${c_{pqr}^{n}}$ are obtained in the above steps.

2.1. For each destination zone $q \in Z$ , compute the destination cost $M_{q}^{n}$ by OD demand $d_{pq}^{n}$ and ${\tilde{d}}_{pq}$ .

2.2. For each OD pair, optimize the additional OD flows as follows:

(a) Find the set of auxiliary trip demands ${{\hat{d}}_{pq}^{n}}$ by solving the following logit distribution model

{\hat{d}}_{pq}^{n} = O_{p} \frac{\exp [- θ (τ_{pq}^{n} + M_{q}^{n})]}{\sum_{k} \exp [- θ (τ_{pk}^{n} + M_{k}^{n})]}, \forall p \in Z, q \in Z_{p}

(b) Calculate the auxiliary traffic flow ${\hat{v}}_{a}^{n}$ on each link a with the given route flow proportions ${γ_{pqr}^{n}}$

{\hat{v}}_{a}^{n} = \sum_{p \in Z} \sum_{q \in Z_{p}} \sum_{r \in R_{pq}} γ_{pqr}^{n} ({\tilde{d}}_{pq} + d_{pq}^{n}) \cdot δ_{a, r}^{pq}

(c) Let $v_{a}^{λ} = (1 - λ) v_{a}^{n} + λ {\hat{v}}_{a}^{n}, \forall a \in A$ and $d_{pq}^{λ} = (1 - λ) d_{pq}^{n} + λ {\hat{d}}_{pq}^{n}, \forall p \in Z, q \in Z_{p}$ , and solve the one-dimensional search problem defined as follows to obtain the optimal step size $λ^{*} \in [0, 1]$

\underset{0 \leq λ \leq 1}{Min} Z (λ) = \sum_{a \in A} \int_{0}^{v_{a}^{λ}} t_{a} (x) dx + (1 / θ) \sum_{p \in Z} \sum_{q \in Z_{p}} d_{pq}^{λ} (\ln d_{pq}^{λ} - 1) + \sum_{q \in Z} \int_{0}^{D_{q}^{λ}} M_{q} (y) dy

where $D_{q}^{λ} = \sum_{q \in Z_{p}} (d_{pq}^{λ} + {\tilde{d}}_{pq})$ .

(d) Update the link flows and the additional trip demands

v_{a}^{n + 1} : = v_{a}^{λ}, \forall a \in A

d_{pq}^{n + 1} : = d_{pq}^{λ}, \forall p \in Z, q \in Z_{p}

2.3. Compute the route flows

F_{r}^{pq} = γ_{pqr} ({\tilde{d}}_{pq} + d_{pq}^{n + 1}), \forall r \in R_{pq}, p \in Z, q \in Z_{p}

2.4. Update the link cost {t_a} and the derivative cost ${\partial t_{a} / \partial v_{a}}$ .

3. Check convergence. Terminate if the convergence criterion is satisfied; otherwise, start a new iteration of the main loop, and set n := n + 1.

Remark 1

The above solution algorithm is developed based on Evan’s algorithm for combined trip distribution and traffic assignment models. The steps are implemented in two stages, in which the trip demand d_pq and link flow v_a are derived in turn. Since the OD demands in the stage for equilibrating route flows vary in each iteration, the route flow proportion $γ_{pqr}$ is defined to denote the portion of the total OD demand that is assigned to the route. This definition has the advantage that the value of $γ_{pqr}$ need not be scaled when the OD demand changes.²³ Furthermore, two classes of trips with different OD distributions are taken into consideration in the ETDA-VDC model, but the equilibrium condition for their route choice principle is same. It is general to suppose that both the existing route flows and the additional route flows have the same proportion on every used route. Therefore, we used the total route flow, $F_{r}^{pq}$ , as the main variable in the traffic assignment stage. The ratio of the existing demand to the additional demand can be derived by ${\tilde{d}}_{pq} / d_{pq}$ .

Remark 2

In the proposed algorithm, the route-based method with gradient projection (GP) is used for equilibrating traffic flows. We chose this method because it is easy for obtaining an equilibrated route set which is the necessary prerequisite to use the restriction sensitivity analysis approach in the next step.²² In addition, the GP algorithm shows good performance for producing high-precision solutions, which is also a necessary requirement for sensitivity analysis.²⁴

Step 3: Local linear approximation procedure

The bi-level problem is linearized using first-order approximation at the given point, $O^{*}$ . Let $v (O^{*})$ and $d (O^{*})$ in vector form denote the solutions to the lower-level model at O*. The implicit relationships between the trip productions and the traffic flow pattern are represented using the Taylor expansion

v (O) \approx v (O^{*}) + \nabla_{O} v \cdot (O - O^{*})

(17)

d (O) \approx d (O^{*}) + \nabla_{O} d \cdot (O - O^{*})

(18)

where $\nabla_{O} v$ and $\nabla_{O} d$ are the gradient matrices of the link flows and OD demands with respect to the trip productions. Thus, the original bi-level problem will be reformulated as

\underset{O \geq 0}{Max} \sum_{p \in Z} O_{p}

(19)

s . t . [\begin{matrix} \nabla_{O} v \\ Φ \cdot \nabla_{O} d \\ Ψ \cdot \nabla_{O} d \end{matrix}] \cdot O \leq [\begin{matrix} C \\ O^{max} - \bar{O} \\ D^{max} - \bar{D} \end{matrix}] - [\begin{matrix} v^{*} \\ O^{*} \\ D^{*} \end{matrix}] + [\begin{matrix} \nabla_{O} v \\ Φ \cdot \nabla_{O} d \\ Ψ \cdot \nabla_{O} d \end{matrix}] O^{*}

(20)

where O is the decision variables in the linear programming. $Φ$ and $Ψ$ are the origin-OD incidence matrix and the destination-OD incidence matrix, respectively. O^max, $\bar{O}$ , D^max, and $\bar{D}$ are, respectively, the variables of $O_{p}^{max}, {\bar{O}}_{p}, D_{p}^{max}$ , and ${\bar{D}}_{p}$ in vector form. Note that the right-hand side of the inequality is a constant vector. When O = O*, the inequality is satisfied only if both the link flow and the zonal trip generation do not exceed their capacity constraints. The solution to this problem, denoted by ${\hat{O}}^{(k)}$ , can be easily derived using a linear programming algorithm, such as the simplex method.

Remark 3

The original SAB procedure for the network capacity problem directly uses the solution to the linear approximation as the new start point in the next iteration. According to our tests, the original SAB only works to very small examples. When dealing with larger networks, using the original procedure may conduct an improved solution located outside the feasible region. If the deviation is sufficiently large, a non-solution linearized problem will be formed based on the infeasible point. Considering the linear programming in this step is only a local approximation, the value of the step length should not be too large. Therefore, the maximum step length is adopted to reduce the influence of the approximation errors. In our modified algorithm, the new solution is updated using the convex combination of the solution from the last iteration, O^(k), and the solution to the approximate linear problem, ${\hat{O}}^{(k)}$ , which is given by the following equation

O^{(k + 1)} : = O^{(k)} + min {λ_{max}, | | {\hat{O}}^{(k)} - O^{(k)} | |} \cdot \frac{({\hat{O}}^{(k)} - O^{(k)})}{| | {\hat{O}}^{(k)} - O^{(k)} | |}

(21)

where $λ_{max}$ is the predetermined maximum step length that restrains the new solution from moving too far from the current point. $({\hat{O}}^{(k)} - O^{(k)}) / | | {\hat{O}}^{(k)} - O^{(k)} | |$ conducts the unit directional vector of the descent direction. The value of $λ_{max}$ is flexible. Since the complexity of the bi-level problem, a self-adaptive scheme for $λ_{max}$ should be considered in the large-scale problem, so as to provide a step-size sequence that ensures the convergence. To guarantee the feasibility of the new solution, we suggested the flowing procedure:

Use equation (21) to produce a temporary solution O^t;

Solve the lower-level problem based on the temporary origin production O^t;

Check the feasibility of the link flows and the zonal trip generations according to the capacity constraints in equations (5)–(7):

(a) If the constraints are violated, lower the maximum step length $λ_{max}$ (e.g. by its half) and then return to step 1;

(b) Otherwise, a feasible new point is found, and let O^(k + 1) := O^t.

Remark 4

The practical network capacity model is formulated as a non-convex optimization which is hard to solve for a global optimum. In practice, the heuristic methods are usually used to deal with these types of problems. Yang²⁵ first suggested an iterative estimation assignment (IEA) algorithm in which the derivatives of the decision variables are approximated using the link choice and destination choice probabilities. An efficient method was conducted in Du et al.²⁶ recently and was shown to find a better solution compared to the original SAB and IEA algorithms. On the basis of our previous research, we further improved the lower-level solution algorithm and adopted a self-adaptive step length restraint. The modified SAB algorithm easily tackles the network capacity problems with larger scale than the previous works.

CNRI

The example in Figure 1 indicates that the NRI may provide a wrong guidance sometimes. The NRI uses the TTT as the evaluation index. The TTT only reflects the transportation efficiency other than the “transportation capacity” of the system. In this section, a new measure, namely CNRI, is suggested which takes the change of the system capacity as an index considering the elimination of the individual link in the transportation network.

Let T be the total capacity of the original network with all full-functional links. Then, T_a represents the capacity of the disrupted network by completely removing link a. So, the CNRI is derived for each link using the decrement in the network capacity when the link is blocked

CNR I_{a} = T - T_{a}

(22)

Thus, the capacity robustness evaluation steps for a transportation network are described as follows, and a flowchart of the procedure is given in Figure 2.

Step 1. Evaluate the transportation capacity of the original network with all links, which produce the value of T. In this study, we employed the practical capacity model to describe the network capacity problem and used the proposed algorithm in the previous section for the model solution.

Step 2. For each individual directed link $a \in A$ in the network, calculate the CNRI value for the link.

Step 2.1. Solve the network capacity problem in the disrupted network where the link a is completely removed, and obtain the value of T_a.

Step 2.2. Compute the CNRI for link a using equation (22).

Step 3. Check if all links in the network have been visited. If not, go to step 2; otherwise, go to the next step.

Step 4. Collect system-wide statistics based on the above evaluation.

Figure 2.

Flowchart of the CNRI evaluation procedure.

Numerical results

A simple example

In this section, we apply the CNRI evaluation procedure to a simple network. The numerical results are produced using the following data:

Test network in Figure 3 consists of 6 nodes, 9 directed links, 2 origins (node 1 and 2), and 2 destinations (nodes 3 and 4).

Link properties are illustrated in Figure 3, and the link travel time function used is the standard Bureau of Public Road (BPR) function: $t_{a} = t_{a}^{0} [1 + 0.15 (v_{a} / C_{a})^{4}]$ .

Existing OD demands are d₁₃ = 18, d₁₄ = 12, d₂₃ = 24, and d₂₄ = 12 (as shown in Figure 3).

Destination cost functions for nodes 3 and 4 are assumed to be $M_{3} = 0.15 D_{3}^{0.25} - 1.2$ and $M_{4} = 0.15 D_{4}^{0.25} - 1.5$ .

Zonal capacities for the origins and destinations are $O_{1}^{max} = 140$ , $O_{2}^{max} = 120$ , $D_{3}^{max} = 140$ , and $D_{4}^{max} = 140$ .

Figure 3.

Test network.

The CNRI of each link is produced when $θ = 0.5$ . For comparison, the value of NRI for each link is also calculated under the current OD demands. The results are shown in Figure 4. The two measures give different results of rank ordering of the critical links. According to the value of the CNRI, links 1 and 3 are the most important links, because the removal of either link will result in a significant reduction in the total network capacity. However, the result from the NRI cannot reflect the importance of the two links.

Figure 4.

Results of the CNRI and NRI for each link.

Figure 5 shows the impact of the impedance parameter (i.e. the dispersion degree of the destination choice behavior) on the results of the CNRI. The impedance parameter θ is given from 0.01 to 10. Note that the overall trend of the CNRI for each link decreases with an increase in the value of the impedance parameter. It means that when the transportation network users are more sensitive to the trip expense, they prefer to choose those closer tourism destinations, and thus the disruption of links could have less influence on the capacity of the whole transportation system. The CNRI of link 1 is shown to be more sensitive to the value of θ, so it is meaningful to predetermine the parameter θ when we apply the proposed CNRI measure.

Figure 5.

Impact of the impedance parameter on CNRI.

Sioux Falls network

Comparative experiments are conducted in this section between the CNRI and NRI for network evaluation. For simplification, the destination attractiveness term, M_q, of the travel utility is set to be zero. The results are produced using the following data:

Sioux Falls network comprises 24 nodes, 76 directed links, and 24 origin/destination nodes.

Link properties and travel demand are obtained from Bar-Gera,²⁷ and the existing OD demand is scaled down from the original data.

Link travel time function employs the BPR function given by $t_{a} (v_{a}) = t_{a}^{0} [1 + 0.15 (v_{a} / C_{a})^{4}]$ , where $t_{a}^{0}$ is the free-flow travel time through link a.

Zonal capacity for each origin or destination is 80,000 unit for both trip production and attraction.

Impedance parameter values are 0.1, 0.2, and 0.5.

The CNRI values are derived under three different values of the impendence parameter, which represent the distinct levels of sensitivity to the travel cost when travelers choose their trip destinations. When θ = 0.2, travelers are not sensitive, and this will produce a scattered trip distribution for the additional demand. As θ = 1.0, the trip distribution is sensitive to impendence, and thus, the distant destinations (with longer travel time) are avoided by travelers. Under different values of θ, the network capacities are evaluated at first. Then, the CNRI values are derived using the modified SAB algorithm. And the NRI is also produced as a reference. Results of CNRI and NRI are summarized in Table 1.

Table 1.

Summary statistics for NRI and CNRI.

	CNRI			NRI
	θ = 0.1	θ = 0.2	θ = 0.5	NRI
Base value	Network capacity			TTT 827,795.996
Base value	139,878.39	194,811.03	339,266.56	TTT 827,795.996
Actual value
Mean	12,646.35	10,899.67	8,236.35	14,388.152
Standard deviation	11,460.26	9,654.63	6,737.76	9,390.926
Minimum	−2,774.73	−4,421.38	−6,408.25	0.000
Maximum	53,142.74	45,090.84	27,192.47	33,965.168
Percentage change from base value
Mean	9.04	5.60	2.43	1.738
Standard deviation	8.19	4.96	1.99	1.134
Minimum	−1.98	−2.27	−1.89	0.000
Maximum	40.00	23.15	8.02	4.103

NRI: network robustness index; CNRI: capacity-based network robustness index; TTT: total travel time.

According to the base value of the capacity in Table 1, when θ is small, the network generally shows a lower transportation capacity. It is because that more trips with long distance consume most of the resources of the system. In contrast, the capacity could be higher in the cases with larger θ. In Table 1, both the absolute values and the percentage changes from base values are listed. The means of the CNRI values are distinguished and decrease as θ grows. The standard deviations are not very different. The maximum value of CNRI is found when θ = 0.2, for both actual and percentage values. The minimum actual value of CNRI is produced under θ = 1.0, while according to the percentage value, the minimum value of CNRI is detected under θ = 0.2. These give the suggestion that the network with lower value of θ could be more sensitive to the disruption of the links. Note that the network capacity could either increase or decrease for the removal of the individual link. Though the absence of the link may improve the throughput of the network analytically, the system-wide travel time is generally increased according to the corresponding value of NRI.

The comparison of the CNRIs for all links (from link 1 to link 76) is illustrated in Figure 6. Obviously, similar trends are obtained for distinct values of θ in the three cases. For each pair of the three results, a scatterplot of the relationship is shown in Figure 7. A linear or monotonic relationship would suggest that the solutions to critical link identification are similar. The Spearman rank-order correlation coefficient is also computed using the SPSS software. For the three paired comparisons, the correlation coefficients (with p-values in parentheses) are 0.354 (0.002), 0.400 (<<0.01), and 0.278 (0.015), respectively, which means the correlations are significant.

Figure 6.

CNRIs of all links in Sioux Falls under different levels of θ.

Figure 7.

Relationship among the CNRIs for different levels of θ.

Important differences in the results of critical link identification are reported in Table 2. Table 2 lists the top 10 links (ranked from highest to lowest values) identified according to each measure. There are apparent distinctions among the ranking according to the CNRI and the NRI. For the CNRI, there are four common links (i.e. links 5, 37, 46, and 66) identified in all the three cases; four links (i.e. links 17, 54, 69, and 75) are found twice in the three CNRIs. The results show that if these links are blocked by accidents, destroyed in disasters, or closed for construction, the whole system will lose a significant portion of its capacity for transportation. Compared to the NRI, links 37 and 46 are identified either using the CNRI or the NRI. The total values of the indices in the bottom row are obtained by summarizing the values of the top 10 links identified with deferent measures. The total values show that the transportation networks with lower impedance parameters, θ, are more vulnerable to the network degradation according to CNRI.

Table 2.

Comparative results of critical links by CNRI and NRI (top 10 links).

Rank	CNRI (θ = 0.1)		CNRI (θ = 0.2)		CNRI (θ = 0.5)		NRI
Rank	Link ID	CNRI value	Link ID	CNRI value	Link ID	CNRI value	Link ID	NRI value
1	74	53,142.74	66	45,090.84	37	27,192.47	39	33,965.16
2	5	47,725.74	54	38,815.40	56	25,462.14	16	33,835.13
3	66	47,228.62	75	30,866.85	36	21,459.84	19	33,751.18
4	54	34,167.83	46	30,450.73	55	19,818.77	74	33,726.76
5	46	33,299.21	34	29,081.92	66	19,189.87	26	31,186.31
6	45	32,330.64	27	26,465.44	46	19,163.89	25	30,735.37
7	69	28,297.79	69	26,330.40	39	17,880.38	38	29,667.31
8	11	26,303.93	37	24,322.96	5	17,869.37	37	29,460.30
9	17	24,369.61	17	22,457.11	38	17,755.49	43	28,388.12
10	37	23,957.03	5	22,002.71	75	17,502.35	46	28,143.40
Total	350,823.14		295,884.36		203,294.57		312,859.04

CNRI: capacity-based network robustness index; NRI: network robustness index.

The bold values signifies that the link is ranked in the top 10 in all three situations with different levels of θ. The italic values signifies that the link is ranked in the top 10 only in two out of three situations.

Besides, the NRI values of the top four links are very close as listed in Table 2. These four links are from two pairs of two-way arcs (i.e. links 16 and 19 connect the same two nodes in contrast directions; same for links 39 and 74). According to the NRI only, the importance of the four links is not clear. Thus, the CNRI can be used as a complement for making decision. For example, according to the CNRI, when θ = 0.2, the rank order is CNRI₃₉ > CNRI₇₄ > CNRI₁₉ > CNRI₁₆. Hence, the importance of the links can be distinguished well. In such situation, the CNRI could be used as an efficient alternate measure in transportation network evaluation.

Conclusion

This study proposed a novel index to evaluate network robustness of transportation system. The new measure was formulated based on the well-known practical network capacity model. The proposed CNRI was represented by the variation of the total capacity of the transportation system when a single link is completely blocked. Differing from the NRI which utilizes the travel time as the indicator, the CNRI is supposed to be more straightforward to reflect the impact on the system-wide transportation ability. A counter-example was also presented to show the effectiveness of the CNRI. According to the numerical experiments, the CNRI provides distinct solutions to the critical link identification compared to the NRI approach. The comparison also showed that the CNRI can give useful complementary information when the results from the NRI are not significant. The CNRI is suggested to be a necessary option to detect the robustness of transportation system. These conclusions were conducted on the Sioux Falls test network. Future research will focus on the practical applications of the CNRI using real transportation networks. Besides, more characteristics could be studied using different network capacity models with various travelers’ choice behaviors.

Footnotes

Academic Editor: Hai Xiang Lin

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the National Natural Science Foundation of China (nos 51408190, 51508161, and 71501061), the Natural Science Foundation of Jiangsu Province (nos BK20150817 and BK20150821), and the Fundamental Research Funds for the Central Universities (no. 2014B04514).

References

Chen

Yang

Kongsomsaksakul

. Network-based accessibility measures for vulnerability analysis of degradable transportation networks. Netw Spat Econ 2006; 7: 241–256.

Bell

MGH

. A game theory approach to measuring the performance reliability of transport networks. Transport Res B: Meth 2000; 6: 533–545.

Jenelius

Mattsson

L-G.

Road network vulnerability analysis: conceptualization, implementation and application. Comput Environ Urban 2015; 49: 136–147.

Nicholson

AJ.

Degradable transportation systems: sensitivity and reliability analysis. Transport Res B: Meth 1997; 31: 225–237.

Kurauchi

Uno

Sumalee

. Network evaluation based on connectivity vulnerability. In: Lam

WHK

Wong

(eds) Transportation and traffic theory 2009: golden jubilee. New York: Springer, 2009, pp.637–649.

Taylor

MAP

Sekhar

SVC

D’Este

GM.

Application of accessibility-based methods for vulnerability analysis of strategic road networks. Netw Spat Econ 2006; 6: 267–291.

Scott

Novak

Aultman-Hall

. Network robustness index: a new method for identifying critical links and evaluating the performance of transportation networks. J Transp Geogr 2006; 14: 215–227.

Knoop

Snelder

van Zuylen

. Link-level vulnerability indicators for real-world networks. Transport Res A: Pol 2012; 46: 843–854.

Chen

Yang

. Capacity related reliability for transportation networks. J Adv Transport 1999; 33: 183–200.

10.

Chen

Yang

. Capacity reliability of a road network: an assessment methodology and numerical results. Transport Res B: Meth 2002; 36: 225–252.

11.

Chen

Kasikitwiwat

Yang

Alternate capacity reliability measures for transportation networks. J Adv Transport 2013; 47: 79–104.

12.

Wong

Yang

Reserve capacity of a signal-controlled road network. Transport Res B: Meth 1997; 31: 397–402.

13.

Wang

Deng

Zhao

Road network reserve capacity with stochastic user equilibrium. Transport 2015; 6: 103–116.

14.

Chen

Jansuwan

. Modeling transportation network redundancy. Transp Res Proced 2015; 9: 283–302.

15.

Gao

Song

YF.

A reserve capacity model of optimal signal control with user-equilibrium route choice. Transport Res B: Meth 2002; 36: 313–323.

16.

Yang

Bell

MGH

Meng

Modeling the capacity and level of service of urban transportation networks. Transport Res B: Meth 2000; 34: 255–275.

17.

Kasikitwiwat

Chen

Analysis of transportation network capacity related to different system capacity concepts. J East Asia Soc Transp Stud 2005; 6: 1439–1454.

18.

Sullivan

Novak

Aultman-Hall

. Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links: a link-based capacity-reduction approach. Transport Res A: Pol 2010; 44: 323–336.

19.

Oppenheim

Equilibrium trip distribution/assignment with variable destination costs. Transport Res B: Meth 1993; 27: 207–217.

20.

Chen

Kasikitwiwat

Modeling capacity flexibility of transportation networks. Transport Res A: Pol 2011; 45: 105–117.

21.

Friesz

Tobin

Cho

. Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints. Math Program 1990; 48: 265–284.

22.

Cheng

Rakha

Sensitivity analysis of combined distribution-assignment model with applications. Transport Res Rec 2012; 2284: 10–20.

23.

Lundgren

Patriksson

An algorithm for the combined distribution and assignment model. In: Transportation networks recent methodological advances: selected proceedings of 4th Euro transportation meeting, 8 September 1999, pp.239–253. Oxford, UK: Elsevier.

24.

Perederieieva

Ehrgott

Raith

. A framework for and empirical study of algorithms for traffic assignment. Comput Oper Res 2015; 54: 90–107.

25.

Yang

Heuristic algorithms for the bilevel origin-destination matrix estimation problem. Transport Res B: Meth 1995; 29: 231–242.

26.

Jiang

Cheng

Estimating the capacity of urban transportation networks with an improved sensitivity based method. Discrete Dyn Nat Soc 2015; 2015: 827094-1–827094–13.

27.

Bar-Gera

Transportation network test problems, http://www.bgu.ac.il/~bargera/tntp (2001, accessed 6 July 2015).

Alternative network robustness measure using system-wide transportation capacity for identifying critical links in road networks

Abstract

Keywords

Introduction

Index for transportation network robustness

NRI

A counter-example of NRI application

Overview of network capacity models

Models

An sensitivity analysis based solution algorithm

Step 1: Route-based algorithm for the ETDA-VDC model

Initialization

Main loop

Remark 1

Remark 2

Step 3: Local linear approximation procedure

Remark 3

Remark 4

CNRI

Numerical results

A simple example

Sioux Falls network

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References