Large-scale road network vulnerability analysis: a sensitivity analysis based approach

Abstract

Traditionally, an assessment of transport network vulnerability is a computationally intensive operation. This article proposes a sensitivity analysis-based approach to improve computational efficiency and allow for large-scale applications of road network vulnerability analysis. Various vulnerability measures can be used with the proposed method. For illustrative purposes, this article adopts the relative accessibility index (AI), which follows the Hansen integral index, as the network vulnerability measure for evaluating the socio-economic effects of link (or road segment) capacity degradation or closure. Critical links are ranked according to the differences in the AIs between normal and degraded networks. The proposed method only requires a single computation of the network equilibrium problem. The proposed technique significantly reduces computational burden and memory storage requirements compared with the traditional approach. The road networks of the Sioux Falls city and the Bangkok metropolitan area are used to demonstrate the applicability and efficiency of the proposed method. Network manager(s) or transport planner(s) can use this approach as a decision support tool for identifying critical links in road networks. By improving these critical links or constructing new bypass roads (or parallel paths) to increase capacity redundancy, the overall vulnerability of the networks can be reduced.

Introduction

Background

The major role of a transport network is to connect urban centers and provide regional coverage and basic necessities for non-urban areas. A further function is to effectively mitigate the effects of natural and/or man-made disasters. Previous studies on handling uncertainty in transport networks have focused primarily on transport network reliability, which is related to recurrent uncertainty. Transport network reliability can be defined as the ability of a transport network to handle a recurrent variation in demand (Asakura and Kashiwadani 1991), and/or supply (Chen et al. 2002). Various measures of network reliability have been proposed, such as travel time reliability (Bell and Iida 1997), capacity reliability (Chen et al. 2002), and connectivity reliability (Wakabayashi and Iida 1992). Most of these studies rely on the availability of probability information regarding link (or road segment) capacity degradation or failure. However, this information is difficult to obtain accurately in practice. Moreover, the occurrence of a sporadic disaster/incident (either natural or man-made), despite its low probability, often results in a vast socio-economic impact. Therefore, network reliability analysis may not be appropriate for evaluating the effects of sporadic events (D’Este and Taylor 2003).

Vulnerability analysis, initially introduced for road systems by Berdica (2002), is an alternative concept for identifying vulnerable (weak) spots (e.g., links or nodes) in a transport network and assessing the effects of network degradation or failure. An evaluation of network vulnerability does not require the probability of link failure. Vulnerability analysis principally focuses on identifying the critical network components that cause the most adverse impact on network performance as they are failed/degraded. By improving the performance of these critical components, or by adding redundancy into the network capacity, e.g., by constructing new bypass roads or parallel paths, the overall vulnerability of the network can be reduced.

Two streams of vulnerability analysis have been investigated in the transport literature. The first involves devising and improving the definition, framework, and measure of network vulnerability. The second stream is the development of efficient algorithms for evaluating network vulnerability. This paper focuses on the latter. We aim to propose a method for assessing the vulnerability of large-scale road networks based on the application of existing network analysis theory (i.e., sensitivity analysis).

Several studies have investigated large-scale applications of road network vulnerability analysis (see, for example, D’Este and Taylor 2003; Berdica and Mattsson 2007; Jenelius 2009; Taylor et al. 2006; Taylor and D’Este 2007; Taylor 2008). However, computational burden has long been recognized as one of the most challenging issues in this analysis. Traditionally, a measure of road vulnerability is a computationally intensive operation. Each network link is partially degraded or completely closed in turn and the performance of the remaining (degraded) network is evaluated by solving a traffic assignment problem. This method also requires a large memory storage capacity for degraded network files.

Typically, an assessment of network vulnerability can be represented by an implicit relationship between input data—link capacity degradation(s) or link closure(s)—and a change in network performance, such as network travel time, generalized travel costs, or other vulnerability measures. This general idea is similar to the concept of sensitivity analysis (SA). SA has a long history in both non-linear programming and transport network analysis. Various applications of SA have been studied extensively for transport network design problems; e.g., trip matrix estimation (Yang et al. 1992), capacity design problems (Sumalee et al. 2009), and toll design problems (Yang 1997). Despite these applications, few studies of transport network vulnerability analysis have been conducted by using the SA technique.

In general, the SA method explicitly evaluates all derivatives of the equilibrium network flows with respect to the continuous decision variables of the network design problem. However, the directional derivatives of the deterministic user equilibrium (UE) flows may not exist at certain points (Robinson 2006). To avoid this problem, stochastic user equilibrium (SUE) is used in this paper. Two types of SUE models are available: logit and probit models. Although derivatives of the logit-based SUE flows exist everywhere under mild conditions (Ying and Miyagi 2001), the logit-based SUE model cannot represent the correlation of alternative paths within the network. However, the probit-based SUE model, proposed by Daganzo and Sheffi (1977), takes proper account of the natural correlations in the traveler utilities between overlapping paths within the network. Clark and Watling (2002) proposed a computational method for SA of the probit-based SUE under fixed travel demand. Connors et al. (2007) extended the work of Clark and Watling (2002) to the case with variable demand and multiple-user classes.

Aims of the article

This article focuses on the methodological development of vulnerability analysis. The SA technique is applied to improve computational efficiency and allow for large-scale applications of road network vulnerability analysis. The proposed method can be applied to various vulnerability measures. For illustrative purposes, this article simply uses the relative accessibility index (AI), following a normalized form of the Hansen integral accessibility index (Hansen 1959), to assess network vulnerability. The AI under normal network condition (no link capacity degradation/failure) can be calculated directly by using the probit-based SUE flows and costs. The AI under degraded network condition is determined by the first-order Taylor series approximation. Evaluation of all sensitivity derivatives required for the approximation follows the method used in Clark and Watling (2002) and Connors et al. (2007). The difference in accessibility indices between normal and degraded networks is then calculated and used as a measure of link importance. A link with a large decrease in accessibility indices between normal and degraded networks is identified as a critical link. The critical links can be ranked according to their link importance measures.

Note that the AI for a degraded network is approximated by using only the equilibrium flows and costs obtained by a single computation of traffic assignment under a normal network. Thus, the proposed technique significantly reduces the computational time and required memory storage for degraded network files compared with the traditional approach.

The remainder of the paper is outlined as follows. The next section presents the notation and network representation used in this paper. The third section proposes the sensitivity analysis method for the vulnerability analysis. In the fourth section, two road networks are used to demonstrate the applicability and efficiency of the proposed method. The final section concludes the paper and discusses future research issues.

Notation and network representation

Notation

