Sensitivity analysis for stochastic user equilibrium traffic assignment with constraints

Abstract

A mathematical programming method for sensitivity analysis of the link-capacitated stochastic user equilibrium model is presented in this article. By the sensitivity matrices, the changes in the network flows can be easily obtained, while some links reach the capacity limits. By link-based stochastic user equilibrium model with link capacity constraints, it is possible to formulate an efficient algorithm for the sensitivity analysis. Two numerical examples are provided for demonstrating the correctness and implementability of the method finally. Since the link capacity is one of the constraints of the model, the method presented here can also be used for the basic model with other constraints.

Introduction

Sensitivity analysis is to analyze the output variables of the model with the change of the input variables. It is important for traffic network equilibrium problems. Knowledge of how sensitive a conclusion is to changes in the network can help to identify which link need to pay more attention. And the information from the sensitivity analysis can also be applied to a variety of control problems, design, and optimal pricing in traffic networks.^1,2

Tobin and Friesz ³ demonstrated the uniqueness properties of a restricted formulation of the deterministic user equilibrium (DUE), and variational inequality method was developed for sensitivity analysis of DUE. Clark and Watling ⁴ presented the mathematical programming method for sensitivity analysis of Probit-based stochastic user equilibrium (SUE) model. Then, in 2001, Ying and Miyagi ⁵ conducted the study on sensitivity analysis of Logit-based SUE model, and the method is developed from a dual formulation of the SUE analysis, and it is more simple and more likely to be accepted relative to the variational inequality method.

Wardrop ⁶ proposed user equilibrium (UE) assignment principle, and the following UE models are too sensitive to traffic cost. SUE assignment was proposed by Daganzo and Sheffi; ⁷ Fisk’s ⁸ model is a general model that unifies Wardropian equilibrium and the concept of the stochastic assignment, and the result of the SUE is more reasonable than UE. Considering in real world, link flow stops increasing when reaching the capacity, and Bell ⁹ did study about Fisk’s model with queues. In this article, we present a mathematical programming method for sensitivity analysis of link-based SUE model with link capacity constraints. ¹⁰ For the basic SUE model avoiding the path enumeration and benefit from it, more efficient algorithm can be developed for SUE assignment. ¹¹

The second section of this article provides a concise review of the link-based SUE model with link capacity constraints. The sensitivity analysis method is formulated in the third section. In the fourth section, we provide two numerical examples for demonstrating the correctness and implementability of the method in detail. Finally, some concluding remarks are summarized in the fifth section.

Link-capacitated SUE model

Let a transportation network G = [N, A], where N and A denote the sets of nodes and links. O and D are the sets of origins and destinations, and we give positive demands $q_{\mathrm{od}}$ for origin–destination (O-D) flows. Let $x_{\mathrm{ij}}$ denote the link flow from node i to j, $C_{\mathrm{ij}}$ denote the link capacity, and $t_{\mathrm{ij}}(x_{\mathrm{ij}})$ denote the travel cost function which is a strictly monotone increasing function, reflecting the relation between cost and flow. $x_{\mathrm{ij}}^o$ is the flow of link $(i,j)\in A$ from $o(o\in O)$ . $\theta$ is the dispersion parameter in the Logit model. ${\delta }_{\mathrm{ok}}$ and ${\delta }_{\mathrm{dk}}$ are switching functions. When k = o(k = d), ${\delta }_{\mathrm{ok}}=1$ $({\delta }_{\mathrm{dk}}=1)$ ; otherwise, ${\delta }_{\mathrm{ok}}=0$ $({\delta }_{\mathrm{dk}}=0)$ .

According to the Logit-type SUE assignment, Akamatsu decomposed the entropy function into link variables, and Ji built the capacitated SUE model as follows^10,11

$$minZ(\mathbf{x})=\sum _{(i,j)\in A}\underset{0}{\overset{x_{\mathrm{ij}}}{\int }}{t}_{\mathrm{ij}}(w)\mathrm{dw}-\frac{1}{\theta }\sum _{o\in O}\{\mathrm{HL}\left({\mathbf{x}}^{\mathbf{o}}\right)-\mathrm{HN}\left({\mathbf{x}}^0\right)\}$$

(1)

$$\begin{array}{l}s.t.h_k\left(x^o\right)={\displaystyle \sum _i{x}_{ik}^o}-{\displaystyle \sum _j{x}_{kj}^o}\hfill \\ +{\displaystyle \sum _d{q}_{od}{\delta }_{ok}-q_{od}}{\delta }_{dk}=0,\forall o\in O,\forall d\in D,\forall k\in N\hfill \end{array}$$

(2)

$$x_{\mathrm{ij}}=\sum _o{x}_{\mathrm{ij}}^o,\forall (i,j)\in A$$

(3)

$$x_{\mathrm{ij}}^o\ge 0,\forall o\in O,\forall (i,j)\in A$$

(4)

$$g_a(\mathbf{x})=C_{\mathrm{ij}}-x_{\mathrm{ij}}\ge 0,\forall (i,j)\in A,\forall a\in A$$

(5)

where we define functions

$$\mathrm{HL}\left({\mathbf{x}}^{\mathbf{o}}\right)=-\sum _{\mathrm{ij}}{x}_{\mathrm{ij}}^o\ln x_{\mathrm{ij}}^o$$

(6)

$$\mathrm{HN}\left({\mathbf{x}}^{\mathbf{o}}\right)=-\sum _j\left(\sum _i{x}_{\mathrm{ij}}^o\right)\ln \left(\sum _i{x}_{\mathrm{ij}}^o\right)$$

(7)

Equation (5) was added to the basic link-based SUE model to limit the increase in the link flows unreality. The equivalent and uniqueness of the model above was proved by Ji et al., ¹⁰ and an effective algorithm for the assignment with constraints was also proposed, so it will not be repeated in this article.

Sensitivity matrices deduced

Let ${\mu }_k$ and $d_a$ be the Lagrangian multipliers for equations (2) and (5), respectively, and $\epsilon$ denotes the perturbations of variables. The Lagrangian function is

$$L(\mathbf{x},\mathbf{\mu },\mathbf{d},\mathbf{\epsilon })=Z(\mathbf{x},\mathbf{\epsilon })+\sum _k{\mu }_k{h}_k({\mathbf{x}}^o,\mathbf{\epsilon })-\sum _a{d}_a{g}_a(\mathbf{x},\mathbf{\epsilon })$$

(8)

From the Kuhn–Tucker conditions, and due to the work by Fiacco, ¹² we define the functions as follows

