A perturbation-based approach for continuous network design problem with emissions

Previous Article
Speeding up a memetic algorithm for the max-bisection problem
NACO Home
This Issue
Next Article
Rank-one and sparse matrix decomposition for dynamic MRI

2015, 5(2): 135-149. doi: 10.3934/naco.2015.5.135

A perturbation-based approach for continuous network design problem with emissions

Robert Ebihart Msigwa ^1, , Yue Lu ^1, , Xiantao Xiao ^2, and Liwei Zhang ^1,

1.	Institute of Operations Research and Control Theory, School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024, China, China, China
2.	Institute of Operations Research and Control Theory, School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

Received October 2014 Revised April 2015 Published June 2015

Abstract
Related Papers

The objective of continuous network design problem (CNDP) is to determine the optimal capacity expansion policy under a limited budget. This transportation system is formulated as a bi-level program where the upper level aims to determine the link capacity expansion vector and emission while taking into account the lower level response. This problem can be solved using various optimization algorithms and software. In this study, the CNDP with environmental considerations is designed and solved using the perturbation based approach. The lower level representing the road users subjected to user equilibrium is solved using the Frank-Wolfe algorithm. The proposed model is tested using a small hypothetical network to show the efficacy of the method. As a contribution of this paper, first it suggests a perturbation based approach for planners to design the capacity expansion, which minimize the total system cost and emission. Second the proposed method solves the nonlinear mathematical program with complementarity constraints (NLMPCC) problem, which overcomes the lack of a suitable set of constraint qualifications, such as Mangasarian Fromovitz constraint qualifications (MFCQ). Although the proposed model illustrated using the CO only and small network, the approach is not limited to large-scale network design problems and other pollutants..

Keywords: mathematical programs with complementarity constraints, traffic assignment problem, Capacity expansion, transport emission., bi-level programming problem.

Mathematics Subject Classification: Primary: 90B10, 65K05; Secondary: 90C3.

Citation: Robert Ebihart Msigwa, Yue Lu, Xiantao Xiao, Liwei Zhang. A perturbation-based approach for continuous network design problem with emissions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 135-149. doi: 10.3934/naco.2015.5.135

References:

