Sensitivity analysis of aggregated variational inequality problems, with application to traffic equilibria

Michael Patriksson^{∗} and R. Tyrrell Rockafellar^{†}

July 10, 2001

Abstract

Some instances of variational inequality models over polyhedral sets can be stated in a disaggregated or aggregated formulation related by an affine variable transformation. For such problems, we establish that sensitivity analysis results under parameterizations rely neither on the strict monotonicity properties of the problem in terms of the disaggregated variables, nor on any particular choice of their values at the solution. We show how to utilize the affine transformation to devise computational tools for calculating sensitivity results, and apply them to the sensitivity analysis of elastic demand traffic equilibrium problems. The results reached show that sensitivity results do not rely on the choice of any particular route or commodity flow solution. Further, the sensitivity analysis, including the calculation of the gradient of the equilibrium link flow, if it exists, can be performed by means of solving linearized traffic equilibrium problems..

Key words: Disaggregated representation; aggregated representation; parameterization; sensitivity analysis; locally Lipschitz function; directional derivative; critical cone; Wardrop; traffic equilibrium.

1 Introduction

The paper concerns the sensitivity analysis of variational problems of the form

−f(ρ, x) ∈ N_{C}(x),  (1)

where ρ ∈ ℜ^{d} is the parameter, x ∈ ℜ^{n} is the solution, f : ℜ^{d} × ℜ^{n} ↦ ℜ^{n} is a smooth function, C ⊆ ℜ^{n} is a nonempty polyhedral set, and N_{C} is the normal cone mapping to C, that is,

N_{C}(x) = \begin{cases}\{ z ∈ ℜ^{n} | z^{T}(x − y) ≤ 0, ∀y ∈ C \}, & x ∈ C, \\ ∅, & x ∉ C. \end{cases}

We focus our attention on the generalized differentiation of the solution mapping

S : ρ ↦ S(ρ) := { x | −f(ρ, x) ∈ N_{C}(x) }  (2)

at a pair (ρ^{∗}, x^{∗}) with x^{∗} ∈ S(ρ^{∗}). We further take a special interest in cases where the problem (1) is generated by problems in a higher-dimensional setting, related by a linear transformation, as follows.

Let D ∈ ℜ^{m} be a nonempty polyhedron, u ∈ ℜ^{m} the solution, φ : ℜ^{d} × ℜ^{m} ↦ ℜ^{m} be smooth, and A : ℜ^{m} ↦ ℜ^{n} be a linear mapping. Consider the problem

−φ(ρ, u) ∈ N_{D}(u),  u ∈ ℜ^{m}.  (3)

If the two problems (1) and (3) are related by

C = A(D),  x = Au,  and  A^{T}f(ρ, A(·)) = φ(ρ, ·),  (4)

∗Department of Mathematics, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden. E-mail:

mipat@math.chalmers.se

†Department of Mathematics, University of Washington, Seattle, WA 98195-4350, USA. E-mail:

rtr@math.washington.edu

we then say that (1) [respectively, (3)] is an aggregated [respectively, disaggregated] representation of the same problem. Note that the linearity of the mapping A implies that C is polyhedral if D is, and vice versa ([RoW98, Proposition 3.55]). Further, in cases where φ(ρ, ·) is monotone, this property is inherited by A^{T}f(ρ, A(·)) ([RoW98, Exercise 12.4]), and, vice versa, if f(ρ, ·) is monotone on C, then φ(ρ, ·) is monotone on D.

The remainder of the paper is organized thus: in the next section we briefly outline the parameterization made, and state a basic sensitivity result for the case of the problem (1). In Section 3, we then utilize the affine transformation in setting up rules for the central components in the sensitivity analysis calculations. A key factor in enabling these calculus rules is that an entity in the aggregated space (such as an element in the normal or tangent cones to C) does not depend on the selection of the element in the corresponding entity in the disaggregated space (such as in the corresponding cones to D).

The possibility to choose either a disaggregated or an aggregated representation is particularly pronounced in applications of variational problems associated with games and transportation, where the vector u may represent a disaggregated representation of the decision-makers, or network flows in terms of individual commodities. The aggregated version of the problem then represents the decisions, or commodities, in some aggregated fashion which allows the problem (3) to be solved through the solution of (1). Section 4 presents one such important application, the (elastic demand) traffic equilibrium problem, in which the mappings φ and f measure the cost of travel at different levels of aggregation, such as on routes or individual links, and their parameterizations may be associated with decisions on the part of society to change the level of service of the traffic infrastructure in order to influence the travellers’ decisions on when, by which mode, and on which route trips will be made. For these problems, the linear transformation described in (4) is a sum, and the corresponding special cases of the sensitivity results of Section 2 are given in the form of corollaries.

In Section 5, we then provide the corresponding results for the sensitivity analysis of traffic equilibria, and establish that the calculations correspond to strictly monotone and affine variational inequality problems that can be solved as special network equilibrium problems. We also give an illustrative example, and compare the results obtained with some previous sensitivity analysis techniques for traffic equilibrium problems. The paper concludes by mentioning some further research work that is currently being conducted.

2 Parameterization and sensitivity analysis

Throughout this paper we will assume, without further reference, that the parameterization is done in such a way that at any (ρ^{∗}, x^{∗}) with x^{∗} ∈ S(ρ^{∗}), the partial Jacobian matrix ∇_{ρ}f(ρ^{∗}, x^{∗}) for f with respect to ρ at (ρ^{∗}, x^{∗}) has full rank; in other words,

rank ∇_{ρ}f(ρ^{∗}, x^{∗}) = n,  ∇_{ρ}f(ρ^{∗}, x^{∗}) ∈ ℜ^{n×d}.  (5)

(In [DoR00, Def. 1.1]), the property (5) is termed ample.) We note that this property can always be enforced, if necessary, through the addition of an additive vector of canonical (dummy) parameters to f. The paper [DoR00] contains a full theory of Lipschitzian properties of the solution mapping ρ ↦ S(ρ) defined in (2), as well as of the graphical geometry associated with its generalized differentiation. For its present use, a small subset of the results obtained therein will suffice. We first recall the concept of proto-derivative: the mapping S is said to be proto-differentiable at ρ^{∗} for x^{∗} when x^{∗} ∈ S(ρ^{∗}) and the difference quotient mappings

Δ_{τ} S(ρ^{∗} | x^{∗}) : ρ′ ↦ τ^{−1}[S(ρ^{∗} + τρ′) − x^{∗}], τ > 0,

converge graphically as τ ↓ 0; in other words, there is a mapping D : ℜ^{d} ↦ ℜ^{n} such that graph Δ_{τ} S(ρ^{∗} | x^{∗}) converges to graph D as τ ↓ 0. (For more details on proto-derivatives, consult [RoW98, Chapter 8].) We also say that a mapping is piecewise polyhedral if its graph is the union of a collection of finitely many polyhedral sets. Further, for a vector z ∈ ℜ^{n}, z^{⊥} := { y ∈ ℜ^{n} | z^{T}y = 0 }.

