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]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018

[2]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[3]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134

[4]

Noriyoshi Fukaya. Uniqueness and nondegeneracy of ground states for nonlinear Schrödinger equations with attractive inverse-power potential. Communications on Pure & Applied Analysis, 2021, 20 (1) : 121-143. doi: 10.3934/cpaa.2020260

[5]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[6]

Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097

[7]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[8]

Honglin Yang, Jiawu Peng. Coordinating a supply chain with demand information updating. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020181

[9]

Robert Stephen Cantrell, King-Yeung Lam. Competitive exclusion in phytoplankton communities in a eutrophic water column. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020361

[10]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[11]

Patrick W. Dondl, Martin Jesenko. Threshold phenomenon for homogenized fronts in random elastic media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 353-372. doi: 10.3934/dcdss.2020329

[12]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[13]

Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020034

[14]

Linfeng Mei, Feng-Bin Wang. Dynamics of phytoplankton species competition for light and nutrient with recycling in a water column. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020359

[15]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[16]

Jianli Xiang, Guozheng Yan. The uniqueness of the inverse elastic wave scattering problem based on the mixed reciprocity relation. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021004

[17]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[18]

Puneet Pasricha, Anubha Goel. Pricing power exchange options with hawkes jump diffusion processes. Journal of Industrial & Management Optimization, 2021, 17 (1) : 133-149. doi: 10.3934/jimo.2019103

[19]

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

[20]

Feimin Zhong, Jinxing Xie, Yuwei Shen. Bargaining in a multi-echelon supply chain with power structure: KS solution vs. Nash solution. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020172

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]