[1]	S. P. Anusha, Study of Influence of Lane Restrictions on Vehicular Emissions under the Heterogeneous Traffic Flow, MS thesis, Department of Civil Engineering, Indian Institute of Technology, Madras, 2007.
[2]	C. M. Benedek and L. R. Rillet, Equitable traffic assignment with environmental cost functions, Journal Transportation Engineering, 124 (1998), 16-24.
[3]	E. Deakin, Sustainable develoment and sustaionable transportation: Strategies for economic prosperity environmental quality and equity, Technical Report, Institute of Urban and Region Development, University of California, Berkely, 2001.
[4]	F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Mathematical Programming, 85 (1999), 107-134. doi: 10.1007/s101070050048.
[5]	M. Fukushima and J. S. Pang, Convergence of a Smoothing Continuation Method for Mathematical Problems with Complementarity Constraints, Ill-posed Variational Problems and Regularization Techniques, Lecture Notes in Economics and Mathematical Systems (eds. M. Théra and R. Tichatschke), 477, Springer-Verlag, doi: 10.1007/978-3-642-45780-7.
[6]	C. M. Jeon and A. Amekudzi, Addressing sustainability in transportation systems, (French) [Definitions, Indicators and Metrics], Journal of Infrastucture Systems, 11 (2005), 31-50. Berlin/Heidelberg, 1999.
[7]	G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints, Annals of Operations Research, 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z.
[8]	Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996. doi: 10.1017/CBO9780511983658.
[9]	T. V. Mathew and S. Sharma, Capacity expansion problem for large urban transportation networks, Journal of Transportation Engineering, 135 (2009), 406-4015.
[10]	A. Nagurney, Sustainable Transportation Networks, Edward Elgar, Cheltenham, Glos,2000b.
[11]	A. Nagurney, Congested urban transportation networks and emission paradoxes, Transportation Research Part D, 5 (2000a), 145-151.
[12]	A. Nagurney, Q. Qiang and L. S. Nagurney, Environmental impact assessment of transportation networks with degradable links in an era of climate change, International Journal of Sustainable Transportation, 1 (2007), 29-51.
[13]	A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks, International Journal of Transportation, 4 (2010), 154-171.
[14]	A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks, International Journal of Transportation, 4 (2010), 154-171.
[15]	M. Patriksson, The traffic assignment problem: Models and Methods, VSP, Utrecht, The Netherlands, 1994.
[16]	R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer-Verlag, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[17]	S. Sharma and T. V. Mathew, Transportation network design considering emissions as bi-level optimization problem, in TBR 86th Annual Meeting Compendium of the Paper CD-ROM, Transportation Research Board, Washington, DC, 2007.
[18]	S. Sharma and S. Mishra, Optimal emission pricing models for containing carbon footprints due to vehicular pollution in a city network, Proceedings of Transportation Research Board 90th Annual Meeting, 2011.
[19]	S. Sharma, Transportation Network Design Considering Environmental Parameters and Demand Uncertainity, PhD thesis, Indian Institute of Technology, Bombay, India, 2009.
[20]	Y. Sheffi, Urban Transportation Networks, First edition, Mathematical Models [Equilibrium Analysis with Mathematical programming Methods], 416, Prentice-Hall, Englewood Cliffs, 1985.
[21]	S. Sugawara and D.A. Niemeier, How much can vehicle emissions be reduced?, (French) [exploratory analysis of an upper boundary using an emissions optimized trip assignment], Transportation Research Record, 1815 (2003), 29-37.
[22]	S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim, 11 (2001), 918-936. doi: 10.1137/S1052623499361233.
[23]	J. Y. Teng and G. H. Tzeng, A multiobjective programming approach for selecting non-independent transportation investment alternatives, Transportation Research Part B, 30 (1996), 291-307.
[24]	M. M. Venigalla, A. Chatterjee and M. S. Bronzini, A specialized equilibrium assignment algorithm for air quality modeling, Transportation Research Part D, 4 (1999), 29-44.
[25]	Y. Yin and S. Lawphongpanich, Internalizing emission externality on road networks, Transportation Research Part D, 11 (2006), 292-301.
[26]	Y. Yin and H. Lu, Traffic equilibrium problems with environmental concerns, Journal of Eastern Asia Society for Transportation Study, 3 (1999), 195-206.

show all references

References:

