Capacity Expansion Problem for Large Urban Transportation Networks
Publication: Journal of Transportation Engineering
Volume 135, Issue 7
Abstract
A traffic network design problem attempts to find optimal network expansion policies under budget constraints. This can be formulated as a bilevel optimization problem: the upper level determines the optimal link capacity expansion vector and the lower level determines the link flows subject to user equilibrium conditions. The upper level is a capacity expansion problem which minimizes the total system cost and can be solved using any optimization algorithm. In the present study, genetic algorithm (GA) is used in the upper level because of its modeling simplicity and ability to handle large problems. The proposed model is first applied to a small sized network and then to a medium sized test network and the results are compared with other existing solution approaches. The sensitivity analysis of the model is performed by designing the networks at different demand levels. The resilience of the solution when demand increases the design demand is also carried out. Finally, the network design for the city of Pune, India was taken as a case study. This is a large sized network having 1,131 links and 370 nodes. The capacity expansion is carried out under various budget scenarios and the results are discussed. This study shows the potential of GA to obtain a high quality solution for large network design problems.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers are grateful to Mr. Mallikarjun Setty and Dr. Tagore of the CES organization for providing Pune city data. They are also grateful to reviewers for their useful comments and suggestions.
References
Abdulaal, M., and LeBlanc, L. J. (1979). “Continuous equilibrium network design problem.” Transp. Res., Part B: Methodol., 13, 19–32.
Aggarwal, J., and Mathew, T. V. (2004). “Transit route network design using genetic algorithms.” J. Comput. Civ. Eng., 18(3), 248–256.
Allsop, R. E. (1974). “Some possibilities for using traffic control to influence trip distribution and route choice.” Proc., 6th Int. Symp. on Transportation and Traffic Theory, D. J. Buckley, ed., Elsevier, New York, 345–375.
Ceylan, H., and Bell, M. G. H. (2004). “Traffic signal timing optimization based on genetic algorithm approach, including driver’s routing.” Transp. Res., Part B: Methodol., 38, 329–342.
Chen, A., Ji, Z., and Recker, W. (2002). “Travel time reliability with risk sensitive travelers.” Transportation Research Record. 1783, Transportation Research Board, Washington, D.C., 27–33.
Chiou, S. W. (1999). “Optimization of area traffic control for equilibrium network flows.” Transp. Sci., 33(3), 279–289.
Chiou, S. W. (2005). “Bilevel programming for continuous network design problem.” Transp. Res., Part B: Methodol., 39, 361–383.
Clark, S., and Watling, D. (2005). “Modeling network travel time reliability under stochastic demand.” Transp. Res., Part B: Methodol., 39, 119–140.
Dafermos, S. (1980). “Traffic equilibrium and variational inequalities.” Transp. Sci., 14(1), 42–54.
Deb, K. (1998). Optimization for engineering design: Algorithms and examples, Prentice-Hall, New Delhi, India.
Fisk, C. S. (1984). “Game theory and transportation systems modelling.” Transp. Res., Part B: Methodol., 18, 301–313.
Friesz, T. L., Cho, H. J., Mehta, N. J., Tobin, R. L., and Anandalingam, G. (1992). “A simulated annealing approach to the network design problem with variational inequality constraints.” Transp. Sci., 26(1), 18–26.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, Mass.
LeBlanc, L. J. (1975). “An algorithm for discrete network design problem.” Transp. Sci., 9, 183–199.
Lim, Y., Heydecker, B. G., and Lee, S. (2005). “A continuous network design model in stochastic user equilibrium based on sensitivity analysis.” J. Adv. Transp., 39(1), 63–79.
Maher, M. J., Zhang, X., and Vleit, D. V. (2001). “A bilevel programming approach for trip matrix estimation and traffic control problems with stochastic user equilibrium link flows.” Transp. Res., Part B: Methodol., 35, 23–40.
Marcotte, P. (1983). “Network optimization with continuous control parameters.” Transp. Sci., 17, 181–197.
Meng, Q., Lee, D.-H., Yang, H., and Huang, H.-J. (2004). “Transportation network optimization problems with stochastic user equilibrium constraints.” Transportation Research Record. 1882, Transportation Research Board, Washington, D.C., 113–119.
Meng, Q., Yang, H., and Bell, M. G. H. (2001). “An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem.” Transp. Res., Part B: Methodol., 35, 83–105.
Rao, S. S. (1996). Engineering optimization: Theory and practice, Wiley, New York.
Smith, M. J. (1979). “Existence, uniqueness, and stability of traffic equilibria.” Transp. Res., Part B: Methodol., 13, 295–304.
Steenbrink, P. A. (1974). Optimization of transport network, Wiley, West Sussex, U.K.
Suwansirikul, C., Friesz, T. L., and Tobin, R. L. (1987). “Equilibrium decomposed optimization: A continuous network design problem.” Transp. Sci., 21(4), 254–263.
Thompson, D. R., and Bilbro, G. L. (2000). “Comparison of genetic algorithm with simulated annealing algorithm for design of an ATM network.” IEEE Commun. Lett., 4(8), 267–269.
Tobin, R. L., and Friesz, T. L. (1988). “Sensitivity analysis for equilibrium network flows.” Transp. Sci., 22(4), 242–250.
Ukkusuri, S. V., Mathew, T. V., and Waller, S. T. (2007). “Robust network design problem under demand uncertainty.” Comput. Aided Civ. Infrastruct. Eng., 22, 6–18.
Wong, S. C. (1997). “Group-based optimisation of signal timings using parallel computing.” Transp. Res., Part C: Emerg. Technol., 5(2), 123–129.
Wong, S. C., and Yang, H. (1997). “Reserve capacity of a signal controlled road network.” Transp. Res., Part B: Methodol., 31(5), 397–402.
Yan, H., and Lam, W. H. K. (1996). “Optimal road tolls under conditions of queuing and congestion.” Transp. Res., Part A: Policy Pract., 30(5), 319–332.
Yang, H. (1995). “Sensitivity analysis for queuing equilibrium and network flows and its application to traffic control.” Math. Comput. Modell., 22, 247–258.
Yang, H. (1997). “Sensitivity analysis for elastic demand network equilibrium problem with applications.” Transp. Res., Part B: Methodol., 31, 55–70.
Yang, H., and Bell, M. G. H. (2001). “Transport bilevel programming problems: Recent methodological advances.” Transp. Res., Part B: Methodol., 35, 1–4.
Yin, Y. (2000). “Genetic algorithms based approach for bi-level programming models.” J. Transp. Eng., 126(2), 115–120.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 135 • Issue 7 • July 2009
Pages: 406 - 415
Copyright
© 2009 ASCE.
History
Received: Jun 15, 2006
Accepted: Dec 22, 2008
Published online: Jun 15, 2009
Published in print: Jul 2009
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.