October  2014, 10(4): 1019-1030. doi: 10.3934/jimo.2014.10.1019

A power penalty method for the general traffic assignment problem with elastic demand

1. 

School of Mathematics and Statistics, Wuhan University, Wuhan, Hubei 430072, China, China

Received  April 2013 Revised  August 2013 Published  February 2014

This paper established some new convergence results for the power penalty method for the nonlinear complementarity problem(NCP), and then applied the method to solve the general traffic assignment problem with elastic demand. The power penalty method approximates the NCP by a nonlinear equation containing a power penalty term. We prove that this method can handle general monotone NCPs. This result is important for the general traffic assignment problem with elastic demand because the associated NCP is often not $\xi$ monotone. This study considered the traffic assignment problem with symmetric and asymmetric link costs, as well as additive and non-additive route costs. We propose to use a column generation scheme based on the proposed power penalty method to solve this problem. Numerical results are provided to demonstrate the efficiency of the method.
Citation: Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1019-1030. doi: 10.3934/jimo.2014.10.1019
References:
[1]

H. Z. Aashtiani and T. L. Magnanti, Equilibria on a congested transportation network,, SIAM Journal on Algebraic Discrete Methods, 2 (1981), 213.  doi: 10.1137/0602024.  Google Scholar

[2]

F. Babonneau and J. P. Vial, An efficient method to compute traffic assignment problems with elastic demands,, Transportation Science, 42 (2008), 249.  doi: 10.1287/trsc.1070.0208.  Google Scholar

[3]

A. Chen, H. K. Lo and H. Yang, A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs,, European Journal of Operational Research, 135 (2001), 27.  doi: 10.1016/S0377-2217(00)00287-3.  Google Scholar

[4]

S. Dafermos, Relaxation algorithms for the general asymmetric traffic equilibrium problem,, Transportation Science, 16 (1982), 231.  doi: 10.1287/trsc.16.2.231.  Google Scholar

[5]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Springer-Verlag, (2003).  doi: 10.1007/b97544.  Google Scholar

[6]

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

[7]

N. H. Gartner, Optimal traffic assignment with elastic demands: A review. Part II. algorithmic approaches,, Transportation Science, 14 (1980), 192.  doi: 10.1287/trsc.14.2.192.  Google Scholar

[8]

D. Han and H. 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

[9]

C. Huang and S. Wang, A power penalty approach to a nonlinear complementarity problem,, Operations Research Letters, 38 (2010), 72.  doi: 10.1016/j.orl.2009.09.009.  Google Scholar

[10]

C. Huang and S. Wang, A penalty method for a mixed nonlinear complementarity problem,, Nonlinear Analysis: Theory, 75 (2012), 588.  doi: 10.1016/j.na.2011.08.061.  Google Scholar

[11]

L. J. LeBlanc and K. Farhangian, Efficient algorithms for solving elastic demand traffic assignment problems and mode split-assignment problems,, Transportation Science, 15 (1981), 306.  doi: 10.1287/trsc.15.4.306.  Google Scholar

[12]

W. Li and S. Wang, Pricing American options under proportional transaction costs using a penalty approach and a finite difference scheme,, Journal of Industrial and Management Optimization, 9 (2013), 365.  doi: 10.3934/jimo.2013.9.365.  Google Scholar

[13]

E. Martins and M. Pascoal, A new implementation of Yen's ranking loopless paths algorithm,, 4OR: A Quarterly Journal of Operations Research, 1 (2003), 121.  doi: 10.1007/s10288-002-0010-2.  Google Scholar

[14]

A. Nagurney, Computational comparisons of algorithms for general asymmetric traffic equilibrium problems with fixed and elastic demands,, Transportation Research Part B: Methodological, 20 (1986), 78.  doi: 10.1016/0191-2615(86)90041-X.  Google Scholar

[15]

S. Nguyen and C. Dupuis, An efficient method for computing traffic equilibria in networks with asymmetric transportation costs,, Transportation Science, 18 (1984), 185.  doi: 10.1287/trsc.18.2.185.  Google Scholar

[16]

G. Qian, D. Han, L. Xu and H. Yang, Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities,, Journal of Industrial and Management Optimization, 9 (2013), 255.  doi: 10.3934/jimo.2013.9.255.  Google Scholar

[17]

S. Wang and C. S. Huang, A power penalty method for solving a nonlinear parabolic complementarity problem,, Nonlinear Analysis: Theory, 69 (2008), 1125.  doi: 10.1016/j.na.2007.06.014.  Google Scholar

[18]

S. Wang and X. Yang, A power penalty method for linear complementarity problems,, Operations Research Letters, 36 (2008), 211.  doi: 10.1016/j.orl.2007.06.006.  Google Scholar

[19]

S. Wang, X. Yang and K. Teo, Power penalty method for a linear complementarity problem arising from American option valuation,, Journal of Optimization Theory & Applications, 129 (2006), 227.  doi: 10.1007/s10957-006-9062-3.  Google Scholar