$$\mathbf{G}=\{\begin{array}{c}\nabla L=0\hfill \\ \multicolumn{1}{c}{d_a{g}_a(\mathbf{x},\mathbf{\epsilon })=0}\\ \multicolumn{1}{c}{h_k({\mathbf{x}}^o,\mathbf{\epsilon })=0}\end{array}$$

(9)

$$\mathbf{y}(\mathbf{\epsilon })=\left[\begin{array}{c}{\mathbf{x}}^o(\mathbf{\epsilon })\hfill \\ \multicolumn{1}{c}{\mathbf{d}\mathbf{(}\mathbf{\epsilon }\mathbf{)}}\\ \multicolumn{1}{c}{\mathbf{u}\mathbf{(}\mathbf{\epsilon }\mathbf{)}}\end{array}\right]$$

(10)

When we get the optimum solution, we obtain

$$\left[\begin{array}{ccc}{\nabla }^2\mathbf{L}\hfill & -\nabla {\mathbf{g}}^{\mathbf{T}}\hfill & \nabla {\mathbf{h}}^{\mathbf{T}}\hfill \\ \multicolumn{1}{c}{\mathbf{d}\nabla \mathbf{g}}& \mathrm{diag}(\mathbf{g})\hfill & 0\hfill \\ \multicolumn{1}{c}{\nabla \mathbf{h}}& 0\hfill & 0\hfill \end{array}\right]{\nabla }_{\mathbf{\epsilon }}\mathbf{y}+\left[\begin{array}{c}{\nabla }_{\epsilon x^o}^2\mathbf{L}\hfill \\ \multicolumn{1}{c}{\mathbf{d}{\nabla }_{\epsilon }\mathbf{g}}\\ \multicolumn{1}{c}{{\nabla }_{\epsilon }\mathbf{h}}\end{array}\right]=0$$

(11)

In equation (11), the “diag” denotes a diagonal matrix with corresponding diagonal entries. We give matrices M and N

$$\mathbf{M}\equiv \left[\begin{array}{ccc}{\nabla }^2\mathbf{L}\hfill & -\nabla {\mathbf{g}}^{\mathbf{T}}\hfill & \nabla {\mathbf{h}}^{\mathbf{T}}\hfill \\ \multicolumn{1}{c}{\mathbf{d}\nabla \mathbf{g}}& \mathrm{diag}(\mathbf{g})\hfill & 0\hfill \\ \multicolumn{1}{c}{\nabla \mathbf{h}}& 0\hfill & 0\hfill \end{array}\right]$$

(12)

$$\mathbf{N}\equiv {[-{\nabla }_{\epsilon x^o}^2{\mathbf{L}}^{\mathbf{T}},-\mathbf{d}{\nabla }_{\epsilon }{\mathbf{g}}^{\mathbf{T}},-{\nabla }_{\epsilon }{\mathbf{h}}^{\mathbf{T}}]}^{\mathbf{T}}$$

(13)

According to equations (11)–(13), we obtain

$${\nabla }_{\mathbf{\epsilon }}\mathbf{y}={\mathbf{M}}^{-1}\mathbf{N}$$

(14)

A first-order approximation of the solution can be obtained as follows

$$\mathbf{y}(\mathbf{\epsilon })=\left[\begin{array}{c}{\mathbf{x}}^o(\mathbf{\epsilon })\hfill \\ \multicolumn{1}{c}{\mathbf{d}\mathbf{(}\mathbf{\epsilon }\mathbf{)}}\\ \multicolumn{1}{c}{\mathbf{u}\mathbf{(}\mathbf{\epsilon }\mathbf{)}}\end{array}\right]=\left[\begin{array}{c}{\mathbf{x}}^o(0)\hfill \\ \multicolumn{1}{c}{\mathbf{d}\mathbf{(}0\mathbf{)}}\\ \multicolumn{1}{c}{\mathbf{u}\mathbf{(}0\mathbf{)}}\end{array}\right]+\left(\mathbf{M}{\left(0\right)}^{-1}\mathbf{N}\left(0\right)\right)\mathbf{\epsilon }+o(||\mathbf{\epsilon }||)$$

(15)

where $o(||\mathbf{\epsilon }||)$ represents a real-valued function, it means that $o(||\mathbf{\epsilon }||)\to 0$ as $\epsilon \to 0$ . We can get new assignment results by the initial flows.

According to equations (1), (6), (7), and (8), we obtain the core elements of the M

$$\begin{array}{l}{\nabla }^{2}L={\left(\frac{{\partial }^{2}L}{\partial x_{ij}^o\partial x_{gh}^o}\right)}_{ij,gh}=\mathrm{diag}{\left({\left(t_{ij}(x_{ij})\right)}_{x_{ij}}\right)}_{ij}\hfill \\ -\frac{1}{\theta }\left(\frac{1}{{\displaystyle \sum _m{x}_{mj}^o}}-\frac{1}{x_{ij}^o}{\delta }_{ij,gh}\right)\hfill \end{array}$$

(16)

where ${\delta }_{\mathrm{ij},\mathrm{gh}}=1$ when link (g, h) is link (i, j), otherwise, ${\delta }_{\mathrm{ij},\mathrm{gh}}=0$ .

Considering the Kuhn–Tucker conditions, the function $d_a{g}_a(x_{\mathrm{ij}})=0$ . When the link flow $x_{\mathrm{ij}}<C_{\mathrm{ij}}$ , $d_a=0$ ; when the link flow $x_{\mathrm{ij}}$ over the link capacity, the method of augmented Lagrangian (ALM) can be used to make the assignment results more reasonable; then, we can obtain $g_a(x_{\mathrm{ij}})=0$ , so the M and N can be transformed as follows

$$\begin{array}{l}M\equiv \left[\begin{array}{ccc}{\nabla }^{2}L\hfill & -\nabla g^T\hfill & \nabla h^T\hfill \\ d\nabla g\hfill & \mathrm{diag}(g)\hfill & 0\hfill \\ \nabla h\hfill & 0\hfill & 0\hfill \end{array}\right]\hfill \\ =\left[\begin{array}{ccc}1\hfill & 0\hfill & 0\hfill \\ 0\hfill & -d\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right]•\left[\begin{array}{ccc}{\nabla }^{2}L\hfill & -\nabla g^T\hfill & \nabla h^T\hfill \\ -\nabla g\hfill & 0\hfill & 0\hfill \\ \nabla h\hfill & 0\hfill & 0\hfill \end{array}\right]\hfill \end{array}$$

(17)

$$\begin{array}{c}\mathbf{N}\equiv \left[\begin{array}{c}-{\nabla }_{\epsilon x^o}^2\mathbf{L}\hfill \\ \multicolumn{1}{c}{-\mathbf{d}{\nabla }_{\epsilon }\mathbf{g}}\\ \multicolumn{1}{c}{-{\nabla }_{\epsilon }\mathbf{h}}\end{array}\right]=\left[\begin{array}{ccc}1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& -\mathbf{d}\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 1\hfill \end{array}\right]•\left[\begin{array}{c}-{\nabla }_{\epsilon x^o}^2\mathbf{L}\hfill \\ \multicolumn{1}{c}{{\nabla }_{\epsilon }\mathbf{g}}\\ \multicolumn{1}{c}{-{\nabla }_{\epsilon }\mathbf{h}}\end{array}\right]\hfill \end{array}$$

(18)

Thus

$${\nabla }_{\mathbf{\epsilon }}\mathbf{y}={\mathbf{M}}^{-1}\mathbf{N}={\left[\begin{array}{ccc}{\nabla }^2\mathbf{L}\hfill & -\nabla {\mathbf{g}}^{\mathbf{T}}\hfill & \nabla {\mathbf{h}}^{\mathbf{T}}\hfill \\ \multicolumn{1}{c}{-\nabla \mathbf{g}}& 0\hfill & 0\hfill \\ \multicolumn{1}{c}{\nabla \mathbf{h}}& 0\hfill & 0\hfill \end{array}\right]}^{-1}•\left[\begin{array}{c}-{\nabla }_{\epsilon x^o}^2\mathbf{L}\hfill \\ \multicolumn{1}{c}{{\nabla }_{\epsilon }\mathbf{g}}\\ \multicolumn{1}{c}{-{\nabla }_{\epsilon }\mathbf{h}}\end{array}\right]$$

(19)

where $\epsilon$ denotes the perturbations of variables, and the sensitivity analysis problem treated here is the small perturbation of the costs and flows, and by our method, the differences between them are reflected by N.

Let ${\gamma }_{\mathrm{od}}$ and ${\lambda }_{\mathrm{ij}}$ denote the perturbation of the travel demands $q_{\mathrm{od}}$ and free-flow link travel time $t_{\mathrm{ij}0}$ when the link cost functions $t_{\mathrm{ij}}(x_{\mathrm{ij}})$ are of the bureau of public roads (BPR) form. We obtain the functions as follows

$$q_{\mathrm{od}}(\gamma )=q_{\mathrm{od}}+{\gamma }_{\mathrm{od}}$$

(20)

$$t_{\mathrm{ij}}(x_{\mathrm{ij}},{\epsilon }_{\mathrm{ij}})=(t_{\mathrm{ij}0}+{\epsilon }_{\mathrm{ij}})[1+0.15{\left(\frac{x_{\mathrm{ij}}}{C_{\mathrm{ij}}}\right)}^4]$$

(21)

We obtain the core elements of the N

$${\nabla }_{\gamma x^o}^{2}L=\frac{\partial \left({\nabla }_{x^o}L\right)}{\partial \mathbf{q}}\frac{\partial \mathbf{q}}{\partial \mathbf{\gamma }}=\frac{\partial \left({\nabla }_{x^o}L\right)}{\partial \mathbf{q}}$$

(22)

$${\nabla }_{\epsilon x^o}^{2}L=\frac{\partial \left({\nabla }_{x^o}L\right)}{\partial \mathbf{\epsilon }}$$

(23)

According to the model, the value of equation (22) is zero. Therefore, the rest can be computed efficiently.

The link-based SUE model represents the SUE assignment as an optimization problem with only link variables; benefit from it, Lee et al. ¹³ developed an efficient algorithm. It gave the CPU times needed by the conventional and modified method for Sioux Falls network; in the case of $\theta =10$ , the modified method performs more than five times faster than the conventional method.

An outline of the procedure for the sensitivity analysis is as follows:

• Step 1. (Initialization) Compute the SUE by the linearization method. ¹³

• Step 2. (Checking the constraints) If the results satisfied, stop and obtain ${x_{\mathrm{ij}}}^o$ and $x_{\mathrm{ij}}$ . Otherwise ALM used to limit the link flows if necessary. ¹⁰

• Step 3. Compute the matrices M and N.

• Step 4. Compute equation (14) or (19). If M cannot inverse for rank defect, giving up the last rows and columns which are uncorrelated with traffic flows can cope.

According to equation (15), we can obtain new assignment results quickly, while some links are closed because of the flows reaching the capacity.

Numerical examples

Example 1. Illustrate our method

It is a network with five nodes and six links which Ying and Miyagi ⁵ used, as shown in Figure 1. The link cost functions are as follows

$$t_{\mathrm{ij}}=({\alpha }_{\mathrm{ij}}+{\epsilon }_{\mathrm{ij}}^{(1)})+({\beta }_{\mathrm{ij}}+{\epsilon }_{\mathrm{ij}}^{(2)})x_{\mathrm{ij}}^4$$

(24)

where ${\epsilon }_{\mathrm{ij}}^{(1)}$ and ${\epsilon }_{\mathrm{ij}}^{(2)}$ denote the uncertainty parameters in the functions. And the values of the parameters are assumed to be

$$\begin{array}{c}{\alpha }_{12}=4,{\alpha }_{14}={\alpha }_{42}=10,{\alpha }_{23}=1,{\alpha }_{25}={\alpha }_{53}=15\hfill \\ {\beta }_{12}=1,{\beta }_{14}={\beta }_{42}=2.5,{\beta }_{23}=30,{\beta }_{25}={\beta }_{53}=0.5\hfill \end{array}$$

Figure 1.

Network of Example 1.

The traffic demand is

$$q_{13}=10+{\gamma }_{13}$$

According to our method, link constraints are added to the basic model, and we give the constraints

$$\begin{array}{l}{C}_{12}\le 6,\mathrm{\hspace{1em}}{C}_{14}\le 5,\mathrm{\hspace{1em}}{C}_{42}\le 5,\hfill \\ C_{23}\le 6,\mathrm{\hspace{1em}}{C}_{25}\le 8,\mathrm{\hspace{1em}}{C}_{53}\le 8\hfill \end{array}$$

For there is one origin in the network, we can obtain $x_{\mathrm{ij}}^o=x_{\mathrm{ij}}$ . With $\theta =0.001$ , the link flows at SUE are

$$\begin{array}{l}{x}_{12}=5.8442,\mathrm{\hspace{1em}}{x}_{14}=x_{42}=4.1558,\hfill \\ x_{23}=3.1598,\mathrm{\hspace{1em}}{x}_{25}=x_{53}=6.8402\hfill \end{array}$$

The Hessian matrix is

$${\nabla }^{2}L=\left[\begin{array}{cccccc}869.5368\hfill & -100\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-100}& 858.3622\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 717.7347\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 4002.296\hfill & -100\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & -100\hfill & 686.2777\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 640.0832\hfill \end{array}\right]$$