The road network is represented by a directed graph. The following notations are used throughout the paper unless otherwise specified.

G(N, A):

a road network composed by nodes and links;

N :

set of nodes;

A :

set of links;

W :

set of origin to destination (OD) movements;

K ^w :

set of paths connecting the OD movement w;

w :

OD movement index, w ∈ W;

k :

path index, k ∈ K;

a :

link index, a ∈ A;

$\delta_{a,k}^{w}$ :

a link-path incidence indicator, where $\delta_{a,k}^{w} = 1$ if link a is used by path k connecting the OD movement w ∈ W, and $\delta_{a,k}^{w} = 0$ otherwise;

$\Updelta$ :

$\left[ {A \times W} \right]$ block-diagonal link-path incidence matrix, $\Updelta = \left[ {\begin{array}{*{20}c} {\Updelta^{1} } & {\Updelta^{2} } \ldots {\Updelta^{w} } \\ \end{array} } \right]$ where $\Updelta^{w}$ is the [A × K^w] link-path incidence matrix of OD movement w ∈ W and whose components are $\delta_{a,k}^{w}$;

${\mathbf{q}}$ :

$\left[ {W \times 1} \right]$ vector of OD travel demands, ${\mathbf{q}} = \left[ {q^{1} ,q^{2} , \ldots ,q^{w} } \right]^{T}$ where q^w is the travel demand of OD movement w ∈ W;

${\mathbf{f}}$ :

$\left[ {W \times 1} \right]$ block vector of path flows, ${\mathbf{f}} = \left[ {\begin{array}{*{20}c} {{\mathbf{f}}^{1} } & {{\mathbf{f}}^{2} } \ldots {{\mathbf{f}}^{w} } \\ \end{array} } \right]^{T}$ where ${\mathbf{f}}^{w} = \left[ {f_{1}^{w} ,f_{2}^{w} , \ldots ,f_{k}^{w} , \ldots ,f_{{K^{w} }}^{w} } \right]^{T}$ is the $\left[ {K^{w} \times 1} \right]$ vector of flows on the paths serving OD movement w ∈ W and each path flow is $f_{k}^{w} = P_{k}^{w} q^{w}$;

${\mathbf{P}}$ :

$\left[ {W \times 1} \right]$ block vector of path choice probabilities, ${\mathbf{P}} = \left[ {\begin{array}{*{20}c} {{\mathbf{P}}^{1} } & {{\mathbf{P}}^{2} } \ldots {{\mathbf{P}}^{w} } \\ \end{array} } \right]^{T}$ where ${\mathbf{P}}^{w} = \left[ {P_{1}^{w} ,P_{2}^{w} , \ldots ,P_{k}^{w} , \ldots ,P_{{K^{w} }}^{w} } \right]^{T}$ is the $\left[ {K^{w} \times 1} \right]$ vector of probabilities of the paths serving OD movement w ∈ W, i.e., $P_{k}^{w} ,\quad k \in K^{w}$;

${\mathbf{x}}$ :

$\left[ {A \times 1} \right]$ vector of link flows, ${\mathbf{x}} = \left[ {x_{1} ,x_{2} , \ldots ,x_{a} } \right]^{T} ,\quad a \in A$ and this vector can be calculated from ${\mathbf{x}} = \Updelta \cdot {\mathbf{f}} = \sum\limits_{w \in W} {\Updelta^{w} \cdot q^{w} \cdot {\mathbf{P}}^{w} }$;

${\mathbf{y}}$ :

$\left[ {A \times 1} \right]$ vector of average link capacities, ${\mathbf{y}} = \left[ {y_{1} ,y_{2} , \ldots ,y_{a} } \right]^{T} ,\quad a \in A$;

${\mathbf{s}}$ :

$\left[ {A \times 1} \right]$ vector of link capacity degradations, ${\mathbf{s}} = \left[ {s_{1} ,s_{2} , \ldots ,s_{a} } \right]^{T} ,\quad a \in A$;

${\mathbf{t}}$ :

$\left[ {A \times 1} \right]$ vector of link travel times, each element is the function of flow and capacity degradation on that link, ${\mathbf{t}} = \left[ {t_{1} \left( {x_{1} ,s_{1} } \right),t_{2} \left( {x_{2} ,s_{2} } \right), \ldots ,t_{a} \left( {x_{a} ,s_{a} } \right)} \right]^{T} ,\quad a \in A$;

${\mathbf{c}}^{w}$ :

$\left[ {K^{w} \times 1} \right]$ vector of mean travel costs of the paths connecting OD movement w ∈ W. This vector can be determined from ${\mathbf{c}}^{w} = \left( {\Updelta^{w} } \right)^{T} \cdot\,\omega \cdot {\mathbf{t}}$ where ω is the value of time.

This paper assumes that the link travel time functions are monotonically increasing and differentiable everywhere. This assumption ensure that the Jacobian of link travel times with respect to link flows (denoted by $\nabla_{{\mathbf{x}}} {\mathbf{t}}$) is positive definite.

Probit-based stochastic user equilibrium model

In general, travelers neither know precisely nor perceive identically the travel times or costs they will experience on their journeys. This condition implies some forms of stochastic model. In this paper, the probit-based SUE (Daganzo and Sheffi 1977) is used to represent the route choice behavior of travellers. The travel time function of each degradable link is assumed to follow a standard Bureau of Public Roads (BPR) function,

$$ t_{a} \left( {x_{a} ,s_{a} } \right) = t_{a}^{0} + b_{a} \left( {\frac{{x_{a} }}{{y_{a} - s_{a} }}} \right)^{{n_{a} }} ,\quad \forall a \in A $$

(1)

where $t_{a}^{0}$, b _a and n _a are parameters of the BPR function; and s _a is the link capacity degradation incurred by a natural/man-made disaster.

Travelers are assumed to consider only personal travel costs as the disutility of their trips. Then, the perceived travel cost of using path k is

$$ \tilde{c}_{k}^{w} = c_{k}^{w} + \varepsilon_{k}^{w} ,\quad \forall k \in K^{w} ,\quad w \in W $$

(2)

where $c_{k}^{w}$ is the mean path travel cost, which is an element of ${\mathbf{c}}^{w}$, and $\varepsilon_{k}^{w}$ is the perception error of the path travel cost, which is a member of the path travel cost perception error vector (denoted by $\varvec{\varepsilon }^{w}$).

In the probit-based SUE model, $\varvec{\varepsilon }^{w}$ is assumed to follow a multivariate normal distribution with zero mean and variance–covariance matrix $\varvec{\Upsigma}^{w}$. Each stochastic component of $\varvec{\Upsigma}^{w}$ is assumed to have a non-degenerate joint probability density function that is continuous and strictly positive definite. In addition, $\varvec{\Upsigma}^{w}$ must be independent from ${\mathbf{c}}^{w}$. These assumptions are required for calculating the inverse of $\varvec{\Upsigma}^{w}$ in the sensitivity analysis. Note that if $\varvec{\Upsigma}^{w}$ is singular ($\varvec{\Upsigma}^{w}$ is not strictly positive definite), then $\varvec{\Upsigma}^{w}$ is non-invertible. To avoid this scenario, a certain path set should be constructed in advance (Connors et al. 2007).

$\varvec{\Upsigma}^{w}$ can be calculated by using the joint distribution of link travel cost perception errors. This condition allows the correlation of travel cost perception errors on different links in the probit-based SUE model. However, for simplicity, the correlation is neglected in this paper and the travel cost perception error on each link is assumed to follow a normal distribution with zero mean and variance $\sigma_{a}^{2}$. Thus, each component of $\varvec{\Upsigma}^{w}$ can be calculated from

$$ \varepsilon_{k,j}^{w} = \sum\limits_{a \in A} {\delta_{a,k}^{w} } \delta_{a,j}^{w} \sigma_{a}^{2} ,\quad \forall k,j \in K^{w} ,\quad w \in W $$

(3)

where $\varepsilon_{k,j}^{w}$ is the covariance of travel cost perception error between paths k and j. If k = j, then $\varepsilon_{k,j}^{w}$ is equivalent to $\varepsilon_{k}^{w}$ as expressed in Eq. 2. $\varepsilon_{k}^{w}$, which is the variance of travel cost perception error on path k, can be determined from $\varepsilon_{k}^{w} = \sum\nolimits_{a \in A} {\delta_{a,k}^{w} \sigma_{a}^{2} } ,\, \forall k \in K^{w} ,\, w \in W$. In other words, $\varepsilon_{k}^{w}$ are the diagonal elements of $\varvec{\Upsigma}^{w}$.

Travelers on the wth OD movement choosing the kth path are those who perceive the travel cost on this path as the minimum from all possible paths on this OD movement, given the current mean path cost vector ${\mathbf{c}}^{w}$. The corresponding path choice probability is

$$ \begin{gathered} P_{k}^{w} = \Pr \left[ {\tilde{c}_{k}^{w} \le \tilde{c}_{j}^{w} ,\quad \left. {\forall j \in K^{w} } \right|{\mathbf{c}}^{w} } \right] \\ = \Pr \left[ {c_{k}^{w} \left( {t_{a} \left( {x_{a} ,s_{a} } \right)} \right) + \varepsilon_{k}^{w} \le c_{j}^{w} \left( {t_{a} \left( {x_{a} ,s_{a} } \right)} \right) + \varepsilon_{j}^{w} ,\quad \forall j \in K^{w} } \right], \\ \end{gathered} $$

(4)

where $\Pr [.]$ denotes the probability.

There is no closed form for solving the probit path choice probability as defined in Eq. 4. However, several methods can be used to calculate this probability, for example, numerical integration, simulation technique, or analytical approximation.

Following Connors et al. (2007), no inter OD dependence of the path choice probabilities is assumed in this paper. This assumption implies that the path choice probabilities for any OD movement only depend on its own path utilities and do not rely on the utilities experienced by the users on other OD movements, i.e., ${{\partial P_{k}^{w} } \mathord{\left/ {\vphantom {{\partial P_{k}^{w} } {\partial c_{j}^{v} }}} \right. \kern-\nulldelimiterspace} {\partial c_{j}^{v} }} = 0 \quad {\text{for}}\;k \ne j\;{\text{and}}\quad w \ne v.$ Note that the impacts of flows from other OD movements, which share the same sections (i.e., links) of paths, are included in the path travel costs, as an extra delay, of the OD considered.

Based on the above assumption, the Jacobian of the probit path choice probability vector with respect to the mean path cost vector (denoted by $\nabla_{{\mathbf{c}}} {\mathbf{P}}$) has a block diagonal by OD movements, i.e.

$$ \nabla_{{\mathbf{c}}} {\mathbf{P}} = \left[ {\begin{array}{*{20}c} {\nabla_{{{\mathbf{c}}^{1} }} {\mathbf{P}}^{1} } & {} & {\mathbf{0}} \\ {} & \ddots & {} \\ {\mathbf{0}} & {} & {\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w} } \\ \end{array} } \right] \;{\text{where}}\;\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w} = \left[ {\begin{array}{*{20}c} {\frac{{\partial \text{P}_{1}^{w} }}{{\partial c_{1}^{w} }}} & \cdots & {\frac{{\partial \text{P}_{1}^{w} }}{{\partial c_{{K^{w} }}^{w} }}} \\ \vdots & \ddots & \vdots \\ {\frac{{\partial \text{P}_{k}^{w} }}{{\partial c_{1}^{w} }}} & \cdots & {\frac{{\partial \text{P}_{k}^{w} }}{{\partial c_{{K^{w} }}^{w} }}} \\ \end{array} } \right] . $$

(5)

At the SUE condition, no traveler can reduce perceived travel cost by unilaterally changing his/her path. Following Sheffi (1985), the probit-based SUE condition can be formulated as the fixed-point (FP) problem as

$$ {\mathbf{x}} = \sum\limits_{w \in W} {\Updelta^{w} \cdot q^{w} \cdot {\mathbf{P}}^{w} \left( {{\mathbf{c}}^{w} \left( {\mathbf{x}} \right)} \right)} . $$

(6)

In Eq. 6, ${\mathbf{c}}^{w}$ can be derived from the link travel time vector ${\mathbf{t}}$ and further expressed as a function of the link flow vector ${\mathbf{x}}$. Thus, Eq. 6 is the FP problem. Several methods for solving the FP problem of the network equilibrium condition under fixed demand can be found, for example, in Sheffi (1985).

Sensitivity analysis method for vulnerability analysis

Network vulnerability measure

Several measures have been proposed for assessing network vulnerability (Taylor 2008). For illustrative purposes, a relative accessibility index is used in this paper. The accessibility index for each OD movement (denoted by $AI^{w}$) is defined as

$$ \begin{gathered} AI^{w} = \frac{1}{{{\text{Average path travel cost}}^{w} }} \\ = \frac{{q^{w} }}{{\sum\nolimits_{{k \in K^{w} }} {f_{k}^{w} c_{k}^{w} } }},\quad \forall w \in W. \\ \end{gathered} $$

(7)