[20]

K. Zhang, X. Yang and K. L. Teo, A power penalty approach to American option pricing with jump diffusion processes,, Journal of Industrial and Management Optimization, 4 (2008), 783.  doi: 10.3934/jimo.2008.4.783.  Google Scholar

show all references

References:
[1]

H. Z. Aashtiani and T. L. Magnanti, Equilibria on a congested transportation network,, SIAM Journal on Algebraic Discrete Methods, 2 (1981), 213.  doi: 10.1137/0602024.  Google Scholar

[2]

F. Babonneau and J. P. Vial, An efficient method to compute traffic assignment problems with elastic demands,, Transportation Science, 42 (2008), 249.  doi: 10.1287/trsc.1070.0208.  Google Scholar

[3]

A. Chen, H. K. Lo and H. Yang, A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs,, European Journal of Operational Research, 135 (2001), 27.  doi: 10.1016/S0377-2217(00)00287-3.  Google Scholar

[4]

S. Dafermos, Relaxation algorithms for the general asymmetric traffic equilibrium problem,, Transportation Science, 16 (1982), 231.  doi: 10.1287/trsc.16.2.231.  Google Scholar

[5]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Springer-Verlag, (2003).  doi: 10.1007/b97544.  Google Scholar

[6]

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

[7]

N. H. Gartner, Optimal traffic assignment with elastic demands: A review. Part II. algorithmic approaches,, Transportation Science, 14 (1980), 192.  doi: 10.1287/trsc.14.2.192.  Google Scholar

[8]

D. Han and H. 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

[9]

C. Huang and S. Wang, A power penalty approach to a nonlinear complementarity problem,, Operations Research Letters, 38 (2010), 72.  doi: 10.1016/j.orl.2009.09.009.  Google Scholar

[10]

C. Huang and S. Wang, A penalty method for a mixed nonlinear complementarity problem,, Nonlinear Analysis: Theory, 75 (2012), 588.  doi: 10.1016/j.na.2011.08.061.  Google Scholar

[11]

L. J. LeBlanc and K. Farhangian, Efficient algorithms for solving elastic demand traffic assignment problems and mode split-assignment problems,, Transportation Science, 15 (1981), 306.  doi: 10.1287/trsc.15.4.306.  Google Scholar

[12]

W. Li and S. Wang, Pricing American options under proportional transaction costs using a penalty approach and a finite difference scheme,, Journal of Industrial and Management Optimization, 9 (2013), 365.  doi: 10.3934/jimo.2013.9.365.  Google Scholar

[13]

E. Martins and M. Pascoal, A new implementation of Yen's ranking loopless paths algorithm,, 4OR: A Quarterly Journal of Operations Research, 1 (2003), 121.  doi: 10.1007/s10288-002-0010-2.  Google Scholar

[14]

A. Nagurney, Computational comparisons of algorithms for general asymmetric traffic equilibrium problems with fixed and elastic demands,, Transportation Research Part B: Methodological, 20 (1986), 78.  doi: 10.1016/0191-2615(86)90041-X.  Google Scholar

[15]

S. Nguyen and C. Dupuis, An efficient method for computing traffic equilibria in networks with asymmetric transportation costs,, Transportation Science, 18 (1984), 185.  doi: 10.1287/trsc.18.2.185.  Google Scholar

[16]

G. Qian, D. Han, L. Xu and H. Yang, Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities,, Journal of Industrial and Management Optimization, 9 (2013), 255.  doi: 10.3934/jimo.2013.9.255.  Google Scholar

[17]

S. Wang and C. S. Huang, A power penalty method for solving a nonlinear parabolic complementarity problem,, Nonlinear Analysis: Theory, 69 (2008), 1125.  doi: 10.1016/j.na.2007.06.014.  Google Scholar

[18]

S. Wang and X. Yang, A power penalty method for linear complementarity problems,, Operations Research Letters, 36 (2008), 211.  doi: 10.1016/j.orl.2007.06.006.  Google Scholar

[19]

S. Wang, X. Yang and K. Teo, Power penalty method for a linear complementarity problem arising from American option valuation,, Journal of Optimization Theory & Applications, 129 (2006), 227.  doi: 10.1007/s10957-006-9062-3.  Google Scholar

[20]

K. Zhang, X. Yang and K. L. Teo, A power penalty approach to American option pricing with jump diffusion processes,, Journal of Industrial and Management Optimization, 4 (2008), 783.  doi: 10.3934/jimo.2008.4.783.  Google Scholar

[1]

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

[2]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[3]

Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1

[4]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013

[5]

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

[6]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267

[7]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933

[8]

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

[9]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

[10]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[11]

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

[12]

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

[13]

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

[14]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

[15]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[16]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[17]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[18]

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

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]