For $x_{\mathrm{ij}}<C_{\mathrm{ij}}$ , $\mathbf{d}\nabla \mathbf{g}=0$ , the matrix $\mathrm{diag}(\mathbf{g})$ is $\mathrm{diag}(\mathbf{g})=\mathrm{diag}(0.1558,0.8442,0.8442,2.8402,1.1598,1.1598)$ .

According to equations (2) and (5), $\nabla \mathbf{h}$ and $-\nabla {\mathbf{g}}^{\mathbf{T}}$ can be obtained as follows

$$\nabla h=\left[\begin{array}{cccccc}-1\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 0\hfill & 1\hfill & -1\hfill & -1\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill \\ 0\hfill & 1\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & -1\hfill \end{array}\right],-\nabla g^T=\left[\begin{array}{l}\begin{array}{cccccc}1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\hfill \end{array}\right]$$

Then, according to equations (22) and (23), the matrix N about demand and costs can be obtained. In order to compare it with Ying’s results, the sensitivity matrix is expressed as follows

$$\left[\begin{array}{lll}\frac{\partial x_{12}}{\partial {\gamma }_{13}}\hfill & \frac{\partial x_{12}}{\partial {\epsilon }_{12}^{(1)}}\hfill & \frac{\partial x_{12}}{\partial {\epsilon }_{12}^{(2)}}\hfill \\ \frac{\partial x_{14}}{\partial {\gamma }_{13}}\hfill & \frac{\partial x_{14}}{\partial {\epsilon }_{12}^{(1)}}\hfill & \frac{\partial x_{14}}{\partial {\epsilon }_{12}^{(2)}}\hfill \\ \frac{\partial x_{23}}{\partial {\gamma }_{13}}\hfill & \frac{\partial x_{23}}{\partial {\epsilon }_{12}^{(1)}}\hfill & \frac{\partial x_{23}}{\partial {\epsilon }_{12}^{(2)}}\hfill \\ \frac{\partial x_{25}}{\partial {\gamma }_{13}}\hfill & \frac{\partial x_{25}}{\partial {\epsilon }_{12}^{(1)}}\hfill & \frac{\partial x_{25}}{\partial {\epsilon }_{12}^{(2)}}\hfill \end{array}\right]=\left[\begin{array}{lll}0.6335\hfill & -0.0004\hfill & -0.4409\hfill \\ 0.3665\hfill & 0.0004\hfill & 04409\hfill \\ 0.2580\hfill & 0\hfill & 0\hfill \\ 0.7420\hfill & 0\hfill & 0\hfill \end{array}\right]$$

