American Institute of Mathematical Sciences

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 and 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-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.

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-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.
 [1] Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241 [2] Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012 [3] Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1261-1274. doi: 10.3934/jimo.2021018 [4] Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911 [5] 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 and Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255 [6] Hongming Yang, C. Y. Chung, Xiaojiao Tong, Pingping Bing. Research on dynamic equilibrium of power market with complex network constraints based on nonlinear complementarity function. Journal of Industrial and Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617 [7] Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030 [8] Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030 [9] Chuong Van Nguyen, Phuong Huu Hoang, Hyo-Sung Ahn. Distributed optimization algorithms for game of power generation in smart grid. Numerical Algebra, Control and Optimization, 2019, 9 (3) : 327-348. doi: 10.3934/naco.2019022 [10] X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287 [11] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [12] O. İlker Kolak, Orhan Feyzioğlu, Ş. İlker Birbil, Nilay Noyan, Semih Yalçindağ. Using emission functions in modeling environmentally sustainable traffic assignment policies. Journal of Industrial and Management Optimization, 2013, 9 (2) : 341-363. doi: 10.3934/jimo.2013.9.341 [13] Kai Zhang, Xiaoqi Yang, Kok Lay Teo. A power penalty approach to american option pricing with jump diffusion processes. Journal of Industrial and Management Optimization, 2008, 4 (4) : 783-799. doi: 10.3934/jimo.2008.4.783 [14] Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049 [15] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51 [16] Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381 [17] Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391 [18] Jun Guo, Qinghua Wu, Guozheng Yan. The factorization method for cracks in elastic scattering. Inverse Problems and Imaging, 2018, 12 (2) : 349-371. doi: 10.3934/ipi.2018016 [19] Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115 [20] Liping Zhang. A nonlinear complementarity model for supply chain network equilibrium. Journal of Industrial and Management Optimization, 2007, 3 (4) : 727-737. doi: 10.3934/jimo.2007.3.727

2020 Impact Factor: 1.801