Solving nonadditive traffic assignment problems:A self-adaptive projection-auxiliary problem method for variationalinequalities

Gang Qian; Deren Han; Lingling Xu; Hai Yang

doi:10.3934/jimo.2013.9.255

Article Contents

2013, Volume 9, Issue 1: 255-274. Doi: 10.3934/jimo.2013.9.255

This issue Previous Article An outcome space algorithm for minimizing the product of two convex functions over a convex set Next Article

Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities

1.
School of Computer Sciences, Nanjing Normal University, Nanjing 210097
2.
School of Mathematical Science, Nanjing Normal University, Nanjing 210046
3.
School of Mathematical Sciences, Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing 210046
4.
Department of Civil Engineering, The Hong Kong University of Science and Technology, Hong Kong

Received: January 2012

Revised: June 2012

Published: January 2013

Abstract Related Papers Cited by

Abstract

In the last decade, as calibrations of the classical traffic equilibrium problems, various models of traffic equilibrium problems with nonadditive route costs have been proposed. For solving such models, this paper develops a self-adaptive projection-auxiliary problem method for monotone variational inequality (VI) problems. It first converts the original problem where the feasible set is the intersection of a linear manifold and a simple set to an augmented VI with simple set, which makes the projection easy to implement. The self-adaptive strategy avoids the difficult task of choosing `suitable' parameters, and leads to fast convergence. Under suitable conditions, we prove the global convergence of the method. Some preliminary computational results are presented to illustrate the ability and efficiency of the method.

Keywords:

Traffic equilibrium and nonadditive cost,
variational inequality problem,
auxiliary problem principle,
projection method,
self-adaptive strategy.

Mathematics Subject Classification: Primary: 90C33; Secondary: 90B20, 93B40.

Citation:

Related Papers

Cited by

References

[1]	R. P. Agdeppa, N. Yamashita and M. Fukushima, The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation, Transportation Research Part B, 41 (2007), 862-874.doi: 10.1016/j.trb.2007.04.008.
[2]	D. Bernstein and S. Gabriel, Solving the non-additive traffic equilibrium problem, in "Proceedings of the Network Optimization Conference" (eds. P. Pardalos, D. Hearn and W. Hager), Springer, (1997), 72-102.
[3]	D. P. Bertsekas and E. M. Gafni, Projection method for variational inequalities with application to the traffic assignment problem, Mathematical Programming Study, 17 (1982), 139-159.doi: 10.1007/BFb0120965.
[4]	A. Bnouhachem, M. H. Xu, X. L. Fu and Z. H. Sheng, Modified extragradient methods for solving variational inequalities, Computers and Mathematics with Applications, 57 (2009), 230-239.doi: 10.1016/j.camwa.2008.10.065.
[5]	G. Cohen, Auxiliary problem principle extended to variational inequalities, Journal of Optimization Theory and Applications, 59 (1988), 325-333.
[6]	T. De Luca, F. Facchinei and C. Kanzow, A theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Computational Optimization and Applications, 16 (2000), 173-205.doi: 10.1023/A:1008705425484.
[7]	B. C. Eaves, On the basic theorem of complementarity, Mathematical Programming, 1 (1971), 68-75.doi: 10.1007/BF01584073.
[8]	F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Volumes I and II, Springer Verlag, Berlin, 2003.
[9]	M. C. Ferris and J. S. Pang, Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.doi: 10.1137/S0036144595285963.
[10]	S. Gabriel and D. Bernstein, The traffic equilibrium problem with non-additive path costs, Transportation Science, 31 (1997), 337-348.doi: 10.1287/trsc.31.4.337.
[11]	A. A. Goldstein, Convex programming in Hilbert space, Bulletin of the American Mathematical Society, 70 (1964), 709-710.doi: 10.1090/S0002-9904-1964-11178-2.
[12]	D. R. Han and Hong K. Lo, Solving non-additive traffic assignment problems: A descent method for co-coercive variational inequalities, European Journal of Operational Research, 159 (2004), 529-545.doi: 10.1016/S0377-2217(03)00423-5.
[13]	D. R. Han and W. Y. Sun, A new modified Goldstein-Levitin-Polyak projection method for variational inequality problems, Computers and Mathematics with Applications, 47 (2004), 1817-1825.doi: 10.1016/j.camwa.2003.12.002.
[14]	D. R. Han, Inexact operator splitting methods with self-adaptive strategy for variational inequality problems, Journal of Optimization Theory and Applications, 132 (2007), 227-243.doi: 10.1007/s10957-006-9060-5.
[15]	D. R. Han, W. Xu and H. Yang, An operator splitting method for variational inequalities with partially unknown mappings, Numerische Mathematik, 111 (2008), 207-237.doi: 10.1007/s00211-008-0181-7.
[16]	P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220.doi: 10.1007/BF01582255.
[17]	B. S. He, A class of projection and contraction methods for monotone variational inequalities, Applied Mathematics and Optimization, 35 (1997), 69-76.
[18]	B. S. He, H. Yang, Q. Meng and D. R. Han, Modified Goldstein-Levitin-Polyak projection method for asymmetric strongly monotone variational inequalities, Journal of Optimization Theory and Applications, 112 (2002), 129-143.doi: 10.1023/A:1013048729944.
[19]	B. S. He, L. Z. Liao and S. L. Wang, Self-adaptive operator splitting methods for monotone variational inequalities, Numerische Mathematik, 94 (2003), 715-737.
[20]	B. S. He, X. H. Liu, T. Wu and X. Z. He, Self-adaptive projection method for co-coercive variational inequalities, European Journal of Operational Research, 196 (2009), 43-48.doi: 10.1016/j.ejor.2008.03.004.
[21]	G. M. Korpolevich, The extragradient method for finding saddle points and other problems, Matecon, 12 (1976), 747-756.
[22]	E. N. Khobotov, Modification of the extragradient method for solving variational inequalities and certain optimization problems, USSR, Computational Mathematics and Mathematical Physics, 27 (1987), 120-127.doi: 10.1016/0041-5553(87)90058-9.
[23]	E. S. Levitin and B. T. Polyak, Constrained minimization problems, USSR. Computational Mathematics and Mathematical Physics, 6 (1966), 1-50.doi: 10.1016/0041-5553(66)90114-5.
[24]	H. Lo, A dynamic traffic assignment formulation that encapsulates the Cell Transmission Model, in "Transportation and Traffic Theory" (ed. A. Cedar), Elsevier Science, (1999), 327-350.
[25]	H. Lo and A. Chen, Reformulating the traffic equilibrium problem via a smooth gap function, Mathematical and Computer Modeling, 31 (2000), 179-195.doi: 10.1016/S0895-7177(99)00231-9.
[26]	H. Lo and A. Chen, Traffic equilibrium problem with route-specific costs: Formulation and algorithms, Transportation Research Part B, 34 (2000), 493-513.doi: 10.1016/S0191-2615(99)00035-1.
[27]	A. Nagurney, "Network Economics: A Variational Inequality Approach," Kluwer Academics Publishers, Dordrecht, Boston, London, 1993.
[28]	K. Scott and D. Bernstein, Solving a traffic equilibrium problem when path costs are non-additive, Paper presented at "The 78th Annual Meeting of the Transportation Research Board", Washington, DC, January 1999.
[29]	K. Taji, M. Fukushima and T. Ibaraki, A globally convergent Newton method for solving strongly monotone variational inequalities, Mathematical Programming, 58 (1993), 369-383.doi: 10.1007/BF01581276.
[30]	J. G. Wardrop, Some theoretical aspects of road traffic research, in "Proceedings of Institute of Civil Engineers, Pt. II", 1 (1952), 325-378.
[31]	H. Yang, Q. Meng and D. H. Lee, Trial-and-error implementation of marginal-cost pricing on networks in the absence of demand functions, Transportation Research Part B, 38 (2004), 477-493.doi: 10.1016/S0191-2615(03)00077-8.
[32]	D. L. Zhu and P. Marcotte, Co-coercivity and its role in the convergence of iterative schemes for solving variational inequalities, SIAM Journal on Optimization, 6 (1996), 714-726.doi: 10.1137/S1052623494250415.
[33]	T. Zhu and Z. G. Yu, A simple proof for some important properties of the projection mapping, Mathematical Inequalities and Applicatrions, 7 (2004), 453-456.doi: 10.7153/mia-07-45.