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

Robert  Ebihart  Msigwa; Yue  Lu; Xiantao  Xiao; Liwei  Zhang

doi:10.3934/naco.2015.5.135

Article Contents

2015, Volume 5, Issue 2: 135-149. Doi: 10.3934/naco.2015.5.135

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

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

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

Received: September 30, 2014

Revised: March 31, 2015

Published: May 2015

Abstract Related Papers Cited by

Abstract

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:

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

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

Citation:

Related Papers

Cited by

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.