This matrix agrees with that computed by Ying and Miyagi. Pay attention, when M is rank defect, we can give up the rows and columns which are uncorrelated with flows and costs.

In order to illustrate the method comprehensively, we closed the link (1, 2), and in the model, the constraint for $x_{12}$ changes to $x_{12}\le 5.8442$ . According to the link flows, the value of the element $g_{12}$ is zero, and by equation (19), the sensitivity matrices can be obtained. The new M matrix is

$$\mathbf{M}=\left[\begin{array}{ccccccccccccccccc}869.5368\hfill & -100\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-100}& 858.3622\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 717.7347\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 0\hfill & -1\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 4002.296\hfill & -100\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & -1\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & -100\hfill & 686.2777\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 640.0832\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill & -1\hfill \\ \multicolumn{1}{c}{1}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0.8442\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0.8442\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 2.8402\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1.1598\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1.1598\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{-1}& -1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& 0\hfill & 1\hfill & -1\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 1\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 1\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \end{array}\right]$$

Table 1 shows comparisons of estimated flows by our method with the actual solutions recomputed by the algorithm for capacitated SUE model, and the error between them is very small up to maximum 0.0005.

Table 1.

Traffic flows with small perturbations in Example 1.

Link (i, j)	Unperturbed flows	Perturbed with ${\gamma }_{13}=0.3$
		Actual	Estimated