[1]	S. P. Anusha, Study of Influence of Lane Restrictions on Vehicular Emissions under the Heterogeneous Traffic Flow, MS thesis, Department of Civil Engineering, Indian Institute of Technology, Madras, 2007.
[2]	C. M. Benedek and L. R. Rillet, Equitable traffic assignment with environmental cost functions, Journal Transportation Engineering, 124 (1998), 16-24.
[3]	E. Deakin, Sustainable develoment and sustaionable transportation: Strategies for economic prosperity environmental quality and equity, Technical Report, Institute of Urban and Region Development, University of California, Berkely, 2001.
[4]	F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Mathematical Programming, 85 (1999), 107-134. doi: 10.1007/s101070050048.
[5]	M. Fukushima and J. S. Pang, Convergence of a Smoothing Continuation Method for Mathematical Problems with Complementarity Constraints, Ill-posed Variational Problems and Regularization Techniques, Lecture Notes in Economics and Mathematical Systems (eds. M. Théra and R. Tichatschke), 477, Springer-Verlag, doi: 10.1007/978-3-642-45780-7.
[6]	C. M. Jeon and A. Amekudzi, Addressing sustainability in transportation systems, (French) [Definitions, Indicators and Metrics], Journal of Infrastucture Systems, 11 (2005), 31-50. Berlin/Heidelberg, 1999.
[7]	G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints, Annals of Operations Research, 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z.
[8]	Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996. doi: 10.1017/CBO9780511983658.
[9]	T. V. Mathew and S. Sharma, Capacity expansion problem for large urban transportation networks, Journal of Transportation Engineering, 135 (2009), 406-4015.
[10]	A. Nagurney, Sustainable Transportation Networks, Edward Elgar, Cheltenham, Glos,2000b.
[11]	A. Nagurney, Congested urban transportation networks and emission paradoxes, Transportation Research Part D, 5 (2000a), 145-151.
[12]	A. Nagurney, Q. Qiang and L. S. Nagurney, Environmental impact assessment of transportation networks with degradable links in an era of climate change, International Journal of Sustainable Transportation, 1 (2007), 29-51.
[13]	A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks, International Journal of Transportation, 4 (2010), 154-171.
[14]	A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks, International Journal of Transportation, 4 (2010), 154-171.
[15]	M. Patriksson, The traffic assignment problem: Models and Methods, VSP, Utrecht, The Netherlands, 1994.
[16]	R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer-Verlag, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[17]	S. Sharma and T. V. Mathew, Transportation network design considering emissions as bi-level optimization problem, in TBR 86th Annual Meeting Compendium of the Paper CD-ROM, Transportation Research Board, Washington, DC, 2007.
[18]	S. Sharma and S. Mishra, Optimal emission pricing models for containing carbon footprints due to vehicular pollution in a city network, Proceedings of Transportation Research Board 90th Annual Meeting, 2011.
[19]	S. Sharma, Transportation Network Design Considering Environmental Parameters and Demand Uncertainity, PhD thesis, Indian Institute of Technology, Bombay, India, 2009.
[20]	Y. Sheffi, Urban Transportation Networks, First edition, Mathematical Models [Equilibrium Analysis with Mathematical programming Methods], 416, Prentice-Hall, Englewood Cliffs, 1985.
[21]	S. Sugawara and D.A. Niemeier, How much can vehicle emissions be reduced?, (French) [exploratory analysis of an upper boundary using an emissions optimized trip assignment], Transportation Research Record, 1815 (2003), 29-37.
[22]	S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim, 11 (2001), 918-936. doi: 10.1137/S1052623499361233.
[23]	J. Y. Teng and G. H. Tzeng, A multiobjective programming approach for selecting non-independent transportation investment alternatives, Transportation Research Part B, 30 (1996), 291-307.
[24]	M. M. Venigalla, A. Chatterjee and M. S. Bronzini, A specialized equilibrium assignment algorithm for air quality modeling, Transportation Research Part D, 4 (1999), 29-44.
[25]	Y. Yin and S. Lawphongpanich, Internalizing emission externality on road networks, Transportation Research Part D, 11 (2006), 292-301.
[26]	Y. Yin and H. Lu, Traffic equilibrium problems with environmental concerns, Journal of Eastern Asia Society for Transportation Study, 3 (1999), 195-206.

[1]	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 and Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
[2]	Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[3]	Zhi Lin, Zaiyun Peng. Algorithms for the Pareto solution of the multicriteria traffic equilibrium problem with capacity constraints of arcs. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022104
[4]	Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial and Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99
[5]	Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028
[6]	Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial and Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086
[7]	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
[8]	Yufeng Zhou, Bin Zheng, Jiafu Su, Yufeng Li. The joint location-transportation model based on grey bi-level programming for early post-earthquake relief. Journal of Industrial and Management Optimization, 2022, 18 (1) : 45-73. doi: 10.3934/jimo.2020142
[9]	Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[10]	Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
[11]	Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951
[12]	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
[13]	Lei Guo, Gui-Hua Lin. Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations. Journal of Industrial and Management Optimization, 2013, 9 (2) : 305-322. doi: 10.3934/jimo.2013.9.305
[14]	Tim Hoheisel, Christian Kanzow, Alexandra Schwartz. Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 49-60. doi: 10.3934/naco.2011.1.49
[15]	Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[16]	Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial and Management Optimization, 2019, 15 (1) : 59-79. doi: 10.3934/jimo.2018032
[17]	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
[18]	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
[19]	Zhe Zhang, Jiuping Xu. Bi-level multiple mode resource-constrained project scheduling problems under hybrid uncertainty. Journal of Industrial and Management Optimization, 2016, 12 (2) : 565-593. doi: 10.3934/jimo.2016.12.565
[20]	Gayatri Pany, Ram N. Mohapatra. A study on vector variational-like inequalities using convexificators and application to its bi-level form. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021161

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Robert Ebihart Msigwa Yue Lu Xiantao Xiao Liwei Zhang
on Google Scholar
Robert Ebihart Msigwa Yue Lu Xiantao Xiao Liwei Zhang

[Back to Top]