The index, as expressed in Eq. 7, evaluates the accessibility of OD movement w ∈ W by considering the reciprocal of the average travel cost of the path set K ^w for that OD movement. An OD movement with a large average path travel cost provides low accessibility, and vice versa. An accessibility index for the entire network (denoted by AI) is then defined by the normalized form of the Hansen integral accessibility index (Hansen 1959) as

$$ AI = \frac{{\sum\nolimits_{w \in W} {q^{w} \cdot AI^{w} } }}{{\sum\nolimits_{w \in W} {q^{w} } }} . $$

(8)

Approximation of network accessibility index

Let ${\mathbf{AI}}^{\text{normal}}$ and ${\mathbf{AI}}^{\text{degraded}}$ be the $\left[ {A \times 1} \right]$ vectors of network accessibility indices for normal and degraded networks, respectively. ${\mathbf{AI}}^{\text{normal}}$ can be calculated from ${\mathbf{AI}}^{\text{normal}} = AI^{\text{normal}} \cdot diag\left( {\mathbf{I}} \right)$ where $AI^{\text{normal}}$ is the network accessibility index for the normal network; ${\mathbf{I}}$ is the $\left[ {A \times A} \right]$ identity matrix; and $diag(.)$ denotes the vector with corresponding diagonal matrix entries. Note that $AI^{\text{normal}}$ can be calculated by using Eq. 8 whereas $AI^{w}$ in Eq. 8 can be computed by using the SUE path flows and costs (of a normal network) as the inputs of Eq. 7.

Each element of ${\mathbf{AI}}^{\text{degraded}}$, denoted by $AI_{a}^{\text{degraded}}$, is the network accessibility index of a degraded network due to a capacity reduction on (or closure of) link a ∈ A. ${\mathbf{AI}}^{\text{degraded}}$ can be determined by using the first-order Taylor series approximation,

$$ {\mathbf{AI}}^{\text{degraded}} \approx {\mathbf{AI}}^{\text{normal}} + \left. {\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}} } \right|_{{{\mathbf{s}}_{0} }} \cdot \,\left( {{\mathbf{s}} - {\mathbf{s}}_{0} } \right)^{T} $$

(9)

where $\left. {\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}} } \right|_{{{\mathbf{s}}_{0} }}$ is the Jacobian of ${\mathbf{AI}}^{\text{normal}}$ with respect to ${\mathbf{s}}$ evaluated at ${\mathbf{s}}_{0}$, and ${\mathbf{s}} - {\mathbf{s}}_{0}$ is the difference in link capacity degradations between degraded and normal networks. Note that ${\mathbf{s}}_{0} = {\mathbf{0}}$ because there is no link capacity degradation under a normal network. Thus, Eq. 9 is rewritten as

$$ {\mathbf{AI}}^{\text{degraded}} \approx {\mathbf{AI}}^{\text{normal}} + \left. {\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}} } \right|_{{{\mathbf{s}}_{0} }} \cdot\, {\mathbf{s}}^{T} $$

(10)

In Eq. 10, $\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}}$ can be derived by applying the SA technique. The details are explained later. Once ${\mathbf{AI}}^{\text{normal}}$ and $\left. {\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}} } \right|_{{{\mathbf{s}}_{0} }}$ are obtained, ${\mathbf{AI}}^{\text{degraded}}$ can be calculated. Hence, this approximation method substantially reduces the computational effort compared with the traditional approach. However, the first-order Taylor series approximation is expected to be a reasonable approximation only if $\left| {\mathbf{s}} \right|$, or $\left| {{\mathbf{s}} - {\mathbf{s}}_{0} } \right|$ in general, is small. The accuracy of approximating the accessibility indices by using the first-order Taylor series approximation will be shown in the numerical examples. The proposed method may not be accurate if the link travel time function is highly nonlinear. A higher order(s) of Taylor series expansion should be added to overcome this problem.

Let ${\mathbf{AI}}^{w}$ be the $\left[ {W \times 1} \right]$ vector of OD accessibility indices $AI^{w} ,\, w \in W.$ $\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}}$ in Eq. 10 can be derived by following the definition of network accessibility, as expressed in Eq. 8, and using the chain rule,

$$ \nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}} = \frac{1}{{\sum\nolimits_{w \in W} {q^{w} } }} \cdot {\mathbf{q}}^{T} \cdot \nabla_{{\mathbf{s}}} {\mathbf{AI}}^{w} $$

(11)

where $\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{w}$ is the Jacobian of ${\mathbf{AI}}^{w}$ with respect to ${\mathbf{s}}$, i.e.

$$ \nabla_{{\mathbf{s}}} {\mathbf{AI}}^{w} = \left[ {\begin{array}{*{20}c} {\frac{{\partial AI^{1} }}{{\partial s_{1} }}} & \cdots & {\frac{{\partial AI^{1} }}{{\partial s_{a} }}} \\ \vdots & \ddots & \vdots \\ {\frac{{\partial AI^{w} }}{{\partial s_{1} }}} & \cdots & {\frac{{\partial AI^{w} }}{{\partial s_{a} }}} \\ \end{array} } \right] . $$

(12)

Denote $\nabla_{{\mathbf{s}}} AI^{w}$ as the $\left[ {1 \times A} \right]$ vector, which consists of the wth row components of $\nabla_{{\mathbf{s}}} {\mathbf{AI}}^{w}$ as defined in Eq. 12. $\nabla_{{\mathbf{s}}} AI^{w}$ can be referred to as the gradient of the OD accessibility index, i.e., $AI^{w}$ as defined in Eq. 7, with respect to ${\mathbf{s}}$. $\nabla_{{\mathbf{s}}} AI^{w}$ can be derived by using Eq. 7 and the chain rule,

$$ \nabla_{{\mathbf{s}}} AI^{w} = \frac{{ - q^{w} }}{{\left[ {\left( {{\mathbf{f}}^{w} } \right)^{T} \cdot \,{\mathbf{c}}^{w} } \right]^{2} }}\left\{ {\left( {{\mathbf{f}}^{w} } \right)^{T} \cdot \left[ {\left( {\Updelta^{w} } \right)^{T} \cdot \,\omega \cdot \nabla_{{\mathbf{s}}} {\mathbf{t}}} \right] + \left( {{\mathbf{c}}^{w} } \right)^{T} \cdot \,\left( {q^{w} \cdot \nabla_{{\mathbf{s}}} {\mathbf{P}}^{w} } \right)} \right\}\quad \forall w \in W $$

(13)

In Eq. 13, each diagonal element of $\nabla_{{\mathbf{s}}} {\mathbf{t}}$ is determined from