1–2	5.8442	5.8442	5.8442
1–4	4.1558	4.4558	4.4558
2–3	3.1598	3.2377	3.2372
2–5	6.8402	7.0623	7.0628
		Perturbed with ${\epsilon }_{23}^{(1)}=5$
		Actual	Estimated
1–2	5.8442	5.8442	5.8442
1–4	4.1558	4.1558	4.1558
2–3	3.1598	3.1589	3.1588
2–5	6.8402	6.8411	6.8412

Example 2. A toy-size network example

Solutions of the link-based SUE model are $x_{\mathrm{ij}}^o$ , and we can get the knowledge of where the flows came from. A network with 2 origins, 13 nodes, 19 links, and 4 O-D pairs is considered to verify our method, as shown in Figure 2.

Figure 2.

Network of Example 2.

The link cost functions are of the BPR forms as equation (21), and the unperturbed parameters are assumed to be as in Table 2. Set $\theta =0.01$ , and the traffic demands are

$$q_{0102}=400,q_{0103}=800,q_{0402}=600,q_{0403}=200$$

Table 2.

Network parameters in Example 2.

Link (i, j)	$t_0$	$C_{\mathrm{ij}}$	Link (i, j)	$t_0$	$C_{\mathrm{ij}}$
01–12	9	700	06–10	13	500
01–05	7	900	07–11	9	400
12–06	7	400	08–02	9	700
12–08	14	700	09–10	10	700
04–05	9	700	10–11	6	700
05–06	3	800	11–02	9	700
06–07	5	900	09–13	9	600
07–08	5	300	11–03	8	700
04–09	12	900	13–03	11	700
05–09	9	600

Perturbations of parameters are as follows

