American Institute of Mathematical Sciences

Advanced
January  2013, 9(1): 255-274. doi: 10.3934/jimo.2013.9.255

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

Gang Qian 1, , Deren Han 2, , Lingling Xu 3, and  Hai Yang 4,

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, China
4. 

Department of Civil Engineering, The Hong Kong University of Science and Technology, Hong Kong

Received  January 2012 Revised  June 2012 Published  December 2012

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: auxiliary problem principle, self-adaptive strategy., projection method, Traffic equilibrium and nonadditive cost, variational inequality problem.
Mathematics Subject Classification: Primary: 90C33; Secondary: 90B20, 93B4.
Citation: Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial & Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255
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.  doi: 10.1016/j.trb.2007.04.008.  Google Scholar

[2]

D. Bernstein and S. Gabriel, Solving the non-additive traffic equilibrium problem,, in, (1997), 72.   Google Scholar

[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.  doi: 10.1007/BFb0120965.  Google Scholar

[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.  doi: 10.1016/j.camwa.2008.10.065.  Google Scholar

[5]

G. Cohen, Auxiliary problem principle extended to variational inequalities,, Journal of Optimization Theory and Applications, 59 (1988), 325.   Google Scholar

[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.  doi: 10.1023/A:1008705425484.  Google Scholar

[7]

B. C. Eaves, On the basic theorem of complementarity,, Mathematical Programming, 1 (1971), 68.  doi: 10.1007/BF01584073.  Google Scholar

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Volumes I and II, (2003).   Google Scholar

[9]

M. C. Ferris and J. S. Pang, Engineering and economic applications of complementarity problems,, SIAM Review, 39 (1997), 669.  doi: 10.1137/S0036144595285963.  Google Scholar

[10]

S. Gabriel and D. Bernstein, The traffic equilibrium problem with non-additive path costs,, Transportation Science, 31 (1997), 337.  doi: 10.1287/trsc.31.4.337.  Google Scholar

[11]

A. A. Goldstein, Convex programming in Hilbert space,, Bulletin of the American Mathematical Society, 70 (1964), 709.  doi: 10.1090/S0002-9904-1964-11178-2.  Google Scholar

[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.  doi: 10.1016/S0377-2217(03)00423-5.  Google Scholar

[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.  doi: 10.1016/j.camwa.2003.12.002.  Google Scholar

[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.  doi: 10.1007/s10957-006-9060-5.  Google Scholar

[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.  doi: 10.1007/s00211-008-0181-7.  Google Scholar

[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.  doi: 10.1007/BF01582255.  Google Scholar

[17]

B. S. He, A class of projection and contraction methods for monotone variational inequalities,, Applied Mathematics and Optimization, 35 (1997), 69.   Google Scholar

[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.  doi: 10.1023/A:1013048729944.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/j.ejor.2008.03.004.  Google Scholar

[21]

G. M. Korpolevich, The extragradient method for finding saddle points and other problems,, Matecon, 12 (1976), 747.   Google Scholar

[22]

E. N. Khobotov, Modification of the extragradient method for solving variational inequalities and certain optimization problems,, USSR, 27 (1987), 120.  doi: 10.1016/0041-5553(87)90058-9.  Google Scholar

[23]

E. S. Levitin and B. T. Polyak, Constrained minimization problems,, USSR. Computational Mathematics and Mathematical Physics, 6 (1966), 1.  doi: 10.1016/0041-5553(66)90114-5.  Google Scholar

[24]

H. Lo, A dynamic traffic assignment formulation that encapsulates the Cell Transmission Model,, in, (1999), 327.   Google Scholar

[25]

H. Lo and A. Chen, Reformulating the traffic equilibrium problem via a smooth gap function,, Mathematical and Computer Modeling, 31 (2000), 179.  doi: 10.1016/S0895-7177(99)00231-9.  Google Scholar

[26]

H. Lo and A. Chen, Traffic equilibrium problem with route-specific costs: Formulation and algorithms,, Transportation Research Part B, 34 (2000), 493.  doi: 10.1016/S0191-2615(99)00035-1.  Google Scholar

[27]

A. Nagurney, "Network Economics: A Variational Inequality Approach,", Kluwer Academics Publishers, (1993).   Google Scholar

[28]

K. Scott and D. Bernstein, Solving a traffic equilibrium problem when path costs are non-additive,, Paper presented at, (1999).   Google Scholar

[29]

K. Taji, M. Fukushima and T. Ibaraki, A globally convergent Newton method for solving strongly monotone variational inequalities,, Mathematical Programming, 58 (1993), 369.  doi: 10.1007/BF01581276.  Google Scholar

[30]

J. G. Wardrop, Some theoretical aspects of road traffic research,, in, 1 (1952), 325.   Google Scholar

[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.  doi: 10.1016/S0191-2615(03)00077-8.  Google Scholar

[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.  doi: 10.1137/S1052623494250415.  Google Scholar

[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.  doi: 10.7153/mia-07-45.  Google Scholar

show all references

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.  doi: 10.1016/j.trb.2007.04.008.  Google Scholar

[2]

D. Bernstein and S. Gabriel, Solving the non-additive traffic equilibrium problem,, in, (1997), 72.   Google Scholar

[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.  doi: 10.1007/BFb0120965.  Google Scholar

[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.  doi: 10.1016/j.camwa.2008.10.065.  Google Scholar

[5]

G. Cohen, Auxiliary problem principle extended to variational inequalities,, Journal of Optimization Theory and Applications, 59 (1988), 325.   Google Scholar

[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.  doi: 10.1023/A:1008705425484.  Google Scholar

[7]

B. C. Eaves, On the basic theorem of complementarity,, Mathematical Programming, 1 (1971), 68.  doi: 10.1007/BF01584073.  Google Scholar

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Volumes I and II, (2003).   Google Scholar

[9]

M. C. Ferris and J. S. Pang, Engineering and economic applications of complementarity problems,, SIAM Review, 39 (1997), 669.  doi: 10.1137/S0036144595285963.  Google Scholar

[10]

S. Gabriel and D. Bernstein, The traffic equilibrium problem with non-additive path costs,, Transportation Science, 31 (1997), 337.  doi: 10.1287/trsc.31.4.337.  Google Scholar

[11]

A. A. Goldstein, Convex programming in Hilbert space,, Bulletin of the American Mathematical Society, 70 (1964), 709.  doi: 10.1090/S0002-9904-1964-11178-2.  Google Scholar

[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.  doi: 10.1016/S0377-2217(03)00423-5.  Google Scholar

[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.  doi: 10.1016/j.camwa.2003.12.002.  Google Scholar

[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.  doi: 10.1007/s10957-006-9060-5.  Google Scholar

[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.  doi: 10.1007/s00211-008-0181-7.  Google Scholar

[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.  doi: 10.1007/BF01582255.  Google Scholar

[17]

B. S. He, A class of projection and contraction methods for monotone variational inequalities,, Applied Mathematics and Optimization, 35 (1997), 69.   Google Scholar

[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.  doi: 10.1023/A:1013048729944.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/j.ejor.2008.03.004.  Google Scholar

[21]

G. M. Korpolevich, The extragradient method for finding saddle points and other problems,, Matecon, 12 (1976), 747.   Google Scholar

[22]

E. N. Khobotov, Modification of the extragradient method for solving variational inequalities and certain optimization problems,, USSR, 27 (1987), 120.  doi: 10.1016/0041-5553(87)90058-9.  Google Scholar

[23]

E. S. Levitin and B. T. Polyak, Constrained minimization problems,, USSR. Computational Mathematics and Mathematical Physics, 6 (1966), 1.  doi: 10.1016/0041-5553(66)90114-5.  Google Scholar

[24]

H. Lo, A dynamic traffic assignment formulation that encapsulates the Cell Transmission Model,, in, (1999), 327.   Google Scholar

[25]

H. Lo and A. Chen, Reformulating the traffic equilibrium problem via a smooth gap function,, Mathematical and Computer Modeling, 31 (2000), 179.  doi: 10.1016/S0895-7177(99)00231-9.  Google Scholar

[26]

H. Lo and A. Chen, Traffic equilibrium problem with route-specific costs: Formulation and algorithms,, Transportation Research Part B, 34 (2000), 493.  doi: 10.1016/S0191-2615(99)00035-1.  Google Scholar

[27]

A. Nagurney, "Network Economics: A Variational Inequality Approach,", Kluwer Academics Publishers, (1993).   Google Scholar

[28]

K. Scott and D. Bernstein, Solving a traffic equilibrium problem when path costs are non-additive,, Paper presented at, (1999).   Google Scholar

[29]

K. Taji, M. Fukushima and T. Ibaraki, A globally convergent Newton method for solving strongly monotone variational inequalities,, Mathematical Programming, 58 (1993), 369.  doi: 10.1007/BF01581276.  Google Scholar

[30]

J. G. Wardrop, Some theoretical aspects of road traffic research,, in, 1 (1952), 325.   Google Scholar

[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.  doi: 10.1016/S0191-2615(03)00077-8.  Google Scholar

[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.  doi: 10.1137/S1052623494250415.  Google Scholar

[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.  doi: 10.7153/mia-07-45.  Google Scholar

[1]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[2]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[3]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[4]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[5]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[6]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[7]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[8]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[9]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[10]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[11]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[12]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827
[13]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[14]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[15]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[16]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213
[17]

Thomas Y. Hou, Ruo Li. Nonexistence of locally self-similar blow-up for the 3D incompressible Navier-Stokes equations. Discrete & Continuous Dynamical Systems - A, 2007, 18 (4) : 637-642. doi: 10.3934/dcds.2007.18.637
[18]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045
[19]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[20]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (49)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences