Combined Decision Making of Congestion Pricing and Capacity Expansion: Genetic Algorithm Approach
Publication: Journal of Transportation Engineering
Volume 140, Issue 8
Abstract
This paper presents a solution methodology that can be used to determine the optimal solution for the combined congestion pricing and capacity expansion problems. A bilevel genetic algorithm (GA)-based optimization solution methodology is proposed to determine the optimal toll location, toll rate, percentage capacity expansion, and location for the expansion simultaneously. The upper-level subprogram minimizes the total system travel cost given certain budget and toll constraints. The lower-level subprogram is a user equilibrium problem where all users try to find the route that minimizes their own travel cost (or time). The budget constraint is handled using a penalty parameter. The demand is assumed to be fixed and given a priori. The proposed GA model is applied to Sioux Falls network, which has 76 links and 24 origin-destination (OD)-pairs, assuming homogeneous users. The optimal solution is thus identified. Sensitivity analyses are conducted for the budget and penalty parameter. The proposed methodology will be a very useful tool for transportation network planners for allocation of budgets and prioritization of links for improvements and congestion pricing.
Get full access to this article
View all available purchase options and get full access to this article.
References
Bar-Gera, H. (2010). “Transportation test problems.” 〈http://www.bgu.ac.il/~bargera/tntp/〉 (Apr. 16, 2013).
Bar-Gera, H., Hellman, F., and Patriksson, M. (2013). “Computational precision of traffic equilibria sensitivities in automatic network design and road pricing.” Transp. Res. Part B, 57, 485–500.
Chen, A., and Yang, C. (1992). “Stochastic transportation network design problem with spatial equity constraint.”, Transportation Research Board, Washington, DC, 97–104.
Clegg, J., Smith, M., Xiang, Y., and Yarrow, R. (2001). “Bi-level programming applied to optimizing urban transportation.” Transp. Res. Part B, 35(1), 41–70.
Cree, N. D., Maher, M. J., and Paechter, B. (1998). “The continuous equilibrium optimal network design problem: A genetic approach.” Transportation networks: Recent methodological advances, Pergamon, Amsterdam, 163–174.
Ekström, J., Sumalee, A., and Lo, H. K. (2012). “Optimizing toll locations and levels using a mixed integer linear approximation approach.” Transp. Res. Part B, 46(7), 834–854.
Fan, W. (2004). “Optimal transit route network design problem: Algorithms, implementations, and numerical results.” Ph.D. dissertation, Univ. of Texas at Austin, Austin, TX.
Fan, W., and Machemehl, R. B. (2006). “Optimal transit route network design problem with variable transit demand: A genetic algorithm approach.” J. Transp. Eng., 40–51.
Fan, W., and Machemehl, R. B. (2011). “Bi-level optimization model for public transportation network redesign problem: Accounting for equity issues.”, Transportation Research Board, Washington, DC, 151–162.
Farahani, R. Z., Miandoabchi, E., Szeto, W. Y., and Rashidi, H. (2013). “A review of urban transportation network design problems.” Eur. J. Oper. Res., 229(2), 281–302.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, London.
Hearn, D. W., and Ramana, M. V. (1998). “Solving congestion toll pricing models.” Equilibrium and Advanced Transportation Modelling, Springer, New York.
Holland, J. H. (1975). Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, MI.
LeBlanc, L. J., Morlok, E. K., and Pierskalla, W. P. (1975). “An efficient approach to solving the road network equilibrium traffic assignment problem.” Transp. Res., 9(5), 309–318.
Li, C. M., Yang, H., Zhu, D. L., and Meng, Q. (2012). “A global optimization method for continuous network design problems.” Transp. Res. Part B, 46(9), 1144–1158.
Lo, H., and Szeto, W. Y. (2003). “Time-dependent transport network design: A study of budget sensitivity.” J. East. Asia Soc. Transp. Stud., 5, 1124–1139.
Mathew, T. V., and Sharma, S. (2009). “Capacity expansion problem for large urban transportation networks.” J. Transp. Eng., 406–415.
Miandoabchi, E., Daneshzand, F., Szeto, W. Y., and Farahani, R. Z. (2013). “Multi-objective discrete urban road network design.” Comput. Oper. Res., 40(10), 2429–2449.
Miandoabchi, E., and Farahani, R. Z. (2011). “Optimizing reserve capacity of urban road networks in a discrete network design problem.” Adv. Eng. Softw., 42(12), 1041–1050.
Michalewicz, Z. (1999). Genetic algorithms + Data structure = Evolution programs, 3rd Ed., Springer, New York.
Ordonez, F., and Zhao, J. (2007). “Robust capacity expansion of network flows.” Networks, 50(2), 136–145.
Recker, W., et al. (2005). Considering risk-taking behavior in travel time reliability, Institute of Transportation Studies, Univ. of California, Irvine, CA.
Sheffi, Y. (1984). Urban transportation networks: Equilibrium analysis with mathematical programming methods, Prentice-Hall, Englewood Cliffs, NJ.
Shepherd, S., and Sumalee, A. (2004). “A genetic algorithm based approach to optimal toll level and locations problems.” Network Spat. Econ., 4(2), 161–179.
Verhoef, E. T. (2002). “Second-best congestion pricing in general networks: Heuristic algorithms for finding second-best optimal toll levels and toll points.” Transp. Res. Part B, 36(8), 707–729.
Verhoef, E. T., Nijkamp, P., and Ritveld, P. (1996). “Second-best congestion pricing: The case of an untolled alternative.” J. Urban Econ., 40(3), 279–302.
Wang, S., Meng, Q., and Yang, H. (2013). “Global optimization algorithms for the discrete network design problem.” Transp. Res. Part B, 50, 42–60.
Yang, H. (1996). “Equilibrium network traffic signal setting under conditions of queuing and congestion.” 4th Applications of Advanced Technologies in Transportation Engineering Int. Conf., Capri, Italy, 578–582.
Yang, H., and Bell, M. G. H. (1997). “Traffic restraint, road pricing and network equilibrium.” Transp. Res. Part B, 31(4), 303–314.
Yang, H., and Bell, M. G. H. (1998). “Models and algorithms for road network design: A review and some new development.” Transp. Rev., 18(3), 257–278.
Yang, H., and Huang, H. J. (2005). Mathematical and economic theory of road pricing, Emerald Group Publishing Limited, Bradford, U.K.
Yang, H., and Zhang, X. (2003). “Optimal toll design in second-best link-based congestion pricing.” Transp. Res. Rec., 1857, 85–92.
Zhang, H., and Gao, Z. (2009). “Bi-level programming model and solution method for mixed transportation network design problem.” J. Syst. Sci. Complex., 22, 446–459.
Zhang, L., and Sun, J. (2013). “Dual-based heuristic for optimal cordon pricing design.”J. Transp. Eng., 1105–1116.
Zhang, X., and Yang, H. (2004). “The optimal cordon-based network congestion pricing problem.” Transp. Res. Part B, 38(6), 517–537.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 140 • Issue 8 • August 2014
Copyright
© 2014 American Society of Civil Engineers.
History
Received: Nov 3, 2013
Accepted: Mar 25, 2014
Published online: Apr 29, 2014
Published in print: Aug 1, 2014
Discussion open until: Sep 29, 2014
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.