$$ \frac{{\partial t_{a} }}{{\partial s_{a} }} = n_{a} b_{a} \frac{{\left( {x_{a} } \right)^{{n_{a} }} }}{{\left( {y_{a} - s_{a} } \right)^{{n_{a} + 1}} }} , $$

(14)

whereas all off-diagonal entries of $\nabla_{{\mathbf{s}}} {\mathbf{t}}$ are zero because the link travel time function depends on the flow on that link only, i.e., ${{\partial t_{a} } \mathord{\left/ {\vphantom {{\partial t_{a} } \partial }} \right. \kern-\nulldelimiterspace} \partial }x_{b} = 0$ for a ≠ b and a, b ∈ A. To complete Eq. 13, the Jacobian of probit path choice probabilities ($\nabla_{{\mathbf{s}}} {\mathbf{P}}^{w}$) can be derived by using the SA technique as described below.

Jacobian of probit path choice probabilities

Let $\Uptheta \left( {{\mathbf{P}}^{w} ,{\mathbf{s}}} \right) = {\mathbf{P}}^{w} - {\mathbf{Pr}}\left( {{\mathbf{P}}^{w} \left( {\mathbf{s}} \right),{\mathbf{s}}} \right)$ be the vector of the gap functions of flow probabilities of the paths, connecting OD movement w ∈ W, whose elements are defined in Eq. 4. Denote ${\mathbf{P}}^{w*} \left( {\mathbf{s}} \right)$ as the vector of path choice probabilities at the SUE condition for any given value of ${\mathbf{s}}$, i.e., $\Uptheta \left( {{\mathbf{P}}^{w*} \left( {\mathbf{s}} \right),{\mathbf{s}}} \right) = {\mathbf{0}}$. Assuming that all related functions are differentiable, the first-order Taylor series approximation of $\Uptheta \left( {{\mathbf{P}}^{w} ,{\mathbf{s}}} \right)$, evaluated around the point $\left( {{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} } \right)$, can be expressed as $\Uptheta \left( {{\mathbf{P}}^{w} ,{\mathbf{s}}} \right) \approx \Uptheta \left( {{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} } \right) + \nabla_{{{\mathbf{P}}^{w} }} \left. \Uptheta \right|_{{{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} }} \left( {{\mathbf{P}}^{w} - {\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right)} \right) + \nabla_{{\mathbf{s}}} \left. \Uptheta \right|_{{{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} }} \left( {{\mathbf{s}} - {\mathbf{s}}_{0} } \right)$where $\nabla_{{{\mathbf{P}}^{w} }} \left. \Uptheta \right|_{{{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} }}$ and $\nabla_{{\mathbf{s}}} \left. \Uptheta \right|_{{{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} }}$ are the Jacobian matrices (denoted by ${\mathbf{J}}_{1}$and ${\mathbf{J}}_{2}$) of $\Uptheta \left( {{\mathbf{P}}^{w} ,{\mathbf{s}}} \right)$ with respect to ${\mathbf{P}}^{w}$ and ${\mathbf{s}}$, respectively, evaluated by the solution $\left( {{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} } \right)$. At the equilibrium condition, the approximation of the gap function $\Uptheta \left( {{\mathbf{P}}^{w} ,{\mathbf{s}}} \right)$ becomes ${\mathbf{0}} \approx {\mathbf{0}} + {\mathbf{J}}_{1} \left( {{\mathbf{P}}^{w} - {\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right)} \right) + {\mathbf{J}}_{2} \left( {{\mathbf{s}} - {\mathbf{s}}_{0} } \right)$ and hence

$$ \nabla_{{\mathbf{s}}} {\mathbf{P}}^{w} = \mathop {\lim }\limits_{{{\mathbf{s}} \to {\mathbf{s}}_{0} }} \frac{{\left( {{\mathbf{P}}^{w} - {\mathbf{P}}^{w * } \left( {{\mathbf{s}}_{0} } \right)} \right)}}{{\left( {{\mathbf{s}} - {\mathbf{s}}_{0} } \right)}} = - {\mathbf{J}}_{1}^{ - 1} {\mathbf{J}}_{2} , $$

(15)

with

$$ {\mathbf{J}}_{1} \equiv \nabla_{{{\mathbf{P}}^{w} }} \left. \Uptheta \right|_{{{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} }} = {\mathbf{I^{\prime}}} - \nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w} \cdot \left[ {\left( {\Updelta^{w} } \right)^{T} \cdot \,\omega \cdot \left( {\nabla_{{\mathbf{x}}} {\mathbf{t}} \cdot \nabla_{{{\mathbf{P}}^{w} }} {\mathbf{x}}} \right)} \right] , $$

(16)

$$ {\mathbf{J}}_{2} \equiv \nabla_{{\mathbf{s}}} \left. \Uptheta \right|_{{{\mathbf{P}}^{w*} \left( {{\mathbf{s}}_{0} } \right),{\mathbf{s}}_{0} }} = - \nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w} \cdot \left[ {\left( {\Updelta^{w} } \right)^{T} \cdot \,\omega \cdot \nabla_{{\mathbf{s}}} {\mathbf{t}}} \right] , $$

(17)

where ${\mathbf{I^{\prime}}}$ is the $\left[ {K^{w} \times K^{w} } \right]$ identity matrix; $\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w}$ is the Jacobian of probit path choice probabilities with respect to mean path travel costs; ω is the value of time; $\nabla_{{\mathbf{x}}} {\mathbf{t}}$ is the Jacobian of link travel times with respect to link flows; and $\nabla_{{{\mathbf{P}}^{w} }} {\mathbf{x}}$ is the Jacobian of link flows with respect to path choice probabilities. Note that the path travel cost vector is defined as ${\mathbf{c}}^{w} = \left( {\Updelta^{w} } \right)^{T} \cdot \omega \cdot {\mathbf{t}}$ where each element of ${\mathbf{t}}$ (the link travel time), as defined in Eq. 1, is the function of the link flow (x _a ) and the link capacity degradation (s _a ). x _a , as expressed in Eq. 6, is further defined as the function of probit path choice probability vector (${\mathbf{P}}^{w}$). Following these definitions, the terms in the brackets of Eqs. 16 and 17 are derived by using the chain rule.

In Eqs. 16 and 17, $\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w}$ can be calculated by following the method of Clark and Watling (2002). The details are given in Appendix A.

In Eq. 16, each diagonal element of $\nabla_{{\mathbf{x}}} {\mathbf{t}}$ can be computed from