$$\begin{array}{c}{\gamma }_{0112}^{01}=20,{\gamma }_{0403}^{04}=10\hfill \\ {\epsilon }_{0112}=1,{\epsilon }_{0610}=-3\hfill \end{array}$$

We can get the initial solutions by the efficiency algorithm and ALM. ¹³ Comparing the estimated flows with what obtained by the algorithm, the errors are small to the flow changes. The “estimation error” equals the actual flows minus the estimated flows.

Because the traffic flows of link (07, 08), link (05, 09), link (07, 11), and link (10, 11) reach the capacity limits, they would not increase by ALM. The same results are derived by the sensitivity analysis method, which verifies the proposed method. To save space, we give the results perturbed simultaneously by a set of parameter uncertainties in Table 3, and good results can be obtained by separate parameter uncertainty.

Table 3.

Traffic flows with a set of small perturbations in Example 2.

Origin-based link flows	Unperturbed flows	Perturbed flows		Estimation error
		Actual	Estimated
$x_{0708}^{01}$	111.1220	112.4524	112.2669	0.1855
$x_{0708}^{04}$	188.8780	187.5476	187.7331	−0.1855
$x_{0509}^{01}$	439.8292	441.1404	443.2542	−2.1138
$x_{0509}^{04}$	160.1708	158.8596	156.7458	2.1138
$x_{0711}^{01}$	268.4733	267.1603	265.7783	1.3820
$x_{0711}^{04}$	131.5267	132.8397	134.2217	−1.3820
$x_{1011}^{01}$	352.6896	352.1348	349.2397	2.8951
$x_{1011}^{04}$	347.3104	347.8652	350.7603	−2.8951
$x_{0112}^{01}$	435.6262	450.2506	449.6580	0.5926
$x_{0105}^{01}$	764.3738	769.7494	770.3420	−0.5926
$x_{0506}^{01}$	324.5446	328.6091	327.0878	1.5213
$x_{1206}^{01}$	300.4644	301.1215	299.7842	1.3373
$x_{0607}^{01}$	379.5953	379.6127	378.0452	1.5675
$x_{1208}^{01}$	135.1617	149.1209	149.8737	−0.7528
$x_{0910}^{01}$	107.2759	102.0169	100.4130	1.6039
$x_{0610}^{01}$	245.4137	250.1179	248.8267	1.2912
$x_{1102}^{01}$	153.7163	158.4186	157.8593	0.5593
$x_{0802}^{01}$	246.2837	261.5814	262.1407	−0.5593
$x_{0913}^{01}$	332.5533	339.1235	342.8413	−3.7178
$x_{1303}^{01}$	332.5533	339.1235	342.8413	−3.7178
$x_{1103}^{01}$	467.4467	460.8765	457.1587	3.7178
$x_{0405}^{04}$	600.8051	603.6127	604.2337	−0.6210
$x_{0506}^{04}$	440.6344	444.7531	447.4881	−2.7350
$x_{0607}^{04}$	320.4047	320.3873	321.9548	−1.5675
$x_{0610}^{04}$	120.2297	124.3658	125.5333	−1.1675
$x_{0910}^{04}$	227.0807	223.4994	225.2270	−1.7276
$x_{0913}^{04}$	132.2849	141.7475	137.2849	4.4626
$x_{1303}^{04}$	132.2849	141.7475	137.2849	4.4626
$x_{1103}^{04}$	67.7151	68.2525	72.7151	−4.4626
$x_{0409}^{04}$	199.1949	206.3873	205.7663	0.6210
$x_{0802}^{04}$	188.8780	187.5476	187.7331	−0.1855
$x_{1102}^{04}$	411.1220	412.4524	412.2669	0.1855

In practice, when roads are closed for heavy traffic, neither the origin-based flows nor the traffic flows would be changed. When the flows are checked, new constraints can be joined to the model, such as $x_{0708}^{01}\le 111.1220$ and $x_{0708}^{04}\le 188.8780$ for $x_{0708}\le 300$ in Example 1. New solutions can be easily obtained by the proposed method.

Conclusion

This article has presented the method for sensitivity analysis of Logit-type SUE assignment model with link capacity constraints. By the method, we can estimate changes in traffic flows quickly and accurately when some roads closed for heavy traffic. Benefit from the link-based basic model, the algorithm for our analysis can be efficient. Since the link capacity is one of the constraints of the model, the method presented here can also be used for the basic model adding other constraints.