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]

Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial & 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 & Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012

[3]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

[4]

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

[5]

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 & Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617

[6]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[7]

Chuong Van Nguyen, Phuong Huu Hoang, Hyo-Sung Ahn. Distributed optimization algorithms for game of power generation in smart grid. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 327-348. doi: 10.3934/naco.2019022

[8]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287

[9]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[10]

Kai Zhang, Xiaoqi Yang, Kok Lay Teo. A power penalty approach to american option pricing with jump diffusion processes. Journal of Industrial & Management Optimization, 2008, 4 (4) : 783-799. doi: 10.3934/jimo.2008.4.783

[11]

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 & Management Optimization, 2013, 9 (2) : 341-363. doi: 10.3934/jimo.2013.9.341

[12]

Jun Guo, Qinghua Wu, Guozheng Yan. The factorization method for cracks in elastic scattering. Inverse Problems & Imaging, 2018, 12 (2) : 349-371. doi: 10.3934/ipi.2018016

[13]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51

[14]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381

[15]

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391

[16]

Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049

[17]

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 & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

[18]

Liping Zhang. A nonlinear complementarity model for supply chain network equilibrium. Journal of Industrial & Management Optimization, 2007, 3 (4) : 727-737. doi: 10.3934/jimo.2007.3.727

[19]

Xiaojiao Tong, Felix F. Wu, Yongping Zhang, Zheng Yan, Yixin Ni. A semismooth Newton method for solving optimal power flow. Journal of Industrial & Management Optimization, 2007, 3 (3) : 553-567. doi: 10.3934/jimo.2007.3.553

[20]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]