The following two results were established in [DoR00], as Theorems 7.1 and 7.4.

Theorem 1 (proto-derivatives). Assume that the condition (5) holds. Then S is both graphically Lipschitzian of dimension d and proto-differentiable at ρ^{∗} for x^{∗}, with its proto-derivatives given by an auxiliary variational inequality, namely

DS(ρ^{∗} | x^{∗})(ρ′) = {x′ | r(ρ′, x′) + N_{K}(x′) ∋ 0} ,

where

r(ρ′, x′) := ∇_{ρ}f(ρ^{∗}, x^{∗})ρ′ + ∇_{x}f(ρ^{∗}, x^{∗})x′ and K := T_{C}(x^{∗}) ∩ f(ρ^{∗}, x^{∗})^{⊥}.

Furthermore, the mapping DS(ρ^{∗} | x^{∗}) is itself graphically Lipschitzian of dimension d everywhere, and is piecewise polyhedral.

The set K in the definition of the derivative DS(ρ^{∗} | x^{∗})(ρ′) is known as the critical cone associated with the variational inequality (1) for ρ = ρ^{∗} and x = x^{∗}.

The main interest in the above result is in the special case where S is locally single-valued and Lipschitz continuous, when proto-differentiability turns into something stronger, extending the strong regularity results of Robinson [Rob80]. If S happens to be single-valued and Lipschitz continuous around ρ^{∗} with x^{∗} being the unique element of S(ρ^{∗}), proto-differentiability implies that the mapping DS(ρ^{∗} | x^{∗}) is likewise single-valued and Lipschitz continuous and that

S(ρ) = S(ρ^{∗}) + DS(ρ^{∗} | x^{∗})(ρ − ρ^{∗}) + o(|ρ − ρ^{∗}|),