$$ \frac{{\partial t_{a} }}{{\partial x_{a} }} = n_{a} b_{a} \frac{{\left( {x_{a} } \right)^{{n_{a} - 1}} }}{{\left( {y_{a} - s_{a} } \right)^{{n_{a} }} }}, \quad \forall a \in A $$

(18)

whereas all off-diagonal entries of $\nabla_{{\mathbf{x}}} {\mathbf{t}}$ are zero; and $\nabla_{{{\mathbf{P}}^{w} }} {\mathbf{x}}$ can be calculated from

$$ \nabla_{{{\mathbf{P}}^{w} }} {\mathbf{x}} = \sum\limits_{w \in W} {\Updelta^{w} \cdot q^{w} \cdot {\mathbf{I^{\prime}}}} . $$

(19)

In Eq. 17, $\nabla_{{\mathbf{s}}} {\mathbf{t}}$ can be determined by using Eq. 14. In summary, all derivatives from Eqs. 16–19 are substituted in reverse order to obtain the Jacobian of probit path choice probabilities ($\nabla_{{\mathbf{s}}} {\mathbf{P}}^{w}$) as defined in Eq. 15. As a result, $\nabla_{{\mathbf{s}}} AI^{w}$ can be calculated by using the corresponding Jacobian as the input of Eq. 13.

Critical link identification

For simplicity, the difference in accessibility indices between normal and degraded networks is used as a measure of link importance, i.e.

$$ \Updelta {\mathbf{AI}} = {\mathbf{AI}}^{\text{normal}} - {\mathbf{AI}}^{\text{degraded}} . $$

(20)

By substituting ${\mathbf{AI}}^{\text{degraded}}$ as defined in Eq. 10 into Eq. 20, $\Updelta {\mathbf{AI}}$ is rewritten as

$$ \Updelta {\mathbf{AI}} = - \nabla_{{\mathbf{s}}} {\mathbf{AI}}^{\text{normal}} \cdot {\mathbf{s}}^{T} . $$

(21)

Each element of $\Updelta {\mathbf{AI}}$ is used as a measure of link importance. A link with a large reduction in accessibility indices between normal and degraded networks (each element of $\Updelta {\mathbf{AI}}$) is identified as a critical link. The critical links can then be ranked according to their link importance measures.

Numerical examples

This section demonstrates the applicability and efficiency of the proposed method with the road networks of the Sioux Falls city and the Bangkok metropolitan area. The applicability is assessed by comparing the critical link rankings of the proposed technique and the traditional method. The efficiency is evaluated in terms of the computational time and memory storage (hard disk space) requirements of the two approaches. A personal computer with Intel Core 2 Duo 1.86 GHz CPU, 4 GB RAM, and Windows 7 Ultimate operating system, was used for all tests.

For the tests using the traditional approach, SATURN (Van Vliet and Wright 2006) was used for solving the probit-based SUE under normal and degraded networks. In the probit-based SUE model, the link travel cost perception error is assumed to follow a normal distribution with zero mean and variance $\sigma_{a}^{2} = 0.3 \times t{_{a(0)}^{2}}$. Since the variance of a normal distribution is additive (not the standard deviation), the variance of the link travel cost perception error (i.e., $\sigma_{a}^{2}$) is used for computing the path travel cost perception error ($\varepsilon_{k,j}^{w}$), as defined in Eq. 3. The value of time (ω) is set to 1.00 for all tests. The probit path choice probability ($P_{k}^{w} , \forall k \in K^{w} , w \in W$), as defined in Eq. 4, were achieved by Monte Carlo simulation. The probit-based SUE problem (FP problem), as defined in Eq. 6, is solved by the method of successive averages (MSA) with the maximum number of iterations of 200. Once the equilibrium path flows and costs of normal and degraded networks are obtained, the vector of the differences in AI between normal and degraded networks ($\Updelta {\mathbf{AI}}$) for the traditional approach is then calculated by using Eq. 20.

For the tests using the SA technique, $\Updelta {\mathbf{AI}}$ can be determined by using the equilibrium path flows and travel costs under a normal network as the inputs of Eq. 21. Note that all derivatives in the previous section allow the implementation of the proposed method in any matrix-based mathematical language. MATLAB (MathWorks 2011) is used in this article. The details of all tests are as follows.

Sioux falls road network

The first test is with the Sioux Falls city, a medium-sized road network, as shown in Fig. 1. The network consists of 24 zones, 76 road links, and 528 OD movements. The link travel time function is set to $t_{a} = t_{a}^{0} + b_{a} \left[ {{{x_{a} } \mathord{\left/ {\vphantom {{x_{a} } {\left( {y_{a} - s_{a} } \right)}}} \right. \kern-\nulldelimiterspace} {\left( {y_{a} - s_{a} } \right)}}} \right]^{4} , \forall a \in A$. The OD travel demands and the parameters of the link travel time function are the same as those used in Suwansirikul et al. (1987).

Fig. 1

The Sioux Falls road network

For the traditional approach, the capacity on each link is partially decreased in turn, and the performance of the degraded network is evaluated by solving the probit-based SUE problem. Thus, the traditional approach involves solving the probit-based SUE problem 76 times. In addition, four different levels of link capacity degradations, i.e., 25, 50, 75 and 100% (link closure), and three conditions of network congestion, i.e., free flow, intermediate flow, and highly congested flow, are considered. Therefore, the number of network files generated to assess the accessibility indices under different networks is 76 × 4 × 3 + 1 (normal network) = 913. The traffic assignment problems of all 913 network files are then solved by SATURN. $\Updelta {\mathbf{AI}}$ is then calculated by using Eq. 20.

For the SA approach, 1,306 paths (for the Sioux Falls network) are generated in advance to avoid the non-invertible problem of $\Upsigma^{w}$ in the calculation of $\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w}$, which is not required for the traditional method. The paths are generated by assuming that the OD travel demands are 10 times higher than the original OD travel demands (597 paths). Hence, $\Updelta {\mathbf{AI}}$ for the SA approach is computed by using the equilibrium path flows and costs of the normal network and the generated path set as the inputs of Eq. 21.

Critical links for each approach are identified according to $\Updelta {\mathbf{AI}}$. In this paper, Spearman’s rho (denoted by ρ) (Spearman 1904) is used to determine the relationship of the critical link rankings between the SA method and the traditional approach. Note that Pearson’s coefficient (Pearson 1920) can also be used to evaluate this relationship.

