American Institute of Mathematical Sciences

Advanced
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

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 & 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, (2007).   Google Scholar

[2]

C. M. Benedek and L. R. Rillet, Equitable traffic assignment with environmental cost functions,, \emph{Journal Transportation Engineering}, 124 (1998), 16.   Google Scholar

[3]

E. Deakin, Sustainable develoment and sustaionable transportation: Strategies for economic prosperity environmental quality and equity,, Technical Report, (2001).   Google Scholar

[4]

F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints,, \emph{Mathematical Programming}, 85 (1999), 107.  doi: 10.1007/s101070050048.  Google Scholar

[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,, \emph{Lecture Notes in Economics and Mathematical Systems} (eds. M. Théra and R. Tichatschke), ().  doi: 10.1007/978-3-642-45780-7.  Google Scholar

[6]

C. M. Jeon and A. Amekudzi, Addressing sustainability in transportation systems,, (French) [Definitions, 11 (2005), 31.   Google Scholar

[7]

G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints,, \emph{Annals of Operations Research}, 133 (2005), 63.  doi: 10.1007/s10479-004-5024-z.  Google Scholar

[8]

Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511983658.  Google Scholar

[9]

T. V. Mathew and S. Sharma, Capacity expansion problem for large urban transportation networks,, \emph{Journal of Transportation Engineering}, 135 (2009), 406.   Google Scholar

[10]

A. Nagurney, Sustainable Transportation Networks,, Edward Elgar, ().   Google Scholar

[11]

A. Nagurney, Congested urban transportation networks and emission paradoxes,, \emph{Transportation Research Part D}, 5 (): 145.   Google Scholar

[12]

A. Nagurney, Q. Qiang and L. S. Nagurney, Environmental impact assessment of transportation networks with degradable links in an era of climate change,, \emph{International Journal of Sustainable Transportation}, 1 (2007), 29.   Google Scholar

[13]

A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks,, \emph{International Journal of Transportation}, 4 (2010), 154.   Google Scholar

[14]

A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks,, \emph{International Journal of Transportation}, 4 (2010), 154.   Google Scholar

[15]

M. Patriksson, The traffic assignment problem: Models and Methods,, VSP, (1994).   Google Scholar

[16]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[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, (2007).   Google Scholar

[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).   Google Scholar

[19]

S. Sharma, Transportation Network Design Considering Environmental Parameters and Demand Uncertainity,, PhD thesis, (2009).   Google Scholar

[20]

Y. Sheffi, Urban Transportation Networks,, First edition, (1985).   Google Scholar

[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], 1815 (2003), 29.   Google Scholar

[22]

S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints,, \emph{SIAM J. Optim}, 11 (2001), 918.  doi: 10.1137/S1052623499361233.  Google Scholar

[23]

J. Y. Teng and G. H. Tzeng, A multiobjective programming approach for selecting non-independent transportation investment alternatives,, \emph{Transportation Research Part B}, 30 (1996), 291.   Google Scholar

[24]

M. M. Venigalla, A. Chatterjee and M. S. Bronzini, A specialized equilibrium assignment algorithm for air quality modeling,, \emph{Transportation Research Part D}, 4 (1999), 29.   Google Scholar

[25]

Y. Yin and S. Lawphongpanich, Internalizing emission externality on road networks,, \emph{Transportation Research Part D}, 11 (2006), 292.   Google Scholar

[26]

Y. Yin and H. Lu, Traffic equilibrium problems with environmental concerns,, \emph{Journal of Eastern Asia Society for Transportation Study}, 3 (1999), 195.   Google Scholar

show all references

References:
[1]

S. P. Anusha, Study of Influence of Lane Restrictions on Vehicular Emissions under the Heterogeneous Traffic Flow,, MS thesis, (2007).   Google Scholar

[2]

C. M. Benedek and L. R. Rillet, Equitable traffic assignment with environmental cost functions,, \emph{Journal Transportation Engineering}, 124 (1998), 16.   Google Scholar

[3]

E. Deakin, Sustainable develoment and sustaionable transportation: Strategies for economic prosperity environmental quality and equity,, Technical Report, (2001).   Google Scholar

[4]

F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints,, \emph{Mathematical Programming}, 85 (1999), 107.  doi: 10.1007/s101070050048.  Google Scholar

[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,, \emph{Lecture Notes in Economics and Mathematical Systems} (eds. M. Théra and R. Tichatschke), ().  doi: 10.1007/978-3-642-45780-7.  Google Scholar

[6]

C. M. Jeon and A. Amekudzi, Addressing sustainability in transportation systems,, (French) [Definitions, 11 (2005), 31.   Google Scholar

[7]

G. H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints,, \emph{Annals of Operations Research}, 133 (2005), 63.  doi: 10.1007/s10479-004-5024-z.  Google Scholar

[8]

Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511983658.  Google Scholar

[9]

T. V. Mathew and S. Sharma, Capacity expansion problem for large urban transportation networks,, \emph{Journal of Transportation Engineering}, 135 (2009), 406.   Google Scholar

[10]

A. Nagurney, Sustainable Transportation Networks,, Edward Elgar, ().   Google Scholar

[11]

A. Nagurney, Congested urban transportation networks and emission paradoxes,, \emph{Transportation Research Part D}, 5 (): 145.   Google Scholar

[12]

A. Nagurney, Q. Qiang and L. S. Nagurney, Environmental impact assessment of transportation networks with degradable links in an era of climate change,, \emph{International Journal of Sustainable Transportation}, 1 (2007), 29.   Google Scholar

[13]

A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks,, \emph{International Journal of Transportation}, 4 (2010), 154.   Google Scholar

[14]

A. Nagurney, Z. Liu and T. Woolley, Sustainable supply chain and transportation networks,, \emph{International Journal of Transportation}, 4 (2010), 154.   Google Scholar

[15]

M. Patriksson, The traffic assignment problem: Models and Methods,, VSP, (1994).   Google Scholar

[16]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[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, (2007).   Google Scholar

[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).   Google Scholar

[19]

S. Sharma, Transportation Network Design Considering Environmental Parameters and Demand Uncertainity,, PhD thesis, (2009).   Google Scholar

[20]

Y. Sheffi, Urban Transportation Networks,, First edition, (1985).   Google Scholar

[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], 1815 (2003), 29.   Google Scholar

[22]

S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints,, \emph{SIAM J. Optim}, 11 (2001), 918.  doi: 10.1137/S1052623499361233.  Google Scholar

[23]

J. Y. Teng and G. H. Tzeng, A multiobjective programming approach for selecting non-independent transportation investment alternatives,, \emph{Transportation Research Part B}, 30 (1996), 291.   Google Scholar

[24]

M. M. Venigalla, A. Chatterjee and M. S. Bronzini, A specialized equilibrium assignment algorithm for air quality modeling,, \emph{Transportation Research Part D}, 4 (1999), 29.   Google Scholar

[25]

Y. Yin and S. Lawphongpanich, Internalizing emission externality on road networks,, \emph{Transportation Research Part D}, 11 (2006), 292.   Google Scholar

[26]

Y. Yin and H. Lu, Traffic equilibrium problems with environmental concerns,, \emph{Journal of Eastern Asia Society for Transportation Study}, 3 (1999), 195.   Google Scholar

[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 & Management Optimization, 2019  doi: 10.3934/jimo.2019134
[2]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[3]

Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99
[4]

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 & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086
[5]

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
[6]

Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028
[7]

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 & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[8]

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 & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
[9]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951
[10]

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
[11]

Lei Guo, Gui-Hua Lin. Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations. Journal of Industrial & Management Optimization, 2013, 9 (2) : 305-322. doi: 10.3934/jimo.2013.9.305
[12]

Tim Hoheisel, Christian Kanzow, Alexandra Schwartz. Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 49-60. doi: 10.3934/naco.2011.1.49
[13]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[14]

Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial & Management Optimization, 2019, 15 (1) : 59-79. doi: 10.3934/jimo.2018032
[15]

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
[16]

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
[17]

Zhe Zhang, Jiuping Xu. Bi-level multiple mode resource-constrained project scheduling problems under hybrid uncertainty. Journal of Industrial & Management Optimization, 2016, 12 (2) : 565-593. doi: 10.3934/jimo.2016.12.565
[18]

Bettina Klaus, Frédéric Payot. Paths to stability in the assignment problem. Journal of Dynamics & Games, 2015, 2 (3&4) : 257-287. doi: 10.3934/jdg.2015004
[19]

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
[20]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

 Impact Factor: 

Tools

Metrics

  • PDF downloads (32)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences