Solving non-additive traffic assignment problems: a descent method for co-coercive variational inequalities. (English) Zbl 1065.90015

Han, Deren; Lo, Hong K.

Eur. J. Oper. Res. 159, No. 3, 529-544 (2004).

Summary: This paper developed a descent direction of the merit function for co-coercive variational inequality (VI) problems. The descent approach is closely related to Fukushima’s method for strongly monotone VI problems and He’s method for linear VI problems, and can be viewed as an extension for the more general case of co-coercive VI problems. This extension is important for route-based traffic assignment problems as the associated VI is often neither strongly monotone nor linear. This study then implemented the solution method for traffic assignment problems with non-additive route costs. Similar to projection-based methods, the computational effort required per iteration of this solution approach is modest. This is especially so for traffic equilibrium problems with elastic demand, where the solution method consists of a function evaluation and a simple projection onto the non-negative orthant.

MSC:

90B20	Traffic problems in operations research
90B80	Discrete location and assignment
58E35	Variational inequalities (global problems) in infinite-dimensional spaces

Keywords:

Variational inequalities; Co-coercivity; Traffic assignment

References:

[1]	Gabriel, S.; Bernstein, D., The traffic equilibrium problem with non-additive path costs, Transportation science, 31, 337-348, (1997) · Zbl 0920.90058
[2]	Lo, H., A dynamic traffic assignment formulation that encapsulates the cell transmission model, (), 327-350
[3]	Wong, S.C.; Yang, C.; Lo, H., A path-based traffic assignment algorithm using the TRANSYT traffic model, Transportation research part B, 35, 163-181, (2001)
[4]	Bernstein, D.; Gabriel, S., Solving the non-additive traffic equilibrium problem, (), 72-102 · Zbl 0878.90030
[5]	Lo, H.; Chen, A., Reformulating the traffic equilibrium problem via a smooth gap function, Mathematical and computational models, 31, 179-195, (2000) · Zbl 1042.90515
[6]	Lo, H.; Chen, A., Traffic equilibrium problem with route-specific costs: formulation and algorithms, Transportation research part B, 34, 493-513, (2000)
[7]	Bertsekas, D.P.; Gafni, E.M., Projection method for variational inequalities with application to the traffic assignment problem, Mathematical programming, 17, 139-159, (1982) · Zbl 0478.90071
[8]	He, B., A class of projection and contraction methods for monotone variational inequalities, Applied mathematics and optimization, 35, 69-76, (1997) · Zbl 0865.90119
[9]	Harker, P.T.; Pang, J.S., Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical programming, 48, 161-220, (1990) · Zbl 0734.90098
[10]	Taji, K.; Fukushima, M.; Ibaraki, T., A globally convergent Newton method for solving strongly monotone variational inequalities, Mathematical programming, 58, 369-383, (1993) · Zbl 0792.49007
[11]	Ferris, M.C.; Pang, J.S., Engineering and economic applications of complementarity problems, SIAM review, 39, 669-713, (1997) · Zbl 0891.90158
[12]	Ferris, M.C.; Kanzow, C., Complementarity and related problems, ()
[13]	Eaves, B.C., On the basic theorem of complementarity, Mathematical programming, 1, 68-85, (1971) · Zbl 0227.90044
[14]	Fukushima, M., Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical programming, 53, 99-110, (1992) · Zbl 0756.90081
[15]	He, B., A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming, Applied mathematics and optimization, 25, 247-262, (1992) · Zbl 0767.90086
[16]	Cohen, G., Auxiliary problem principle extended to variational inequalities, Journal of optimization theory and applications, 59, 325-333, (1988) · Zbl 0628.90066
[17]	Zhu, D.L.; Marcotte, P., Co-coercivity and its role in the convergence of iterative schemes for solving variational inequalities, SIAM journal of optimality, 6, 714-726, (1996) · Zbl 0855.47043
[18]	Tseng, P., Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming, Mathematical programming, 48, 249-264, (1990) · Zbl 0725.90079
[19]	Noor, M.A., A modified projection method for monotone variational inequalities, Applied mathematical letters, 12, 5, 83-87, (1999) · Zbl 0941.49006
[20]	Gafni, E.M.; Bertsekas, D.P., Two-metric projection methods for constrained optimization, SIAM journal of control and optimization, 22, 936-964, (1984) · Zbl 0555.90086
[21]	Peng, J.M., Equivalence of variational inequality problems to unconstrained minimization, Mathematical programming, 78, 347-355, (1997) · Zbl 0887.90171
[22]	Pang, J.S., Error bounds in mathematical programming, Mathematical programming, 79, 299-332, (1997) · Zbl 0887.90165
[23]	()
[24]	Wardrop, J.G., Some theoretical aspects of road traffic research, Proceedings of the institute of civil engineers, part II, 1, 325-378, (1952)
[25]	Marcotte, P.; Wu, J.H., On iterative projection methods for the variational inequality problem, Journal of optimization theory and applications, 85, 347-362, (1992,1995)
[26]	Chen, A.; Lo, H.; Yang, H., A self-adaptive projection and contraction algorithm for the traffic equilibrium problem with route-specific costs, European journal of operational research, 135, 1, 27-41, (2001) · Zbl 1077.90516
[27]	Nguyen, S.; Dupuis, C., An efficient method for computing traffic equilibria in networks with asymmetric transportation costs, Transportation science, 18, 185-202, (1984)
[28]	K. Scott and D. Bernstein, Solving a traffic equilibrium problem when path costs are non-additive, in: Paper presented at the 78th Annual Meeting of the Transportation Research Board, Washington, DC, January 1999
[29]	Han, D.; Lo, H., A new alternating direction method for a class of variational inequality problems, Journal of optimization theory and applications, 112, 549-560, (2002) · Zbl 0996.49003
[30]	Han, D., A modified alternating direction method for variational inequality problems, Applied mathematics and optimization, 45, 63-74, (2002) · Zbl 1098.90537
[31]	Tong, C.O.; Wong, S.C., A stochastic transit assignment model using a dynamic schedule-based network, Transportation research, 33B, 107-121, (1999)
[32]	K. Scott, D. Bernstein, Solving the minimum cost path problem when the value of time function is nonlinear, in: Proceedings of TRISTAN III, vol. 1, San Juan, Puerto Rico, 17-23 June 1998
[33]	Lo, H.; Yip, C.W.; Wan, K.H., Modeling transfers and nonlinear fare structure in multi-modal transit network, Transportation research, 37 B, 149-170, (2003)