Application to the proximal point algorithm to the general traffic assignment problem

27 Congreso Nacional de Estad´ıstica e Investigaci´on Operativa Lleida, 8-11 de abril de 2003 APPLICATION OF THE PROXIMAL POINT ALGORITHM TO THE GENERAL ASYMMETRIC TRAFFIC ASSIGNMENT PROBLEM E. Codina, L. Montero Departamento de Estad´ıstica e Investigaci´on Operativa Universidad Polit´ecnica de Catalu˜na, 08028 Barcelona, Espa˜na E-mail: [email protected] E-mail: [email protected] ABSTRACT An adaptation of the proximal algorithm for the traffic assignment problem under a user equilibrium formulation for a general asymmetric traffic network is presented in this paper, following the recently published results of Pennanen regarding convergence under nonmonotonicity. As is well known the problem can be formulated as a variational inequality and the algorithmic solutions developed uptodate guarantee convergence only under too restrictive conditions which are difficult to appear in practice. In this paper new conditions guaranteing convergence are developed and the possibility of including the algorithm on a bilevel scheme is discussed Keywords: Traffic assignment, variational inequality, proximal point algorithm, Bilevel programming, demand adjustment. AMS Classification: 90C31, 90C59, 90C99, 90B10, 90B30 1. Introduction The traffic assignment problem is one of the core problems in the transportation planning process. Given a transportation network, and certain assumptions of the route choice behaviour of the tripmakers, the problem of traffic assignment is to assign traffic onto the network, so as to fulfill the demands for transportation and to minimize some merit function, based on the behavioural assumption made. Several assumptions on the route choice behaviour have been made. However, the most natural assumption is that each driver chooses the shortest perceived route to his/her destination under prevailing traffic conditions. The result from a generalized decision like that made by all the travelers yields a situation in which no driver can reduce 1 his/her journey time by choosing another route. This is the user optimal criteria for route choice. Wardrop (1952) was the first to state this route choice criteria. The asymmetric traffic assignment problem (i.e. when there are link flow interactions on the link travel costs) was first formulated as a variational inequality problem by Smith (1979b) and a number of algorithms emerged to solve the resulting formulation and basically the convergence of all them required at least the strong monotonicity of the link travel costs. The proximal point method of Martinet (1970) and its application by Rockafellar in order to develop the method of proximal multipliers has been the subject of many researchers that have applied it on a variety of problems. The recent work of Pennanen (2002) has shown that this methods present local convergence under some weaker conditions that the ones stated on previous works. On the other hand, updating an obsolete origin and destination matrix of trips within a transportation area, using available information, is a very common problem in traffic and transportation planning. For traffic networks, a source of information of a relatively moderate cost are traffic counts on a subset of links of the traffic network. The paper is organized as follows. Following this paragraphs in the introduction a subsection for the basic formulations and notation used to described the user equilibrium in an asymmetric traffic network. In section 2, the formulation as a variational inequality is developed reproducing already known results mainly due to Smith (1979b) as well as conditions for existence and uniqueness of solutions. In section 3 the convergence conditions of many algorithms to solve the variational inequality formulations of the traffic assignment problem are revisited (linearization methods, projecton methods and diagonalization methods and simplicial decomposition methods). Section number 4 describes the recently developed convergence conditions for the proximal point algorithm for inclusions due to Pennanen (2002). His results basically state that the convergence can be even if the application map of the inclusion is hypomonotone, while up to date conditions ensured convergence only under maximal monotonicity conditions. In section number 5 the application of the proximal point algorithm is shown for the case of the demand adjustment problem formulated as a bilevel program in which the lower level (the traffic assignment problem) is formulated as a variational inequality in which the link travel costs are strongly monotone. 1.1 Formulations The development of general cost functions was due to the unrealistic assumption that the travel time on a link is independent of the flow on other links. One just has to imagine traffic near a turning intersection or a narrow two-way street to realize this. One reason for the late development of models incorporating more general cost functions may be the difficulty of catching a realistic cost relationship. Consider the Wardrop’s user equilibrium, as it is discussed by authors as Smith and Heydecker in references Smith (1979b) and Heydecker (1986): A traffic distribution is a Wardrop equilibrium when no driver has a less costly alternative route. 2 Assume a transportation network Gwith a single mode of transit and a fix demand D. Consider a specific origin destination pair (i, j) and Rij the set of available paths joining OD pair (i, j). The route flow vector hinduces flows vaon each link a∈A given by the expression, va=X (i, j)∈C X r∈Rij δar hijr (1) where δar = 1 if link a belongs to path r; and δar = 0 otherwise. In words, vais the sum of flows hijr on all paths r, over all OD pairs (i, j). Let vdenote the vector of arc flows and let ∆denote the link path incident matrix. Then in vector form, link flows and path flows are related by the following expression v=∆ h Let each unit of flow on link aincur a travel cost ca(v) which depends upon the vector vof link flows in the network. In the separable traffic assignment problem, the cost on a link depends solely upon the flow vaon that link, in which case it usually increases with increased levels of the link flow. If we now assume that the cost on any path of the network, as a function of path flows, is the sum of travel costs on the links of that path, then Cijr =X a∈A δar ca(va) We refer to this form of route costs as an additive model. Stating this relationship more compactly in vector form, we obtain C(h) = ∆>c(v), where >denotes transposition. In this expression, C(h) = ( Cijr(h) ) is a vector-valued function specifying the travel costs on each path rand c(v)=(v) is a vector valued function whose components specify the link travel costs. The route travel costs Cijr(h) on each route rjoining an OD pair (i, j) defines the least travel cost uij over all paths joining that OD pair. This is uij ≡min r∈Rij Cijr (h) These least travel costs certainly provide a reference point against which to measure any route’s ability to attract trips. If different routes are used for a given OD pair (i, j), the travel cost of the routes used is uij, and Wardrop’s equilibrium may be rewritten as hijr >0⇒Cijr =uij hijr = 0 ⇒Cijr ≥uij 3 or equivalently as hijr ·(Cijr −uij) = 0 ∀r∈Rij ;∀(i, j)∈C (2) Cijr −uij ≥0∀r∈Rij ;∀(i, j)∈C (3) X r∈ Rij hijr =dij ∀(i, j)∈C (4) hijr ≥0∀r∈Rij ;∀(i, j)∈C (5) uij ≥0∀(i, j)∈C (6) 2. Variational Inequality Formulation [TAP-VI] Wardrop conditions for the general traffic assignment model can be reformulated into three main types of equivalent problems: variational inequality formulations, (Smith (1979b), Dafermos (1980) (1982), Florian and Spiess (1982)), nonlinear complementary formulations (Aashtiani and Magnanti (1981)) and fixed point formulations ( Asmuth 1978 and Fisk and Nguyen (1980)). The variational inequality formulations have become very popular, due to the large literature devoted to VIP , compacteness for writing and flexibility in choosing the ground set X. Theorem 1.1 Wardrop conditions for user equilibrium are equivalent to the following variational inequality formulation, defining the general traffic assignment problem [TAP-VI] , Find h∈ H s. t. C(h)>(h−h)≥0∀h∈ H (7) and Hdef ={h|X r∈Rij hijr =dij,hijr ≥0,∀r∈Rij ,∀(i, j)∈C } (8) It should be noted that the variational inequality formulation [TAP-VI] is independent of the form of the cost functions Cijr(h), this is, the travel cost on a route need not be additive. The additivity property is used in our formulations and is assumed to hold when developing algorithmic approaches. There are two main reasons for this: 1. Under the non additive assumption there does not exist a transformation of the above arc route formulation of [TAP-VI] in terms of arc flows. 2. On working with large networks, as our case, the arc route formulations of traffic assignment models involves very large scale problems, and as far as, it is unknown if an efficient algorithm could be designed for solving large general problems, it has been preferred to remove the extra size due to the route flow model and concentrate efforts on solving the aggregated arc flow model. 4 We state the arc flow variational inequality formulation for the traffic assignment problem when travel costs on a route satisfy the additivity property. This formulation is studied below and serves as the basis for developing algorithms to compute equilibrium solutions to [TAP-VI] . Find v∗∈ V s. t. c(v∗)>·(v−v∗)≥0∀v∈V (9) and Vdef ={v|va=X (i, j)∈C X r∈Rij δar hijr ∀a∈A ,h∈H } (10) Smith (1979b) discusses the properties of equilibrium solutions and formulates the problem [TAP-VI] for both the arc node case and the arc route case for additive route costs. Dafermos (1980) develops an equivalent finite dimensional variational inequality formulation. Formulations for the elastic case have been proposed by Dafermos and Florian. Dafermos and Nagurney develop an arc flow formulation, equivalent to the above model, and study the stability and sensitivity of equilibria, based on that formulation. In this point we introduce the primal and dual gap functions GP(x) and GD(x) for [TAP-VI] . GP(v) = −min w∈V c(v)>·(w−v) (11) GD(w) = −max v∈V c(v)>·(w−v) (12) The primal gap function may be interpreted in this context as the difference of total travel costs between the current flow vand the shortest route flow z. Thus a positive gap function corresponds to a potential benefit for some travelers in adjusting their route choices. On the other hand, G(v) = 0 precisely when no traveler has an incentive to change route, that is, when the flow satisfies Wardrop conditions of equilibria. Viewing the gap function in terms of an error in Wardrop conditions, Hearn suggests the use of this formulation even in the separable case, since the objective function of its mathematical formulation is rather artificial. Algorithms based on primal gap function are given Hearn (1982); methods based on simplicial descomposition are given by Lawphongpanich and Hearn (1984), Marcotte and Guelat (1988) and Pang and Yu (1984). Cutting plane methods are given by Nguyen and Dupuis (1984) and Hearn and Lawphongpanich (1989). Now, we present conditions for the existence and uniqueness of the variational inequality formulation [TAP-VI] . Although they are, in the traffic equilibrium context, essentially equivalent, the existence results presented differ. It seems that too strong assumptions have sometimes been put on the model when establishing the existence of a solution, mainly because these conditions serves to validate the proposed algorithms as well. We recall that sufficient conditions for the existence of a solution to VIP , where based on: 5 •Boundedness of the feasible set. •Sufficient monotonicity of the mapping defining the problem. The feasible set in the traffic assignment problem is, in general, not bounded, due to the existence of cycles in the network. Anyway, we can ensure the existence of a solution to [TAP] , by restricting the cost functions c(v) or Cijr(h) to be strictly positive for all feasible flows. The implication of this is that an optimal solution cannot include cyclic flows and the variables can therefore be restricted as follows, 0≤va≤X (i, j)∈C dij,∀a∈A Lawphongpanich and Hearn (1984) consider for [TAP-VI] how the original problem can be replaced by restricted problems over sets of simple or loop-free routes. In convergence results or existence and uniqueness results, boundness it is always assumed. Existence and uniqueness results listed below are extracted from Aashtiani and Magnanti (1981) and Smith (1979b). The graph Gis assumed to be strongly connected, i.e., that there exists at least one route connecting each origin and destination. The problem [TAP-VI] has an equilibrium solution v(∗)under one of the following conditions: 1. Under additive cost model and c(v) continuous, positive and dij ≥0 (Aashtiani and Magnanti). 2. Under additive cost model and c(v) continuous, nonnegative and the feasible set closed and convex (Smith). 3. Under nonadditive cost model and C(h) continuous, positive and dij ≥0 (Aashtiani and Magnanti). Uniqueness results are similar to those obtained for the separable case, where strictly increasing condition on ca(va) is substituted by the condition of strictly monotonicity of c(v). Results listed below proceed from the same sources mentioned before: 1. Under additive cost model and c(v) continuous, nonnegative, strictly monotone and the feasible set closed and convex, the equilibrium link flow solution v(∗) is unique (Smith.) 2. Under additive cost model and c(v) continuous, positive, strictly monotone and dij ≥0, the link flow volumes v(∗)and the accessibility vector uare unique (Aashtiani and Magnanti.) Observe that the results require that the vector c(v) of cost functions be strictly monotone in terms of link volumes v, not in terms of path flows h. Path flows need not to be unique, since two collections of path flows might correspond to the same link flows. 6 3. Convergence conditions for [TAP - VI] algorithms The first methods applied to the general finite dimensional variational inequality problem were based on fixed point problem reformulations, but for large scale problems, these algorithms are impractical, due to the large memory requirements, and their failure to utilize problem structure. Efficient methods for VIP may be grouped into the following methodology classes: •Linearization methods. They are based on iterative approximation of the mapping defining VIP by affine mappings at the current point. •Diagonalization methods. Similar to the algorithms proposed for solving equations: Extensions of Jacobi, Gauss-Seidel and Newton methods. •Simplicial Decomposition methods. •Dual cutting plane methods. These methods apply to solving the maximization of the dual gap function, which it is equivalent to solving [TAP-VI] . Convergence results require strict monotonicity and the set of feasible arc flows to be a compact polyhedron. •Gap descent Newton method. Essentially, the method generates a sequence such that each iterate is the solution to a variational inequality problem involving a linear approximation of the functional cost at the previous iterate, whose solution is used to define a descent direction to the gap function. Monotonicity and continuous differentiability of the functional cost are required for global convergence results. 3.1 Linearization Methods Several variants are described in reports, but all of them can be cast as special cases of the following scheme: Algorithm. Given x(t)∈X, let x(t+1) solve the variational inequality subproblem VI(f(t),X), where f(t)(x) is some mapping approximating the original f(x) at the point x(t). Presumably, each subproblem VI(f(t),X) is numerically easier to solve than the original problem VI(f,X). A linearization method is based on an iterative approximation of f(x) on the current iteration point x(t), called f(t)(x) The method is classified as a linear approximation method if f(t)(x) is of the form f(x)∼f(t)(x) = c+A(t)x where A(t)is a constant matrix at iteration tand c=ρf(ˆx)−A(t)ˆx for ˆx∈Xand ρ > 0. 7 Included in the family of linear approximation methods are: Newton method. The mapping f(x) is assumed to be differentiable and A(t)=∇f(x(t)). The linear approximation is in this case the first order Taylor expansion of f(x) around x(t). Quasi-Newton methods. A(t)is taken to be an approximation to the Jacobian matrix ∇f(x(t)). Linear SOR methods. Successive overrelaxation methods in which the matrix A(t)is taken to be A(t)=(L(t)+D(t)/ω∗ U(t)+D(t)/ω∗0< ω∗<2 Assuming L(t),U(t)and D(t)are respectively the strictly lower and upper triangular parts and diagonal of ∇f(x(t)). When ω∗is taken to be 1, the scheme becomes the linearized Gauss-Seidel method. Linear Jacobi method. The matrix A(t)is taken to be the diagonal of the Jacobian matrix at the current point, i.e., A(t)= Diag(∇f(x(t))). Projection methods. The matrix A(t)is taken to be a fixed symmetric and positive definite matrix Gequal for all iterations t. Although a fast local convergence is ensured for Newton’s method, the problem VI(f(t),X) is not trivial, and the affine variational inequality defined is not equivalent to a mathematical program, since ∇f(x) is, in general, assymetric. Quasi-Newton methods have been proposed with an approximation matrix chosen to be symmetric, to ensure that the variational inequality defined is equivalent to a mathematical programming program. SOR methods lead to decomposition of the original subproblem into independent problems. The reason why methods in the last category are termed projection methods is due to the following geometrical interpretation of the iterates {x(t)}. Indeed, it is easy to show that if the set Xis closed and convex and if A(t)=1 γGis symmetric and positive definite, then the vector x(t+1) that solves the subproblem VI(f(t),X) is the projection of the point x(t)−γG−1f(x(t)) onto the set Xwhere the projection is defined with respect to the G-norm, i. e., x(t+1) =PrG X³x(t)−γG−1f(x(t))´ where for a given vector z,PrG X(z) is the unique vector solving the mathematical programming program min kz−ykG s. t. y∈X and kxkG= (x>G x)1 2 is the G-norm of the vector x. 8 3.2 Projection methods Projection methods are easily converted to mathematical programming equivalents. A projection algorithm for solving VIP sets A(t)=1 γG, for all t, where Gis an arbitrary symmetric and positive definite matrix. The projection algorithm is defined by the iterative formula x(t+1) =PrG X³x(t)−γG−1f(x(t))´t= 1,2,··· (13) Each iteration tis equivalent to a quadratic mathematical programming program stated as, x(t+1) = min y∈X 1 2kx(t)−γG−1f(x(t))−yk2 G(14) defining the projection of the point x(t)−γG−1f(x(t)) onto the feasible set Xaccording to the metric k · kG. The quadratic program is a special case of affine variational inequalities. Let us define the function H(·) as H(y) = 1 2kx(t)−γG−1f(x(t))−yk2 G∀y∈X Then, according to the correspondence between a convex program (derived from the positive definiteness of matrix G) and the optimality conditions, x(t+1) solves the quadratic program if and only if x(t+1) satisfies local minima condition (that are sufficient conditions for global minimum in convex programming) ∇H(x(t+1))>(y−x(t+1))≥0∀y∈X or equivalently, (f(x(t)) + 1 γG(x(t+1) −x(t)))>(y−x(t+1))≥0∀y∈X or equivalently, f(t)(x(t+1))>(y−x(t+1))≥0∀y∈X At this point the equivalence between a mathematical program and an specific affine variational inequality has been shown. It is interesting to note, that any linearization method formerly described can be viewed as a projection algorithm with variable metric; the metric is defined by the approximation matrix A(t)defined at each iteration t, provided the matrices are symmetric and positive definite. The projection algorithm with variable metric is equivalent to the following iterative statement: x(t+1) =PrA(t) X³x(t)−(A(t))−1f(x(t))´t= 1,2,· · · (15) In fact, it is not easy to solve the quadratic program equivalent to the affine variational inequality for [TAP-VI] and the convergence of a pure fix projection method is very poor. Most linearization algorithms applied to [TAP-VI] have been proposed 9 be transformed in the following one: Min(v, g)∈ΩH(v, g) + µ` 2kg−g`k2 2 s.t. G(v, g)=0 (31) Being G(v, g) a gap function for the variational inequality (26) parametrized by g. This function must verify the conditions: G(v, g) = 0 if v∈ V∗(g),for g≥0 G(v, g)>0 if v∈Ω− V∗(g),for g≥0(32) The primal and dual gap functions GP(v) and GD(v), have already been mentioned in section 2. As the methods to be used are primal feasible it is immaterial the value of G(v, g) outside Ω. The function T(v)−V(g), that applies for the case of diagonal and separable inelastic demand traffic assignemnt problem, is also a gap function accordingly to (32) because it is always nonnegative on the cone Ω. Also, at the equilibrium points, T(v∗(g)) −V(g) = 0 and finally that T(v)−V(g)>0 if (v, g)∈Ωbut v6=v∗(g). In this paper we shall deal only with the primal gap function GP(v) parametrized by g. If the constraint GP(v, g) = 0 is penalized with parameter 1/α`, then (31) can be approximated by: Min(v, g)∈Ωψ`(v, g) = GP(v, g) + α`H(v, g) + α`µ` 2kg−g`k2 2(33) where α`·µ`→0. For the case of the gap function T(v)−V(g), valid for the case of diagonal and separable inelastic demand traffic assignment problem, it can be shown that problem (33) consistently approximates problem (31). This is shown in Codina (2001) and in Codina and Montero (2001) where a very similar scheme is followed but for the purpose of approximating the gradient of the upper level objective function H(v∗(g), g) at a point g. In order to solve the non-convex problem (33), the partial linearization of Patriksson (1993) can be applied for the case of the gap function being T(v)−V(g) as the perturbation function V(g) is differentiable. It must be remarked that the partial linearization algorithm of Patriksson is intended primarily for pseudoconvex functions. The convergence for the problem (33) is also proved in Codina and Montero (2001). An efficient way to solve the resulting subproblems in the partial linearization scheme can be the application of the excess demand Gartner’s transformation (Gartner 1980)) and to use a restricted simplicial decomposition method, such as the classical one of Hearn et al. (1987) on the resulting network. The optimality conditions for problem (33) can be stated by means of the Fermat rule as: 0∈¯ ∂GP(v, g) + α`∇H(v, g) + α`µ`(g−g`) + NΩ(v, g) = T(v, g) (34) The calculation of the Clarke’s subgradient of the primal gap function is done in Codina (2002) and it is shown there that: 16 ¯ ∂GP(˜v, ˜g) =       c(˜v) + Ã∂c ∂v !> ˜v (w−˜v) t(˜g)       (35) where w∈argmin{GP(˜v) = −Min w∈V(˜g)c(˜v)>(w−˜v)}. The generalized equation (34) can be difficult to solve and we will consider now the case in which the travel costs c(v) are strongly monotone with modulus mc. Now it is easy to see that Ãc(v∗(g)) −t(g) + α`µ`(g−g`)!+α`∇H(v∗(g), g) + NΩ(v∗(g), g)∈T(v∗(g), g) (36) If cα(v, g) = c(v) + α∇v H(v, g) and tα,µ(v, g) = t(g)−µα(g−g`)−α∇g H(v, g), then (36) can be rewritten as: Ãcα(v∗(g), g) −tα,µ(v∗(g), g)!+NΩ(v∗(g), g)∈T(v∗(g), g) (37) This suggests that a good approximation for the inclusion (34) can be the variational inequality: cα(v, g)>(v0−v)−tα,µ(v, g)>(g0−g)≥0,∀(v0, g0)∈Ω(38) presenting the structure of an elastic demand traffic assignment problem that can be converted to a fixed demand traffic assignment problem by means of the Gartner’s transformation. The good approximation of (38) to (34) is justified because the primal gap function Γ(v, g) for (38) verifies, |Γ(v∗(g), g)| ≤ LΓkv∗(g)−vk2 (1) ≤LΓ mc kcα,µ(v∗(g)) −c(v)k2≤ ≤αLΓ mc k∇v H(v∗(g), g)k2 (39) being mc>0 the modulus of strong monotonicity of the function c(v) (The inequality (1) is based on theorem 5.1 in Dafermos and Nagurney (1984)). The cost approximation algorithms in Patriksson (1999) can be used for the case of the gap function GP(v, g) and H=H(v). At iteration k, of the cost approximation algorithm, the resulting variational inequality subproblem at point gkis: cα(v)>(w−v)+(−t(gk) + µα(g−g`))>(g0−g)≥0,∀(w, g0)∈Ω(40) where t(g`) are the equilibrium O-D travel times resulting from the assignment of the O-D matrix gkwith costs c(v). The algorithm then can be summarized as follows: 17 Algorithm: (Start with µ1small.) At iteration `-th: 1. Carry out just few iterations k= 1, ..., L of the cost approximation scheme in order to approximately solve problem (38): •Solve subproblem (40) •Evaluate t(gk) = O-D travel times for gk;k←k+ 1 2. Let g0←gLand perform a line search along g0−g`. Let g`+1 =g`+β(g0−g`) be the next iterate. 3. Take µ`+1 < µ`(µ`→¯µ) The line search step is optional and not necessary for the convergence. In this case simply g`+1 =g0. For upper level objective functions of the form (30) a line search consisting of a simple quadratic fit can be used very advantageously. Moreover, for the direction g0−g`provided by the algorithm at the end of step 1, the simple quadratic fit seems to provide always a better point g`+1 (i.e. with lower objective function value). 6. Conclusions and further work This paper reviews firstly the conditions for convergence of the more used algorithms to solve variational inequalities with special incidence in the traffic assignment problem and summarizes the recently new conditions developed by Pennanen (2002) for the proximal point algorithm which do not require strong monotonicity. The application of the proximal point algorithm to a problem of bilevel programming that formulates the adjustment of origin-destination trip matrices is also shown. A set of numerical experiments will be required in order to evaluate practically and in comparison with other methods, the performance of the proximal point algorithm to the problems examined in this paper. 7. Acknowledgments This research has been supported under Spanish I+D research project BFM200204548-C03-01. References Bertsekas D.P., Gafni E.M. (1982) Projection methods for variational inequalities with application to the traffic assignment problem. Mathematical Programming Study 17, 139-159. Clarke, F. H. (1983). Optimization and Nonsmooth Analisys, John Wiley InterScience. 18 Codina, E. (2000a). “Lipschitz Continuity of O-D Travel Times for the Asymmetric Traffic Assignment Problem”, Working Paper, DR/2000-21, Departament d’Estad´ıstica i Investigaci´o Operativa. Universitat Polit`ecnica de Catalunya. Codina, E. (2000b). “A Test for the Approximation of Gradients of the Upper Level Function in Demand Adjustment Problems”, Working Paper, DR/2000-23. Departament d’Estad´ıstica i Investigaci´o Operativa. Universitat Polit`ecnica de Catalunya. Codina, E. and Barcel´o, J. (2000). “Adjustment of O-D Trip Matrices from Traffic Counts: an Algorithmic Approach Based on Conjugate Directions”, Proceedings of the 8th EWGT., Rome, Italy, July 2000, pp. 427-432. (forthcoming in European Journal of Operational Research) Codina, E. (2001). “Consistency of an approximation to the upper level objective function gradients in the o-d demand adjustment problem”. Working Paper, DR/2001-16. Departament d’Estad´ıstica i Investigaci´o Operativa. Universitat Polit`ecnica de Catalunya. Codina E., Montero L. (2001) “A Method to Approximate the Steepest Descent Direction of the OD Matrix Adjustment Problem”. Proceedings of the TRISTAN IV Conference at A¸cores, Portugal, June 2001. pp. 537-542. (forthcoming in Annals of Operations Research) Codina, E., Garc´ıa, Ricardo and Mar´ın Angel. (2001). “New Algorithmic Alternatives for the O-D Matrix Adjustment Problem on Traffic Networks”, Proceedings of the 9th EWGT., Bari, Italy, June 2001, pp. 421-425. (submitted for publication to European Journal of Operational Research) Codina, E.. (2002). “Evaluation of subgradients for the primal and dual gap functions for variational inequalities on polyhedral sets”, Working Paper, DR/2002-19, Departament d’Estad´ıstica i Investigaci´o Operativa. Universitat Polit`ecnica de Catalunya. Dafermos S., Nagurney A. (1984): Sensitivity analysis for the asymmetric network equilibrium problem. Math. Prog. 28, 174-184. Dontchev, A. L. and Rockafellar, R. T. (1996). “Characterizations of Strong Regularity for Variational Inequalities over Polyhedral Convex Sets”, SIAM Journal of Optimization, 12 No. 1, 1087-1105. Dontchev A. L. and Rockafellar, R. T. (2001). “Ample Parametrization of Variational Inclusions”. SIAM Journal of Optimization, 12 No. 1 170-187. Gartner, N.H. (1980) Optimal traffic assignments with elastic demands: a review. Part II: algorithmic approaches, Transpn. Sci. 14 (1980) 192-208. Hearn D. W. (1982) The gap function of a convex program. Oper. Res. Lett. 1, 67-71. Hearn D.W., Lawphongpanich S., Ventura J.A. (1987) “ Restricted Simplicial Decomposition: Computation and Extensions.” Mathematical Programming Study Vol 31, pp 99-118. Lawphongpanich S., Hearn D. W. (1984) Simplicial decomposition of the asymmetric traffic assignment problem. Transp. Res 18B, 123-133. Martinet B., (1970): Regularisation d’inequations variationelles par approximations successives “Revue Fran¸caise d’Informatique et de Recherche Operationelle” 4(R-3) pp. 154-158. Pang J. S., Yu C. S. (1984) Linearized simplicial decomposition methods for computing traffic equilibria on networks. Networks 14(3), 427-438. Patriksson, Michael (1999). Nonlinear Programming and variational inequality problems. A unified Approach. Kluwer Academic Publishers. Patriksson, Michael (1993) “Partial linearization Methods in Nonlinear Programming ”. Journal of Optimization Theory and Applications, 78, pp. 227-246. Pennanen, T.(2002): Local convergence of the proxinal point algorithm and multiplier methods without monotonicity Mathematics of Operations Research, Vol. 27 No. 1, pp 170-191. Rockafellar, R. Tyrrell (1976) Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 pp. 877-898. 19 Rockafellar, R. Tyrrell and R. Wets, Roger J-B., (1998) Variational Analysis, Springer Verlag. Smith M. J. (1979) Existence, uniqueness and stability of traffic equilibria. Transp. Res. 13B(4), 295-304. Smith M. J. (1983) An algorithm for solving asymmetric equilibrium problems with continuous cost-flow function. Transp. Res. 17B (5), 365-372. Wardrop J. G. (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civ. Eng. Part II, 1 (2), 325-378. 20