Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 90C33, 90B20; Secondary: 90B10.

 Citation:

•  [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.