where o(·) is such that o(t)/t converges to zero as t → 0. This property is known as semi-differentiability (see further [RoW98, Section 7.D]). (This is further ordinary differentiability precisely when DS(ρ^{∗} | x^{∗}), in addition, is linear.

Theorem 2 (semi-differentiability). Assume that the condition (5) holds. Suppose further that S is convex-valued (as it is when f(ρ^{∗}, ·) happens to be monotone) around ρ^{∗}, in the sense that S(ρ) is a convex set for all ρ in some neighbourhood of ρ^{∗}. Then the following properties are equivalent:

(a) S is single-valued and Lipschitz continuous on some neighbourhood of ρ^{∗};

(b) DS(ρ^{∗} | x^{∗}) is single-valued on some neighbourhood of 0^{d} (hence everywhere).

Moreover, then S is semi-differentiable at ρ^{∗} for x^{∗}, and DS(ρ^{∗} | x^{∗}) is not only Lipschitz continuous and positively homogeneous but also piecewise linear.

Suppose now that the situation is as described in Section 1, that is, that the problem (1) is generated through a linear transformation from the disaggregated problem (3). We next establish decomposition formulas providing the sensitivity calculations for (1) to be performed with the aid of data from a solution to the problem (3).

3 Sensitivity analysis for aggregated variational problems

The existence of a sensitivity analysis amounts, by the above theorem, to the local existence of a singlevalued and Lipschitz continuous mapping S. The fact that the problem (1) also has a disaggregated representation and could be described also in terms of the variables u does not alter the analysis in any way; the only point needed to be analyzed is whether the calculation of DS(ρ^{∗} | x^{∗}) can be performed in some disaggregated fashion in terms in the variables u, thereby perhaps facilitating a more efficient sensitivity analysis. This question will be answered through the development of a disaggregated formulation of DS(ρ^{∗} | x^{∗}). To this end, we first derive a disaggregated representation of the critical cone K. The following result is a special case of Theorem 6.43 in [RoW98], but deserves a special proof for polyhedral sets. (A related result was also previously given in [Out97, Lemma 1.1].)

Theorem 3 (cone decomposition). Let x̄ ∈ C, and consider any ū ∈ D with Aū = x̄.

(a) N_{C}(x̄) = { v ∈ ℜ^{n} | A^{T}v ∈ N_{D}(ū) };

(b) T_{C}(x̄) = { w ∈ ℜ^{n} | ∃z ∈ T_{D}(ū) with Az = w } = A(T_{D}(ū)).

Proof. The result in (a) follows from the relations

v ∈ N_{C}(x̄) ⟺ x̄ ∈ arg max_{x∈C} v^{T}x
⟺ ū ∈ arg max_{u∈D} v^{T}Au = arg max_{u∈D} (A^{T}v)^{T}u
⟺ A^{T}v ∈ N_{D}(ū) = (A^{T})^{−1}(N_{C}(x̄)),

where the first is by definition of N_{C}(x̄), the second by the definition of C through the linear mapping A, and the fourth by definition of N_{D}(ū).

For the result in (b), we first note that T_{C}(x̄) = N_{C}(x̄)^{∗}, by polarity. But, on the other hand,

(A(T_{D}(ū)))^{∗} = {v ∈ ℜ^{n} | v^{T}w ≤ 0, w ∈ A(T_{D}(ū))}
= {v ∈ ℜ^{n} | v^{T}Ah ≤ 0, h ∈ (T_{D}(ū))} = {v ∈ ℜ^{n} | (A^{T}v)^{T}h ≤ 0, h ∈ (T_{D}(ū))}
= {v ∈ ℜ^{n} | A^{T}v ∈ (T_{D}(ū)^{∗})} = {v ∈ ℜ^{n} | A^{T}v ∈ (N_{D}(ū))}
= N_{C}(x̄),

by the result in (a). Hence,

T_{C}(x̄) = N_{C}(x̄)^{∗} = A(T_{D}(ū))^{∗∗} = cl A(T_{D}(ū)) = A(T_{D}(ū)),

where the last equality follows since T_{D}(ū) is polyhedral, hence also A(T_{D}(ū)), which then in particular is closed. This completes the proof.

The following result is given in [RoW98, Exercise 6.44]. The result will be used in the context of traffic equilibrium models in the next section.

Corollary 4 (aggregation by sums). Assume further that D = C_{1} × C_{2} × … × C_{r}, where each set C_{i} is a polyhedron in ℜ^{n}, and that A(u_{1}, u_{2}, …, u_{r}) = u_{1} + u_{2} + … + u_{r} with u_{i} ∈ ℜ^{n} for all i, that is, A = (I^{n}, I^{n}, …, I^{n}) and C = ∑_{i=1}^{r} C_{i}. Let x̄ ∈ C and consider any collection of vectors ū_{i} ∈ C_{i} with x̄ = ∑_{i=1}^{r} ū_{i}.

(a) N_{C}(x̄) = { v ∈ ℜ^{n} | v ∈ N_{C_{i}}(ū_{i}) for all i } = ∩_{i=1}^{r}N_{C_{i}}(ū_{i});

(b) T_{C}(x̄) = ∑_{i=1}^{r} T_{C_{i}}(ū_{i}).

In the same context, consider now any v̄ ∈ N_{C}(x̄) and the critical cone T_{C}(x̄) ∩ v̄^{⊥}. Note that for the perturbed problem (1), the corresponding choice is v̄ = −f(ρ^{∗}, x^{∗}). [Obviously, [−f(ρ^{∗}, x^{∗})]^{⊥} = f(ρ^{∗}, x^{∗})^{⊥}.]

Theorem 5 (critical cone decomposition).

T_{C}(x̄) ∩ v̄^{⊥} = A (T_{D}(ū) ∩ (A^{T}v̄)^{⊥}) .  (6)

Proof. Consider any w̄ ∈ T_{C}(x̄) ∩ v̄^{⊥}, and h̄ ∈ T_{D}(ū) with Ah̄ = w̄, as guaranteed by Theorem 3(b). Then,

w̄ ∈ T_{C}(x̄) ∩ v̄^{⊥} ⟺ 0 = v̄^{T}w̄ ≥ v̄^{T}w,  w ∈ T_{C}(x̄)
⟺ 0 = v̄^{T}Ah̄ ≥ v̄^{T}Ah, h ∈ T_{D}(ū)
⟺ 0 = (A^{T}v̄)^{T}h̄ ≥ (A^{T}v̄)^{T}h, h ∈ T_{D}(ū)
⟺ h̄ ∈ T_{D}(ū) ∩ (A^{T}v̄)^{⊥},

where the first equivalence follows by the definition of T_{C}(x̄) and the relation v̄ ∈ N_{C}(x̄) (cf. also [RoW98, Proposition 6.5]), and the second by the definition of the mapping A. (We note that A^{T}v̄ ∈ N_{D}(ū) = T_{D}(ū)^{∗} as guaranteed by Theorem 3(b).)

Corollary 6 (aggregation by sums). In the special case given in Corollary 4,

T_{C}(x̄) ∩ v̄^{⊥} = ∑_{i=1}^{r} (T_{C_{i}}(ū_{i}) ∩ v̄^{⊥}) .

Proof. We note that v̄ ∈ N_{C}(x̄) amounts to v̄ ∈ N_{C_{i}}(ū_{i}) for all i, cf. Corollary 4(a). The result follows then follows from Theorem 5 and Corollary 4.

We shall utilize the above cone decompositions to derive rules of calculus for the sensitivity of traffic equilibria. We first provide an outline of the modelling of such problems.

4 Traffic (Wardrop) equilibrium

Let G = (N , A) be a transportation network, where N and A are the sets of nodes and directed links (arcs), respectively. For certain ordered pairs of nodes, (p, q) ∈ C, where node p is an origin, node q is a destination, and C is a subset of N × N, there are travel demands d_{pq}, given by functions g_{pq}(ρ, ·) : ℜ^{|C|} ↦ ℜ_{+} of the least costs of travel between the nodes p and q given the parameter vector ρ ∈ ℜ^{d}; these functions are nonnegative, upper bounded and continuous on ℜ^{|C|} for each (p, q) ∈ C. We assume that the network is strongly connected, that is, that at least one route joins each origin–destination (OD) pair.

Wardrop’s user equilibrium principle states that for every OD pair (p, q) ∈ C, the travel costs of the routes utilized are equal and minimal for each individual user, and in the elastic context also that the total demand in the OD pair equals the demand function at this least cost, if positive. We denote by R_{pq} the set of simple (loop-free) routes for OD pair (p, q), by h_{pqr} the flow on route r ∈ R_{pq}, and by c_{pqr} := c_{pqr}(ρ, h) the travel cost on the route as experienced by an individual user given the vector h ∈ ℜ^{|R|} of route flows, where |R| denotes the total number of routes in the network; with this notation, an equilibrium flow is defined by the conditions

h_{pqr} > 0 ⟹ c_{pqr} = π_{pq},  r ∈ R_{pq},  (p, q) ∈ C,  (7a)
h_{pqr} = 0 ⟹ c_{pqr} ≥ π_{pq},  r ∈ R_{pq},  (p, q) ∈ C,  (7b)

where the value of π_{pq} := π_{pq}(ρ, h) is the minimal (i.e., equilibrium) route cost in OD pair (p, q). By the nonnegativity of the route flows, the system (7) can more compactly be written as the complementarity system

0^{|R|} ≤ h ⊥ c(ρ, h) − Γπ ≥ 0^{|R|},  (8)

where c(ρ, ·) : ℜ_{+}^{|R|} ↦ ℜ_{++}^{|R|} is the vector of route travel cost functions given the parameter vector ρ ∈ ℜ^{d}, Γ ∈ ℜ^{|R|×|C|} is the route–OD pair incidence matrix (i.e., the element γ_{rk} is 1 if route r joins OD pair k = (p, q) ∈ C, and 0 otherwise), and a ⊥ b, for two arbitrary vectors a, b ∈ ℜ^{n}, means that a^{T}b = 0. The Wardrop conditions state that an equilibrium state is reached precisely when no traveller can decrease his/her travel cost by unilaterally shifting to another route.

The condition that the total demand d_{pq} in the OD pair (p, q) ∈ C equals the demand function at the least cost π_{pq} is stated as follows:

d_{pq} > 0 ⟹ d_{pq} = g_{pq}(ρ, π),  (p, q) ∈ C,
d_{pq} = 0 ⟹ d_{pq} ≥ g_{pq}(ρ, π),  (p, q) ∈ C,

which, similarly to the conditions (7), can be written as a complementarity system as

0^{|C|} ≤ d ⊥ d − g(ρ, π) ≥ 0^{|C|}.  (9)

In order to cast the Wardrop conditions as a variational inequality problem, we need to decide in which space we wish to represent the flows and the flow feasibility requirements. A general form is obtained by describing the set of feasible, aggregate, link flows as the solution in v ∈ ℜ^{|A|} to the linear system

v = V w,  (10a)
W w = d,  (10b)
w ≥ 0^{ℓ},  (10c)

where w ∈ ℜ^{ℓ} is the (disaggregated) vector of the commodity flows, V ∈ ℜ^{|A|×ℓ} is an incidence matrix which describes the aggregation of these flows into a corresponding link flow v ∈ ℜ^{|A|}, and W is an incidence matrix which describes the feasibility requirements with respect to the demand, d, in the commodity flow space.

The most common representation of the Wardrop conditions as a variational inequality problem is in terms of the route flow variables h_{pqr}. We obtain this formulation by identifying w = h, d ∈ ℜ^{|C|} as the vector of each OD pair’s demand, and W = Γ^{T}. In a disaggregated version of the Wardrop conditions, we consider only utilizing the part (10b)–(10c) of the system (10) above, thus describing the (polyhedral) set

H_{d} := { (h, d) ∈ ℜ_{+}^{|R|} × ℜ^{|C|} | Γ^{T}h = d }

of demand-feasible flows. The complementarity conditions (8) and (9) clearly are equivalent to h and d := Γ^{T}h satisfying

−[c(ρ, h) − Γπ, d − g(ρ, π)] ∈ N_{ℜ_{+}^{|R|}}(h) × N_{ℜ_{+}^{|C|}}(d),  (11)

In order to further simplify the problem formulation, we now stipulate that the function −g(ρ, ·) further is strictly monotone on ℜ^{|C|}, whence −g(ρ, ·) is then also maximal ([RoW98, Example 12.7]). The problem (11) can then be written as

[−c(ρ, h), g^{−1}(ρ, d)] ∈ N_{H_{d}}(h, d),  (12)

where g^{−1}(ρ, ·) denotes the single-valued inverse of the demand function g(ρ, ·). To see this directly, note that, together with the feasibility requirement that Γ^{T}h = d must hold, the systems (8) and (9) describe the optimality conditions for (h, d) solving the linear program to minimize c(ρ, h)^{T}y_{h} − g^{−1}(ρ, d)^{T}y_{d} over y = (y_{h}, y_{d}) ∈ H_{d}; utilizing the strict monotonicity of −g(ρ, ·), this is precisely (12).

In the case where the travel cost of a route is the sum of the travel costs on the links defining it (i.e., the route costs are additive), then the above Wardrop conditions can be described in terms of link flows. We then further identify V = Λ in (10a), where Λ ∈ {0, 1}^{|A|×|R|} is the link–route incidence matrix (i.e., the element λ_{ar} equals 1 if route r utilizes link a, and 0 otherwise), and thus the (polyhedral) set of demand-feasible link flows

F̂_{d} := {(v, d) ∈ ℜ^{|A|} × ℜ^{|C|} | ∃(h, d) ∈ H_{d} with v = Λh } .

Then, the problem (11) can be equivalently written as

[−t(ρ, v), g^{−1}(ρ, d)] ∈ N_{F_{d}}(v, d),  (13)

where t(ρ, ·) : ℜ_{+}^{|A|} ↦ ℜ_{++}^{|A|} is the vector of link travel cost functions given the parameter ρ. [The link and route costs are related by c(ρ, h) = Λ^{T}t(ρ, v) = Λ^{T}t(ρ, Λh), for any feasible pair (h, v).]

The set of feasible link flows can also be described by the OD-specific link flows that satisfy the demand for transportation and flow conservation constraints for all the nodes of the network; this is the other popular representation of feasible flows. In the system (10), we then identify W as a block-diagonal matrix with |C| blocks W_{k}, with W_{k} = E, E ∈ {−1, 0, 1}^{|N |×|A|} being the node–link incidence matrix of the network. Further, d is a (|C| · |N |)-vector, with |C| vectors d_{k}, each being a vector of OD-specific demands, stacked on top of each other. (The elements of d_{k} sum to zero.) We also identify w as the (|C| · |A|)-vector of commodity link flows w_{ak}. Hence, (10b)–(10c) corresponds to the commodity-specific flow conservation constraints, giving rise to the set

W_{d} = {(w, d) ∈ ℜ_{+}^{|C|·|A|} × ℜ_{+}^{|C|·|N |}| Ew_{k} = d_{k}, k ∈ C } .

Finally, V is the block-diagonal (|A|×|C|)-matrix (I^{|A|}, I^{|A|}, …, I^{|A|}), which describes the aggregation of the commodity link flows w_{k} into v: v = ∑_{k∈C} w_{k}. Summarizing, then, the system (10) describes the (polyhedral) set of demand-feasible link flows

F_{d} := { (v, d) ∈ ℜ^{|A|} × ℜ^{|C|·|N |} | ∃(w, d) ∈ ℜ_{+}^{|C|·|A|} × ℜ^{|C|·|N |} with v = ∑_{k∈C} w_{k} and Ew_{k} = d_{k} } ,

giving the problem

[−t(ρ, v), g^{−1}(ρ, d)] ∈ N_{F_{d}}(v, d).  (14)

In the present setting, of course, k is identified with an OD pair (p, q) ∈ C, and, further, each vector d_{k} has precisely two nonzeros (so, g^{−1}(ρ, ·) still operates in ℜ^{|C|}). We may, however, let k denote a less disaggregated flow such as flows from different origins, or different vehicle types, etc. The two representations that we have chosen here are in that sense at the two extremes in terms of level of aggregation. We also note that in more generality, we may consider different networks, that is, different matrices E_{k}, for each commodity k, or type k of traffic. This will necessarily also lead to a proper modification of the matrix V above.

Note that the set of link flows in F̂_{d} is included in that of F_{d}, because the latter contains cyclic flows, but due to the positivity assumption on t(ρ, ·) no equilibrium flow will utilize any cyclic flow, so this alternative representation is, in that sense, equivalent.

For further reading on these traffic equilibrium models, consult [Pat94, Nag00].

The connections between the above models and the perturbed systems (1) and (3) are given as follows. For the route–link representation, we can show that (12) corresponds to letting

D = H_{d}; u = (\begin{matrix}h \\ d \end{matrix}); φ(ρ, u) = (\begin{matrix}c(ρ, h) \\ −g^{−1}(ρ, d) \end{matrix})

in the disaggregated system (3), while the aggregated formulation (1) follows from letting

A = (\begin{matrix}Λ & 0^{|A|×|C|} \\ 0^{|C|×|R|} & I^{|C|} \end{matrix}); x = (\begin{matrix}v \\ d \end{matrix}); f(ρ, x) = (\begin{matrix}t(ρ, v) \\ −g^{−1}(ρ, d) \end{matrix}) = f(ρ, Au).  (15)

As has already been shown, φ(ρ, u) = A^{T}f(ρ, Au) also holds.

For the node–link formulation, its disaggregated formulation corresponds to letting

D = W_{d}; u = (\begin{matrix}w \\ d \end{matrix}); φ(ρ, u) = (t(ρ, (I^{|A|}, I^{|A|}, …, I^{|A|})w) ; t(ρ, (I^{|A|}, I^{|A|}, …, I^{|A|})w) ; ⋮ ; t(ρ, (I^{|A|}, I^{|A|}, …, I^{|A|})w) ; −g^{−1}(ρ, d)) ,

while the aggregated formulation (14) follows from letting

A = (\begin{matrix}I^{|A|}, I^{|A|}, …, I^{|A|} & 0^{|A|×|C|} \\ 0^{|C|×|C|·|A|} & I^{|C|} \end{matrix}); x = (\begin{matrix}v \\ d \end{matrix}); f(ρ, x) = (\begin{matrix}t(ρ, v) \\ −g^{−1}(ρ, d) \end{matrix}) = f(ρ, Au). (16)

As above, it is also here possible to establish that φ(ρ, u) = A^{T}f(ρ, Au) holds.

When the travel cost function t(ρ, ·) is strictly monotone on ℜ_{+}^{|A|}, the upper boundedness of the demand function implies the existence of unique demand and link flow solutions (d, v) (e.g., [Pat94, Nag00]). However, it does not follow in general that the equilibrium route flow h is unique, since the matrix Λ in general does not have full rank (that is, many route flows aggregate to the same equilibrium link flow). Seemingly, this fact might preclude the use of sensitivity analysis results, since they in general rely on some form of local single-valuedness of the solution mapping ρ ↦ S(ρ). The main conclusion of this paper is that a sensitivity analysis indeed may be performed, assuming a local uniqueness in the link flow space. The main reason for the concern about the nonuniqueness of route flows can be attributed to the formulation of the problem in the route flow space, while the appropriate space is that of link flows. In fact, the sensitivity analysis results can be stated, and established to be correct, without even providing any explicit representation of these link flows.

5 Sensitivity analysis of traffic equilibria

5.1 The critical cone

The critical cone K = T_{Q}(v^{∗}, d^{∗}) ∩ [t(ρ^{∗}, v^{∗}), −g^{−1}(ρ^{∗}, d^{∗})]^{⊥} (the set Q being either F̂_{d} or F_{d}) is, roughly speaking, the set of feasible flow adjustments (circulations) that, on the aggregate, retain the equilibrium travel costs and demands, and therefore an equilibrium. Indeed, the problem defined in calculating DS(ρ^{∗} | (v^{∗}, d^{∗}))(ρ′) is a multicommodity flow problem, which we now turn to establish.

Theorem 7 (critical cone decomposition for traffic equilibria).

(a) Let (v^{∗}, d^{∗}) be a solution to (13) for a given ρ^{∗}, and h^{∗} an arbitrary vector of consistent equilibrium route flows, that is, v^{∗} = Λh^{∗}. The set K = T_{F_{d}}(v^{∗}, d^{∗}) ∩ [t(ρ^{∗}, v^{∗}), −g^{−1}(ρ^{∗}, d^{∗})]^{⊥} is given by

A {(h′, d′) ∈ ℜ^{|R|} × ℜ^{|C|} | Γ^{T}h′ = d′; h′_{pqr} free if h_{pqr}^{∗} > 0 h′_{pqr} ≥ 0 if h_{pqr}^{∗} = 0 and c_{pqr}(h^{∗}) = π_{pq} h′_{pqr} = 0 if h_{pqr}^{∗} = 0 and c_{pqr}(h^{∗}) > π_{pq} [r ∈ R_{pq}, (p, q) ∈ C] } ,

where A is given in (15).

(b) Let (v^{∗}, d^{∗}) be a solution to (14) for a given ρ^{∗}, and w^{∗} an arbitrary vector of consistent equilibrium commodity link flows, that is, v^{∗} = ∑_{k∈C} w_{k}^{∗}. The set K = T_{F_{d}}(v^{∗}, d^{∗}) ∩ [t(ρ^{∗}, v^{∗}), −g^{−1}(ρ^{∗}, d^{∗})]^{⊥} is given by

A \{(w′, d′) ∈ ℜ^{|C|×|A|} × ℜ^{|C|·|N |} | \begin{matrix}Ew′_{k} = d′_{k} \\ [k ∈ C] \end{matrix}; w′_{ijk} free if w_{ijk}^{∗} > 0 w′_{ijk} ≥ 0 if w_{ijk}^{∗} = 0 and t_{ij}(v^{∗}) = π_{jk} − π_{ik} w′_{ijk} = 0 if w_{ijk}^{∗} = 0 and t_{ij}(v^{∗}) > π_{jk} − π_{ik} [(i, j) ∈ A, k ∈ C] \} ,

where A is given in (16), and where now a link a ∈ A is identified by its origin node i and terminal node j, and where π_{ik} denotes the equilibrium (least) travel cost from the origin node of commodity k ∈ C to the node i ∈ N.

Proof. For the result in (a), we first note that by Corollary 4(b),

T_{F_{d}}(v^{∗}, d^{∗}) = {(v′, d′) ∈ ℜ^{|A|} × ℜ^{|C|} | v′ = Λh′; Γ^{T}h′ = d′; h′_{pqr} free if h_{pqr}^{∗} > 0 h′_{pqr} ≥ 0 if h_{pqr}^{∗} = 0 [r ∈ R_{pq}, (p, q) ∈ C]} .

For any (v′, d′) ∈ T_{F_{d}}(v^{∗}, d^{∗}) it holds that t(ρ^{∗}, v^{∗})^{T}v′ = c(ρ^{∗}, h^{∗})^{T}h′, so

t(ρ^{∗}, v^{∗})^{T}v′ − g^{−1}(ρ^{∗}, d^{∗})^{T}d′ = ∑_{(p,q)∈C} ( ∑_{r∈R_{pq}} c_{pqr}(ρ^{∗}, h^{∗})h′_{pqr} − g_{pq}^{−1}(ρ^{∗}, d^{∗})d′_{pq})

= ∑_{(p,q)∈C} (π_{pq} ( ∑_{r∈R_{pq}} h′_{pqr} − d′_{pq}) + ∑_{r∈R_{pq}} s_{pqr}h′_{pqr})

= ∑_{(p,q)∈C} ∑_{r∈R_{pq}} s_{pqr}h′_{pqr},

where we have defined s_{pqr} := c_{pqr}(ρ^{∗}, h^{∗}) − π_{pq}, r ∈ R_{pq}, (p, q) ∈ C, to be the slack variables in the Wardrop conditions (7). (Also, g_{pq}^{−1}(ρ^{∗}, d^{∗}) denotes the component (p, q) of the inverse demand function g^{−1}(ρ^{∗}, ·) evaluated at d^{∗}.) Obviously, s_{pqr} ≥ 0 always holds, and for the last sum to be zero, it is both necessary and sufficient that h′_{pqr} = 0 holds for routes where h_{pqr}^{∗} = 0 and s_{pqr} > 0. This completes the proof for (a).

The proof for (b) is analogous. First, note that, again by Corollary 4(b),

T_{F_{d}}(v^{∗}, d^{∗}) = \{(v′, d′) ∈ ℜ^{|A|} × ℜ^{|C|·|N |} | v′ = ∑_{k∈C} w′_{k}; \begin{matrix}Ew′_{k} = d′_{k} \\ [k ∈ C] \end{matrix}; w′_{ijk} free if w_{ijk}^{∗} > 0 w′_{ijk} ≥ 0 if w_{ijk}^{∗} = 0 [(i, j) ∈ A, k ∈ C]\} .

The Wardrop conditions (7) take, for the node–link representation, the following form:

0 ≤ w_{ijk} ⊥ t_{ij}(ρ, v) + π_{ik} − π_{jk} ≥ 0,  (i, j) ∈ A, k ∈ C,  (17)

or,

0^{|A|} ≤ w_{k} ⊥ t(ρ, v) − E^{T}π_{k} ≥ 0^{|A|}, k ∈ C.

Now,

t(ρ^{∗}, v^{∗})^{T}v′ − g^{−1}(ρ^{∗}, d^{∗})^{T}d′ = ∑_{(i,j)∈A} ∑_{k∈C} (t_{ij}(ρ^{∗}, v^{∗})w′_{ijk} − g_{k}^{−1}(ρ^{∗}, d^{∗})^{T}d′_{k})

= ∑_{(i,j)∈A} ∑_{k∈C} ((π_{jk} − π_{ik} + s_{ijk})w′_{ijk} − π_{k}^{T}d′_{k})

= ∑_{(i,j)∈A} ∑_{k∈C} s_{ijk}w′_{ijk} + ∑_{k∈C} π_{k} (Ew_{k} − d′_{k})

= ∑_{(i,j)∈A} ∑_{k∈C} s_{ijk}w′_{ijk},

where, as above, s_{ijk} := t_{ij}(ρ^{∗}, v^{∗}) − π_{jk} + π_{ik} ≥ 0, (i, j) ∈ A, k ∈ C, are the slack variables in the Wardrop conditions (17). The above sum is zero if and only if w′_{ijk} = 0 holds for the links (i, j) ∈ A and commodities k ∈ C where w_{ijk}^{∗} = 0 and s_{ijk} > 0. This completes the proof.

The result (a) above was originally established (although in a different presentation) in [QiM89] as a special case of a general result for polyhedral sets having a special representation. The proof made here is however much more direct and intuitive.

A closer look at these critical cones reveals that they define multicommodity flow polyhedra where the flows are further restricted in sign for those commodity flow variables whose value in some equilibrium solution is zero; those variables that happen to define a shortest route in this solution are restricted to be nonnegative, whereas those that are more expensive are restricted to be zero.

Next, the cost mapping r defined for the problem DS(ρ^{∗} | (v^{∗}, d^{∗}))(ρ′) in Theorem 1 here becomes

r(ρ′, (v′, d′)) = (\begin{matrix}∇_{v}t(ρ^{∗}, v^{∗})v′ + ∇_{ρ}t(ρ^{∗}, v^{∗})ρ′ \\ −∇_{d}g^{−1}(ρ^{∗}, d^{∗})d′ − ∇_{ρ}g^{−1}(ρ^{∗}, d^{∗})ρ′ \end{matrix}) ,  (18)

that is, a linearization of the original mapping (t, −g^{−1}) at (ρ^{∗}, v^{∗}, d^{∗}) in the direction of (ρ′, v′, d′). This mapping is affine in (v′, d′), so the problem DS(ρ^{∗} | (v^{∗}, d^{∗}))(ρ′) amounts to solving an affine cost multicommodity flow problem. We next provide sufficient conditions on the original mapping so that the solution to this problem provide the sensitivity analysis sought.

5.2 Sensitivity analysis

Theorem 8 (sensitivity analysis of traffic equilibria). Assume that the condition (5) holds for the problem (13) [or, (14)]. Suppose that, for ρ^{∗} given, the problem (13) [or, (14)] has a solution (v^{∗}, d^{∗}). Suppose further that ρ ↦ t(ρ, ·) [respectively, ρ ↦ −g^{−1}(ρ, ·)] is differentiable at (ρ, v^{∗}) [(ρ, d^{∗})], and monotone [respectively, strictly monotone] on the critical cone K, for every ρ in a neighbourhood of ρ^{∗}. Finally, assume that

s_{v}^{T}∇_{v}t(ρ^{∗}, v^{∗})s_{v} − s_{d}^{T}∇_{d}g^{−1}(ρ^{∗}, d^{∗})s_{d} > 0, s = (\begin{matrix}s_{v} \\ s_{d} \end{matrix}) ∈ K − K \ \{0^{|A|+|C|}\} ,

that is, that the Jacobian of t(ρ^{∗}, ·) [and −g^{−1}(ρ^{∗}, ·)] at (ρ^{∗}, v^{∗}) [(ρ^{∗}, d^{∗})] is positive definite on the critical subspace K − K. Then, the solution mapping S to the problem (13) [and (14)] is single-valued and Lipschitz continuous on some neighbourhood of ρ^{∗} and hence semi-differentiable at ρ^{∗} for (v^{∗}, d^{∗}), while DS(ρ^{∗} | (v^{∗}, d^{∗})) is single-valued everywhere, and hence Lipschitz continuous, positively homogeneous and piecewise linear.

If further, in the Wardrop conditions (7) [respectively, (17)] the slack variables s_{pqr} are strictly positive for every r ∈ R_{pq} and (p, q) ∈ C with h_{pqr}^{∗} = 0 [respectively, s_{ijk} > 0 for every (i, j) ∈ A and k ∈ C with w_{ijk}^{∗} = 0], that is, strict complementarity holds for some disaggregated solution to the equilibrium problem, then the solution mapping S is differentiable at ρ^{∗}, and DS(ρ^{∗} | (v^{∗}, d^{∗})) is linear.

Proof. We establish that the condition (b) in Theorem 2 is satisfied. That the solution set to (13) and (14) is convex-valued follows from the monotonicity of the mappings t(ρ, ·) and −g^{−1}(ρ, ·) on the feasible set K of DS(ρ^{∗} | (v^{∗}, d^{∗}))(ρ′). It is furthermore single-valued by the assumption on the Jacobian of [t(ρ, ·), −g^{−1}(ρ, ·)] being positive definite on the subspace spanned by K. The results, except the last one, then follow from Theorem 2. The last result follows from the observation that under the strict complementarity assumption, K locally changes linearly with (v^{∗}, d^{∗}).

Quite obviously, the first result holds under a continuous differentiability and strong monotonicity assumption on the mapping (v, d) ↦ [t(ρ, v), −g^{−1}(ρ, d)] on the whole space, but this assumption is far from necessary. It is an interesting source for further investigation whether all the common travel time and demand functions will actually fulfill the assumptions of this theorem.

We mention briefly two related results from the literature. In the context of the problem (13), Qiu and Magnanti [QiM89, Theorem 4.1.1] establish that the mapping S is strongly regular in the sense of Robinson [Rob80] (that is, single-valued and locally Lipschitz continuous, hence directionally differentiable since F̂_{d} is polyhedral), at a reference parameter value ρ^{∗}, if, in our setting, (a) in a neighbourhood of (ρ^{∗}, v^{∗}, d^{∗}) [for (v^{∗}, d^{∗}) ∈ S(ρ^{∗})], (ρ, v, d) ↦ [t(ρ, v), −g^{−1}(ρ, d)] is continuous and further Lipschitz continuous with respect to ρ at (v^{∗}, d^{∗}), and differentiable with respect to (v, d) at (v^{∗}, d^{∗}); (b) the condition (18) holds. In order to reach their conclusion, they select a (uniquely determined) representative equilibrium route flow solution by means of solving a strictly convex quadratic projection problem; a process which is unnecessary, as seen above. Their result is stated under slightly milder assumptions, but on the other hand our results are more far-reaching. In particular, our results immediately imply the semismoothness of S, which will enable the use of bundle-type descent approaches in applications to bilevel optimization (see below). (See [PaR00, Pat01] for detailed discussions on this topic, and [Mif77] for a definition of semismoothness.) Outrata [Out97, Proposition 1.2] establishes strong regularity for a wider class of problems, under conditions which here translate to strong monotonicity of the mapping (v, d) ↦ [t(ρ, v), −g^{−1}(ρ, d)] on F̂_{d}, and a condition like (18) but for a larger subspace. A similar result to Outrata’s is also reached independently by Yen [Yen95, Theorem 4.1], where however the parameterized demand is inelastic.

A few final words are now stated on the use of the results of this paper in the solution to bilevel problems in transportation analysis, and their relation to previous analyses in that context. If we consider a minimization in the parameter values ρ over some set P ⊂ ℜ^{d} and for some objective function φ : P × ℜ^{|A|} × ℜ^{|C|} ↦ ℜ ∪ {+∞} of the form φ(ρ^{∗}, v^{∗}, d^{∗}), where (v^{∗}, d^{∗}) is a pair of equilibrium flows and demands given the parameter vector values ρ^{∗}, then we speak of a mathematical program with equilibrium constraints (MPEC) (e.g., [LPR96, OKZ98]). For such problems, having sufficiently strong differentiability properties of the solution mapping S is essential for its efficient solution. Attempts to define descent algorithms for the minimization of φ in the context of transportation analysis have most often been based on either ignoring the possible nondifferentiability of φ due to the nondifferentiability of S, or on heuristic attempts to circumvent the underlying problem of the non-strict complementarity of the equilibrium solutions. One such heuristic is given in [Fri+90], wherein a route flow is heuristically adjusted from an equilibrium to reach a strictly complementary flow. Another strategy stems from [ToF88] (see also, for example, [YaB97, CSF00]), and is based on the calculation of a “derivative” of S through sensitivity information, also involving the choice of a particular representative commodity flow solution consistent with (v^{∗}, d^{∗}). The formulas include quite involved matrix calculations which moreover depend on relations between the number of OD pairs and links to be satisfied in order to even be applicable. Moreover, even if the formula is applicable, it may not yield a value which can be interpreted as a gradient (cf. the example in [Pat01]). In principle, the gradient, if it exists, can instead be obtained from d calculations of the directional derivative along coordinate directions; more efficient means of calculation are interesting to study further. Needless to say, such a strategy need not yield a true derivative unless strict complementarity holds, and further, as we have pointed out already, the sensitivity analysis of traffic equilibrium problems cannot be influenced by making any such particular choice. We mention finally that a descent algorithm which is valid even for nonmonotone travel cost mappings is found in [PaR00].

5.3 An illustrative example

An example problem for the fixed demand version of the problem (13) is found in [QiM89]. In the following, we consider the elastic demand problem (14).

Consider the small-scale traffic network depicted in Figure 1.

For this network, we have the following data:

Link  t_{ij}(ρ, v_{ij})  OD pair g_{pq}(π_{pq})
1: (1, 2) \frac{5}{2} + \frac{5}{2}v_{12} + ρ_{1} 1: (1,4) 44 − 2π_{14}
2: (1, 5) 2 + 4v_{15}  2: (3,5) 55 − 2π_{35}
3: (2, 4) 11 + 2v_{24} + ρ_{2}
4: (2, 5) \frac{5}{2} + \frac{1}{2}v_{25}
5: (3, 1) 3 + 4v_{31}
6: (3, 2) 4 + 8v_{32}
7: (5, 4) 2 + 4v_{54}

Table 1: Network data.

We consider the case where ρ^{∗} = (ρ_{1}^{∗}, ρ_{2}^{∗})^{T} = (0, 0)^{T}, and ρ′ = (2, 1)^{T}, which we can interpret as a case where tolls are to be introduced on the links (1, 2) and (2, 4), the first toll being double the size of

Figure 1: A traffic network.

the second. At ρ^{∗}, then, we have the following solution to the elastic demand traffic equilibrium problem:

v^{∗} = (\begin{matrix}5 \\ 2 \\ 2 \\ 5 \\ 3 \\ 2 \\ 2 \end{matrix}) ,  t(ρ^{∗}, v^{∗}) = (\begin{matrix}5 \\ 10 \\ 15 \\ 5 \\ 15 \\ 20 \\ 10 \end{matrix}) ,  d^{∗} = (\begin{matrix}4 \\ 5 \end{matrix}) ,  π = (\begin{matrix}20 \\ 25 \end{matrix}) .

We remark that the commodity link flow solution is not unique; two possible combinations of commodity flows are:

w_{1}^{∗} = (\begin{matrix}2 \\ 2 \\ 2 \\ 0 \\ 0 \\ 0 \\ 2 \end{matrix}) , w_{2}^{∗} = (\begin{matrix}3 \\ 0 \\ 0 \\ 5 \\ 3 \\ 2 \\ 0 \end{matrix}) ,  and  w_{1}^{∗} = (\begin{matrix}3 \\ 1 \\ 2 \\ 1 \\ 0 \\ 0 \\ 2 \end{matrix}) , w_{2}^{∗} = (\begin{matrix}2 \\ 1 \\ 0 \\ 4 \\ 3 \\ 2 \\ 0 \end{matrix}) .

We note in particular that in the commodity flow solution w^{∗}, link (2, 5) has no flow in the first commodity and link (1, 5) has no flow in the second commodity. However, these links lie on a shortest route from node 1 to node 4, and from node 3 to node 5, respectively. So, w^{∗} is an example of a non-strictly complementary Wardrop solution. The solution w^{∗}, however, is strictly complementary.

The travel cost function t(ρ^{∗}, ·) is affine and separable, and in particular strongly monotone. The same conclusion can be drawn for −g(ρ^{∗}, ·), whence the conditions of the first part of Theorem 8 are fulfilled. We also note that since w^{∗} is strictly complementary, the equilibrium link flow and demand solution is differentiable at ρ^{∗}. (This is true for almost all values of ρ^{∗}. Unfortunately, however, it can not be expected to be true at optimal solutions to an MPEC problem involving an optimization in ρ.) Whether, for a given ρ^{∗}, there exists a strictly complementary solution can be investigated through the solution of an entropy problem, whereby the aggregated solution is distributed over the commodities by means of maximizing the entropy function. If a feasible commodity solution exists, wherein all links lying on a shortest route has a positive flow, then such a flow will be generated. (See [LLPR00] for further details on this entropy problem in the context of the problem (13).)

When setting up the problem DS(ρ^{∗} | (v^{∗}, d^{∗}))(ρ′) we note again that whether we choose w^{∗} or w^{∗}, or any other disaggregated flow consistent with v^{∗}, makes no difference whatsoever to the result in terms of (v′, d′). (Of course, the perturbations will in general not be unique in the commodity space, however.) We here choose to work with w^{∗}. Given this representation of the equilibrium link flow, we obtain the following networks representing the critical cone K given in Theorem 7(b):

Figure 2: Feasible circulation networks for the two commodities.

For this network, we have the differentiated link costs and demand functions given in Table 2. (Note that ∇(g^{−1}) = (∇g)^{−1}.) Due to the separability of the costs and demands, the affine variational problem is equivalent to an optimization problem over K, where the objective is the minimization of

2v′_{12} + \frac{5}{4}(v′_{12})^{2} + 2(v′_{15})^{2} + v′_{24} + (v′_{24})^{2} + \frac{1}{4}(v′_{25})^{2} + 2(v′_{31})^{2} + 4(v′_{32})^{2} + 2(v′_{54})^{2} + \frac{1}{4}(d′_{14})^{2} + \frac{1}{4}(d′_{35})^{2}.

Link  t′_{ij}(v′_{ij}) OD pair g′_{pq}(π′_{pq})
1: (1, 2) 2 + \frac{5}{2}v′_{12} 1: (1,4) −2π′_{14}
2: (1, 5) 4v′_{15}  2: (3,5) −2π′_{35}
3: (2, 4) 1 + 2v′_{24}
4: (2, 5) \frac{1}{2}v′_{25}
5: (3, 1) 4v′_{31}
6: (3, 2) 8v′_{32}
7: (5, 4) 4v′_{54}

Table 2: Network data.

The solution to this problem is as follows:

v′ = (\begin{matrix}−0.6625 \\ 0.0700 \\ −0.5304 \\ −0.1271 \\ −0.0628 \\ 0.0050 \\ 0.0007 \end{matrix}) ,  t′(v′) = (\begin{matrix}0.3438 \\ 0.2800 \\ −0.0607 \\ −0.0636 \\ −0.2513 \\ 0.0400 \\ 0.0028 \end{matrix}) ,  d′ = (\begin{matrix}−0.5297 \\ −0.0578 \end{matrix}) ,  π′ = (\begin{matrix}0.2648 \\ 0.0289 \end{matrix}) ,

and

w′_{1} = (\begin{matrix}−0.4622 \\ −0.0674 \\ −0.5304 \\ 0.0681 \\ 0 \\ 0 \\ 0.0007 \end{matrix}) , w′_{2} = (\begin{matrix}−0.2003 \\ 0.1374 \\ 0 \\ −0.1953 \\ −0.0628 \\ 0.0050 \\ 0 \end{matrix})

is one representative commodity flow adjustment. The result is the expected: d′ is negative in both commodities, meaning that the demand is decreasing, and we see from v′ that flow is not only reduced as a consequence, but also redistributed from the two tolled links (1, 2) and (2, 4), that is, links 1 and 3, to the other links.

6 Further research

The results obtained in this paper have immediate application to solution algorithms for OD estimation or adjustment problems, where sensitivity analysis is used to direct the update of a prior OD matrix. Algorithms previously proposed for this problem (e.g., [Spi90, DrL92, Yan95, CoB00]) can be viewed as heuristic algorithms which use simplifications of the correct formula for the directional derivative of the demand matrix. In a forthcoming paper ([Pat01]), we show how the analysis of this paper can be applied to the sensitivity analysis of fixed demand traffic equilibrium problems with special emphasis on the OD estimation problem, and also show how the sensitivity analysis of stochastic user equilibrium models can be obtained.

References

[CSF00] H.-J. Cho, T. E. Smith and T. L. Friesz, “A reduction method for local sensitivity analyses of network equilibrium arc flows,” Transportation Research, 34B (2000), pp. 31–51.

[CoB00] E. Codina and J. Barceló, “Adjustment of O-D trip matrices from observed volumes: An algorithmic approach based on conjugate directions,” Report, Statistics and Operations Research Department, Polytechnic University of Catalonia, Barcelona, Spain, 2001.

[DoR00] A.L. Dontchev and R.T. Rockafellar, “Ample parameterization of variational inclusions,” Preprint, Department of mathematics, University of Washington, Seattle, WA, 2000.

[DrL92] O. Drissi-Kaïtouni and J. T. Lundgren, “Bilevel origin-destination matrix estimation using a descent approach,” Report LiTH-MAT-R-1992-49, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1992.

[Fri+90] T.L. Friesz, R.L. Tobin, H.J. Cho and N.J. Mehta, “Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints,” Mathematical Programming, 48 (1990), pp. 265–284.

[LLPR00] T. Larsson, J. Lundgren, M. Patriksson and C. Rydergren, “Most likely traffic equilibrium route flows: Analysis and computation,” In: Proceedings, Equilibrium Problems and Variational Problems: International Workshop in Memory of Marino De Luca, Hotel Villa Diodoro, Taormina, Italy, December 3–5, 1998 (to appear).

[LPR96] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.

[Mif77] R. Mifflin, “Semismooth and semiconvex functions in constrained optimization,” SIAM Journal on Control and Optimization, 15 (1977), pp. 959–972.

[Nag00] A. Nagurney, Network Economics: A Variational Inequality Approach, 2nd edition, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000.

[Out97] J.V. Outrata, “On a special class of mathematical programs with equilibrium constraints,” In: P. Gritzmann, R. Horst, E. Sachs, and R. Tichatschke (eds.), Recent Advances in Optimization, Proceedings of the 8th French-German Conference on Optimization, Trier, July 21–26, 1996, Lecture Notes in Economics and Mathematical Systems, vol. 452, Springer-Verlag, Berlin, 1997, pp. 246–260.

[OKZ98] J. Outrata, M. Kočvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.

[Pat94] M. Patriksson, The Traffic Assignment Problem—Models and Methods, Topics in Transportation, VSP BV, Utrecht, The Netherlands, 1994.

[Pat01] M. Patriksson, “Sensitivity analysis of fixed demand traffic equilibria, with application to the OD estimation/adjustment problem,” Report, Department of Mathematics, Chalmers University of Technology, Gothenburg, Sweden, 2001 (forthcoming).

[PaR00] M. Patriksson and R.T. Rockafellar, “A mathematical model and descent algorithm for bilevel traffic management,” Transportation Science (to appear).

[QiM89] Y. Qiu and T.L. Magnanti, “Sensitivity analysis for variational inequalities defined on polyhedral sets,” Mathematics of Operations Research, 14 (1989), pp. 410–432.

[Rob80] S.M. Robinson, “Strongly regular generalized equations,” Mathematics of Operations Research, 5 (1980), pp. 43–62.

[RoW98] R.T. Rockafellar and R.J-B. Wets, Variational Analysis, Grundlehren der mathematischen Wissenschaften, Vol. 317, Springer-Verlag, Berlin, 1998.

[Spi90] H. Spiess, “A gradient approach for the O–D matrix adjustment problem,” Publication CRT-693, Centre de recherche sur les transports, Université de Montréal, Montréal, 1990.

[ToF88] R.L. Tobin and T.L. Friesz, “Sensitivity analysis for equilibrium network flow,” Transportation Science, 22 (1988), pp. 242–250.

[Yan95] H. Yang, “Heuristic algorithms for the bilevel origin–destination matrix estimation problems,” Transportation Research, 29B (1995), pp. 231–242.

[YaB97] H. Yang and M.G.H. Bell, “Traffic restraint, road pricing and network equilibrium,” Transportation Research, 31B (1997), pp. 303–314.

[Yen95] N.D. Yen, “Lipschitz continuity of solutions of variational inequalities with a parametric polyhedral constraint,” Mathematics of Operations Research, 20 (1995), pp. 695–708.