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

Ming Chen; Chongchao Huang

doi:10.3934/jimo.2014.10.1019

Article Contents

2014, Volume 10, Issue 4: 1019-1030. Doi: 10.3934/jimo.2014.10.1019

This issue Previous Article On minimax fractional programming problems involving generalized $(H_p,r)$-invex functions Next Article Bounds for the greatest eigenvalue of positive tensors

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

Ming Chen^1, and
Chongchao Huang^1,

1.
School of Mathematics and Statistics, Wuhan University, Wuhan, Hubei 430072

Received: March 31, 2013

Revised: July 31, 2013

Published: September 2014

Abstract Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Related Papers

Cited by

References

[1]	H. Z. Aashtiani and T. L. Magnanti, Equilibria on a congested transportation network, SIAM Journal on Algebraic Discrete Methods, 2 (1981), 213-226.doi: 10.1137/0602024.
[2]	F. Babonneau and J. P. Vial, An efficient method to compute traffic assignment problems with elastic demands, Transportation Science, 42 (2008), 249-260.doi: 10.1287/trsc.1070.0208.
[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-41.doi: 10.1016/S0377-2217(00)00287-3.
[4]	S. Dafermos, Relaxation algorithms for the general asymmetric traffic equilibrium problem, Transportation Science, 16 (1982), 231-240.doi: 10.1287/trsc.16.2.231.
[5]	F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003.doi: 10.1007/b97544.
[6]	S. A. Gabriel and D. Bernstein, The traffic equilibrium problem with nonadditive path costs, Transportation Science, 31 (1997), 337-348.doi: 10.1287/trsc.31.4.337.
[7]	N. H. Gartner, Optimal traffic assignment with elastic demands: A review. Part II. algorithmic approaches, Transportation Science, 14 (1980), 192-208.doi: 10.1287/trsc.14.2.192.
[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-544.doi: 10.1016/S0377-2217(03)00423-5.
[9]	C. Huang and S. Wang, A power penalty approach to a nonlinear complementarity problem, Operations Research Letters, 38 (2010), 72-76.doi: 10.1016/j.orl.2009.09.009.
[10]	C. Huang and S. Wang, A penalty method for a mixed nonlinear complementarity problem, Nonlinear Analysis: Theory, Methods & Applications, 75 (2012), 588-597.doi: 10.1016/j.na.2011.08.061.
[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-317.doi: 10.1287/trsc.15.4.306.
[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-389.doi: 10.3934/jimo.2013.9.365.
[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-133.doi: 10.1007/s10288-002-0010-2.
[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-84.doi: 10.1016/0191-2615(86)90041-X.
[15]	S. Nguyen and C. Dupuis, An efficient method for computing traffic equilibria in networks with asymmetric transportation costs, Transportation Science, 18 (1984), 185-202.doi: 10.1287/trsc.18.2.185.
[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-274.doi: 10.3934/jimo.2013.9.255.
[17]	S. Wang and C. S. Huang, A power penalty method for solving a nonlinear parabolic complementarity problem, Nonlinear Analysis: Theory, Methods & Applications, 69 (2008), 1125-1137.doi: 10.1016/j.na.2007.06.014.
[18]	S. Wang and X. Yang, A power penalty method for linear complementarity problems, Operations Research Letters, 36 (2008), 211-214.doi: 10.1016/j.orl.2007.06.006.
[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-254.doi: 10.1007/s10957-006-9062-3.
[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-799.doi: 10.3934/jimo.2008.4.783.