As shown in Fig. 2, under low levels of capacity degradation and network congestion the ranks from both methods are similar, yielding the maximum ρ of 0.9923. As capacity degradation increases, the correlation decreases. For the case with 100% capacity degradation (link closure), the results of ρ are 0.68, 0.59, and 0.43 for low, medium, and high network congestions, respectively. These results become evident that the SA approach can only be expected to be a reasonable approximation if the level of capacity degradation is small. The effect of increasing network congestion is similar to that of increasing capacity degradation. Figure 2 also demonstrates that the SA approach cannot exactly match the critical link ranking of the traditional method, especially with high capacity degradation and network congestion.

Fig. 2

Critical link rankings and Spearman’s ρ between SA and traditional approaches for the Sioux Falls road network

The accuracy of the proposed technique could be improved by introducing a higher-order(s) in the approximation of the SA method. However, for the Sioux Falls network, the SA method takes only 5 s instead of 70 s (the traditional approach). The other advantage of the proposed method is that it does not require large memory storage (i.e., hard disk space) for the degraded network files (913 files) and the SATURN output files storing the equilibrium path flows and costs under different network degradations. Both computational time and memory storage become more critical for large-scale road networks.

Bangkok metropolitan area road network

To highlight the efficiency of the proposed method for large-scale road networks, the second test is with the road network of the Bangkok metropolitan area (BMA) in Thailand. The BMA covers Bangkok and five surrounding provinces (Nonthaburi, Samut Prakan, Pathum Thani, Samut Sakhon, and Nakhon Pathom) with a total area of 7,762 km² and an approximate population of 9,014,470 as of December 31, 2008 (DOPA 2009). The BMA road network, covering freeways, highways, major and minor arterials, and some collectors and local access roads, is shown in Fig. 3. The network consists of 243 zones, 3,296 road links, and 59,049 OD movements. The total travel demand is about one million passenger car equivalent units (pcu) per hour during the morning peak period.

Fig. 3

Bangkok metropolitan area network

For the traditional approach, 3,296 degraded network files (each of them with a single link closure) are generated. The traffic assignment problem is then solved for each degraded network file. $\Updelta {\mathbf{AI}}$ is then calculated by using Eq. 20. Similar to the test with the Sioux Falls network, for the SA approach, 61,593 paths are generated in advance for calculating $\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w}$. In addition, $\Updelta {\mathbf{AI}}$ is determined by using Eq. 21. Critical links of the two approaches are ranked according to their corresponding $\Updelta {\mathbf{AI}}$. Although the critical link rankings of the two approaches are quite different, resulting in a dispersed plot as shown in Fig. 4, Spearman’s ρ is found to be 0.766. This result indicates that the proposed method is also applicable for a large-scale road network.

Fig. 4

Critical link rankings and Spearman’s ρ between SA and traditional approaches for the BMA road network

In Fig. 4, the links in the lower left corner (higher rankings) and the upper right corner (lower ranking) are either the mostly used (lower left corner) or least used (upper right corner) links due to their geographical location. Thus changing the volume and percentage of degradation will not affect much on their rankings. For the links in between these two groups, as they could be easily substituted by other parallel link(s), their importance (ranking) will varies as the distribution of traffic changes with the demand/capacity degradation.

Regarding the efficiency of the proposed method, the computational time can be reduced from 20,779 min or 14.4 days (traditional approach) to 1,239 min or about 1 day (SA approach). However, the ranking correlation of the two approaches is still an issue for the large-scale road network. In general, network manager(s) or transport planner(s) may want to identify some critical or important links (not all critical links in the network) for road maintenance and improvement programs. Information on the exact ranking of the critical links may not be necessary for medium to long term planning. As a trade-off between the exact ranking and computational effort, this paper proposes the shortlist technique to integrate the SA and the traditional approaches.

In the case of the BMA road network, Fig. 5 shows the probability of the critical links obtained by the SA method to be included in the set of top critical links from the traditional approach (true ranking). This probability is calculated by finding the percentage of critical links obtained from the SA method to be included in the list of true critical links found by the traditional approach as same number of top critical links is considered for the two approaches. This probability increases when the larger set of true critical links is considered.

Fig. 5

Probability that critical links from the SA method will be included in the top critical links from the traditional approach

From Fig. 5, if the planner specifies a confidence level of 75%, then about 800 critical links of the SA method are selected as the candidate links. These candidate links are then re-ranked by calculating the actual $\Updelta {\mathbf{AI}}$ based on the traditional approach. By doing so, the computation time is about 3 days (1 day for the SA method and 2 days for the traditional method). The computational time can be reduced further if a smaller confidence level is considered.

Figure 6 shows the top 50 critical links of the BMA road network obtained by the proposed shortlist technique. Most of the top five critical links, Highway no. 4 (Sam Phran), Bang Kruai-Sai Noi road, and Highway No. 9 (Outer ring road), are on the outskirts of the area and serve high travel demands. Besides these links, Ratchadamnoen Nai road, starting from the Grand Palace and along Sanam Luang, also serves high traffic induced by tourism demand around the preserved ancient area of central Bangkok (called Phra Nakhon). This road is the 4th ranked critical link in the whole network. Figure 6 also illustrates that the road segments connecting the bridge across the Chao Phraya River—Krung Thonburi road and Somdet Phra Chao Tak Sin road—are identified as the first and sixth critical links, because there is no alternative path for these roads.

Fig. 6

Top 50 critical links in the BMA road network

The link importance is affected by not only the level of travel demand and the existence of alternative paths, but also the physical factor of the roadway (i.e., road capacity). Figure 7 presents the critical links within the Phra Nakhon area. The Grand Palace and Sanam Luang, in the heart of this area, are surrounded by some of the 101–200th critical links. These links have relatively low capacity due to the space limitation in this area. Also shown in Fig. 7, the Phra Pin-Klao Bridge, located near Sanam Luang, serves the major traffic from the Phra Nakhon area to the left hand side of the Chao Phraya River (called Thonburi). This bridge is identified as the 125th critical link in the network.

Fig. 7

Critical links in the Phra Nakhon area

Conclusion and discussion

This article proposed the SA method to improve computational efficiency and allow for the large-scale application of road network vulnerability analysis. For illustrative purposes, a relative AI was used to measure network vulnerability. For the traditional approach, the AIs for the normal and degraded networks were evaluated by solving a typical traffic assignment. For the proposed method, the difference in AIs between normal and degraded networks, which was used as the measure of link importance, was calculated by using the first-order Taylor series approximation. All derivatives, required for the approximation, were derived in the paper and can be evaluated by using the SA technique. Once the equilibrium path flows and costs under the normal network were obtained, the AI for the degraded network could be approximated. The proposed method substantially reduces the computational burden compared with the traditional approach. Critical links were then ranked according to the differences in the AIs. A link with a large reduction in the difference in the AIs is identified as a critical link.

The proposed method was tested with the road networks of the Sioux Falls city and the Bangkok metropolitan area. For the Sioux Falls road network, with low levels of link capacity degradation and network congestion, the critical link rankings obtained by the two approaches were similar, yielding a correlation coefficient of 0.9923. As capacity degradation and network congestion increased, the correlation decreased. For the Bangkok road network, although the critical link rankings obtained by the two approaches were quite different, the correlation coefficient was 0.766. This result showed the applicability of the proposed technique with a large-scale road network. However, the ranking correlation was still an issue for the large-scale road network. Finally, the shortlist technique was proposed as a trade-off between the exact ranking and computational effort. The technique adopted the SA method to initially find all critical links. Given a specific confidence level for the critical links, the candidate links were selected from the critical links (obtained by the SA approach). These candidate links were re-ranked by using the traditional approach. By doing so, the computational time was reduced to about 3 days instead of about 14 days (the traditional approach). The proposed technique also reduced memory storage requirement.

The proposed technique based on the first-order Taylor series approximation is expected to be a reasonable approximation when the level of capacity degradation is small. The accuracy of critical link ranking should be further improved by introducing higher-order terms in the approximation. The proposed technique can also be extended to consider other vulnerability measures and cases with multiple-user classes and multimodal networks. In the case of the BMA road network, the results of the critical link analysis rely substantially on the definition of the zone and location of centroid connectors in the network. To overcome this problem, a continuum approach should be introduced for transport vulnerability analysis. Queue spillback effect should also be considered in future research.

Appendix A

Since the Jacobian of the probit path choice probability vector with respect to the mean path cost vector ($\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w}$) is symmetric, it is only necessary to determine the upper triangular elements of $\nabla_{{{\mathbf{c}}^{w} }} {\mathbf{P}}^{w}$ by using an approximation method (Clark and Watling, 2002).

For route k connecting the OD movement w, the derivative of the path choice probability ($P_{k}^{w}$) with respect to the cost on an alternative route j ($C_{j}^{w}$), at a given mean path cost vector ${\mathbf{c}}^{w}$ with a variance–covariance matrix $\varvec{\Upsigma}^{w}$, is formulated as

$$ \left. {\frac{{\partial P_{k}^{w} }}{{\partial C_{j}^{w} }}} \right|_{{C = {\mathbf{c}}^{w} }} = \sqrt {\frac{{\left| {\varvec{\Upsigma}^{w} \left( {k,j} \right)} \right|}}{{2\pi \left| {\varvec{\Upsigma}^{w} } \right|}}} \exp \left( {\frac{{A\left( {k,j} \right)}}{2}} \right){\text{MNP}}_{k} \left( {{\mathbf{c}}^{w} \left( {k,j} \right),\varvec{\Upsigma}^{w} \left( {k,j} \right)} \right)\quad k < j;\;k,j \in {\mathbf{K}}^{w}, $$

where ${\mathbf{K}}^{w}$ is the subset of paths connecting the OD movement w; ${\text{MNP}}_{k} \left( {{\mathbf{c}}^{w} \left( {k,j} \right),\varvec{\Upsigma}^{w} \left( {k,j} \right)} \right)$ is the multinomial probit (MNP) choice probability for alternative $k \in {\mathbf{K}}^{w}$ corresponding to a model with N ^w − 1 alternatives (where the original model had $N^{w} = \left| {{\mathbf{K}}^{w} } \right|$ alternatives), mean cost vector ${\mathbf{c}}^{w} \left( {k,j} \right)$ and covariance matrix $\varvec{\Upsigma}^{w} \left( {k,j} \right)$; and the matrix $\varvec{\Upsigma}^{w} \left( {k,j} \right)$, row-vector ${\mathbf{c}}^{w} \left( {k,j} \right)$, and scalar $A\left( {k,j} \right)$ are computed from the following steps (with ${\mathbf{c}}^{w}$ assumed to be in row-vector notation):

Step 1: :

Calculate the inverse covariance matrix $\left( {\varvec{\Upsigma}^{w} } \right)^{ - 1}$ and the row vector ${\mathbf{c}}^{w} \cdot \left( {\varvec{\Upsigma}^{w} } \right)^{ - 1}$.

Step 2::

Form the (N ^w − 1)-square matrix ${\mathbf{D}}\left( {k,j} \right)$ from $\left( {\varvec{\Upsigma}^{w} } \right)^{ - 1}$ by:

(2.1) adding row j of $\left( {\varvec{\Upsigma}^{w} } \right)^{ - 1}$ to row k;

(2.2) adding column j of the resultant matrix from (2.1) to its column k;

(2.3) deleting row j and column j of the resultant matrix from (2.2).

Step 3::

Form the (N ^w − 1) dimensional row vector ${\mathbf{d}}\left( {k,j} \right)$ from ${\mathbf{c}}^{w} \cdot \left( {\varvec{\Upsigma}^{w} } \right)^{ - 1}$, by adding the jth element to the kth element, and then deleting the jth element.

Step 4::

Compute:

$$ \begin{aligned}\varvec{\Upsigma}^{w} \left( {k,j} \right) = \left( {{\mathbf{D}}\left( {k,j} \right)} \right)^{ - 1} , \\ {\mathbf{c}}^{w} \left( {k,j} \right) = {\mathbf{d}}\left( {k,j} \right) \cdot\varvec{\Upsigma}^{w} \left( {k,j} \right),\;{\text{and}} \\ A\left( {k,j} \right) = {\mathbf{d}}\left( {k,j} \right) \cdot\varvec{\Upsigma}^{w} \left( {k,j} \right) \cdot \left( {{\mathbf{d}}\left( {k,j} \right)} \right)^{T} - {\mathbf{c}}^{w} \cdot \left( {\varvec{\Upsigma}^{w} } \right)^{ - 1} \cdot\,\left( {{\mathbf{c}}^{w} } \right)^{T} \\ \end{aligned} $$

Since the Jacobian is symmetry and the choice probabilities must sum to 1, once all the off-diagonal elements have been determined the diagonal terms can be calculated from:

$$ \frac{{\partial P_{k}^{w} }}{{\partial C_{k}^{w} }} = - \sum\limits_{{j \in {\mathbf{K}}^{w} ,j \ne k}} {\frac{{\partial P_{k}^{w} }}{{\partial C_{j}^{w} }}} $$

This approximation method is feasible to apply for large scale networks, where ${\text{MNP}}_{k} \left( {{\mathbf{c}}^{w} \left( {k,j} \right),\varvec{\Upsigma}^{w} \left( {k,j} \right)} \right)$ can be calculated by Monte Carlo methods.