IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v46y2012i10p1504-1518.html
   My bibliography  Save this article

Dynamic congestion pricing with demand uncertainty: A robust optimization approach

Author

Listed:
  • Chung, Byung Do
  • Yao, Tao
  • Friesz, Terry L.
  • Liu, Hongcheng

Abstract

In this paper, we consider dynamic congestion pricing in the presence of demand uncertainty. In particular, we apply a robust optimization (RO) approach based on a bi-level cellular particle swarm optimization (BCPSO) to optimal congestion pricing problems when flows correspond to dynamic user equilibrium on the network of interest. Such a formulation is recognized as a second-best pricing problem, and we refer to it as the dynamic optimal toll problem with equilibrium constraints (DOTPEC). We then present numerical experiments in which BCPSO is compared with two alternative robust dynamic solution approaches: bi-level simulated annealing (BSA) and cutting plane-based simulated annealing (CPSA), as well as a nominal dynamic solution and a robust static solution. We show that robust dynamic solutions improve the worst case, average, and stability of total travel cost in comparison with the nominal dynamic and the robust static solutions. The numerical results also show that BCPSO outperforms BSA and CPSA in terms of solution quality and computational efficiency.

Suggested Citation

  • Chung, Byung Do & Yao, Tao & Friesz, Terry L. & Liu, Hongcheng, 2012. "Dynamic congestion pricing with demand uncertainty: A robust optimization approach," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1504-1518.
    • Handle: RePEc:eee:transb:v:46:y:2012:i:10:p:1504-1518
    DOI: 10.1016/j.trb.2012.07.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261512001002
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2012.07.007?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. AndrÊ de Palma & Robin Lindsey, 2000. "Private toll roads: Competition under various ownership regimes," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 34(1), pages 13-35.
    2. Arnott, Richard & Kraus, Marvin, 1998. "When are anonymous congestion charges consistent with marginal cost pricing?," Journal of Public Economics, Elsevier, vol. 67(1), pages 45-64, January.
    3. Yang, Hai & Meng, Qiang & Lee, Der-Horng, 2004. "Trial-and-error implementation of marginal-cost pricing on networks in the absence of demand functions," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 477-493, July.
    4. Dung-Ying Lin & Avinash Unnikrishnan & S. Waller, 2011. "A Dual Variable Approximation Based Heuristic for Dynamic Congestion Pricing," Networks and Spatial Economics, Springer, vol. 11(2), pages 271-293, June.
    5. Dimitris Bertsimas & Omid Nohadani & Kwong Meng Teo, 2010. "Robust Optimization for Unconstrained Simulation-Based Problems," Operations Research, INFORMS, vol. 58(1), pages 161-178, February.
    6. Friesz, Terry L. & Kim, Taeil & Kwon, Changhyun & Rigdon, Matthew A., 2011. "Approximate network loading and dual-time-scale dynamic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 176-207, January.
    7. Wie, Byung-Wook & Tobin, Roger L., 1998. "Dynamic congestion pricing models for general traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 32(5), pages 313-327, June.
    8. Vickrey, William S, 1969. "Congestion Theory and Transport Investment," American Economic Review, American Economic Association, vol. 59(2), pages 251-260, May.
    9. de Palma, André & Kilani, Moez & Lindsey, Robin, 2005. "Congestion pricing on a road network: A study using the dynamic equilibrium simulator METROPOLIS," Transportation Research Part A: Policy and Practice, Elsevier, vol. 39(7-9), pages 588-611.
    10. A. Ben-Tal & A. Nemirovski, 1998. "Robust Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 769-805, November.
    11. Braid, Ralph M., 1996. "Peak-Load Pricing of a Transportation Route with an Unpriced Substitute," Journal of Urban Economics, Elsevier, vol. 40(2), pages 179-197, September.
    12. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    13. Arnott, R. & de Palma, A. & Lindsey, R., 1990. "Departure time and route choice for the morning commute," Transportation Research Part B: Methodological, Elsevier, vol. 24(3), pages 209-228, June.
    14. Dimitris Bertsimas & Omid Nohadani & Kwong Meng Teo, 2010. "Nonconvex Robust Optimization for Problems with Constraints," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 44-58, February.
    15. Terry L. Friesz & David Bernstein & Tony E. Smith & Roger L. Tobin & B. W. Wie, 1993. "A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem," Operations Research, INFORMS, vol. 41(1), pages 179-191, February.
    16. Takeshi Nagae & Takashi Akamatsu, 2006. "Dynamic Revenue Management of a Toll Road Project under Transportation Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 6(3), pages 345-357, September.
    17. Yang, Hai & Hai-Jun, Huang, 1997. "Analysis of the time-varying pricing of a bottleneck with elastic demand using optimal control theory," Transportation Research Part B: Methodological, Elsevier, vol. 31(6), pages 425-440, November.
    18. Henderson, J. V., 1974. "Road congestion : A reconsideration of pricing theory," Journal of Urban Economics, Elsevier, vol. 1(3), pages 346-365, July.
    19. Li, Michael Z. F., 2002. "The role of speed-flow relationship in congestion pricing implementation with an application to Singapore," Transportation Research Part B: Methodological, Elsevier, vol. 36(8), pages 731-754, September.
    20. Terry L. Friesz & Hsun-Jung Cho & Nihal J. Mehta & Roger L. Tobin & G. Anandalingam, 1992. "A Simulated Annealing Approach to the Network Design Problem with Variational Inequality Constraints," Transportation Science, INFORMS, vol. 26(1), pages 18-26, February.
    21. Lou, Yingyan & Yin, Yafeng & Lawphongpanich, Siriphong, 2010. "Robust congestion pricing under boundedly rational user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 15-28, January.
    22. Xuegang (Jeff)Ban & Shu Lu & Michael Ferris & Henry X. Liu, 2009. "Risk Averse Second Best Toll Pricing," Springer Books, in: William H. K. Lam & S. C. Wong & Hong K. Lo (ed.), Transportation and Traffic Theory 2009: Golden Jubilee, chapter 0, pages 197-218, Springer.
    23. Dimitris Bertsimas & Omid Nohadani, 2010. "Robust optimization with simulated annealing," Journal of Global Optimization, Springer, vol. 48(2), pages 323-334, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Qixiu Cheng & Zhiyuan Liu & Feifei Liu & Ruo Jia, 2017. "Urban dynamic congestion pricing: an overview and emerging research needs," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 21(0), pages 3-18, August.
    2. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    3. Tolou Esfandeh & Rajan Batta & Changhyun Kwon, 2018. "Time-Dependent Hazardous-Materials Network Design Problem," Transportation Science, INFORMS, vol. 52(2), pages 454-473, March.
    4. Chen, Yiwei & Wang, Hai, 2018. "Pricing for a Last-Mile Transportation System," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 57-69.
    5. Beheshtian, Arash & Richard Geddes, R. & Rouhani, Omid M. & Kockelman, Kara M. & Ockenfels, Axel & Cramton, Peter & Do, Wooseok, 2020. "Bringing the efficiency of electricity market mechanisms to multimodal mobility across congested transportation systems," Transportation Research Part A: Policy and Practice, Elsevier, vol. 131(C), pages 58-69.
    6. Zhang, Wei & (Ato) Xu, Wangtu, 2017. "Simulation-based robust optimization for the schedule of single-direction bus transit route: The design of experiment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 203-230.
    7. An, Kun & Lo, Hong K., 2016. "Two-phase stochastic program for transit network design under demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 157-181.
    8. Shao, Jing & Yang, Hangjun & Xing, Xiaoqiang & Yang, Liu, 2016. "E-commerce and traffic congestion: An economic and policy analysis," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 91-103.
    9. Jorge, Diana & Molnar, Goran & de Almeida Correia, Gonçalo Homem, 2015. "Trip pricing of one-way station-based carsharing networks with zone and time of day price variations," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 461-482.
    10. Schwarz, Gregor & Bichler, Martin, 2022. "How to trade thirty thousand products: A wholesale market design for road capacity," Transportation Research Part A: Policy and Practice, Elsevier, vol. 164(C), pages 167-185.
    11. Pi, Xidong & Qian, Zhen (Sean), 2017. "A stochastic optimal control approach for real-time traffic routing considering demand uncertainties and travelers’ choice heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 710-732.
    12. Chiou, Suh-Wen, 2015. "A cutting plane projection method for bi-level area traffic control optimization with uncertain travel demand," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 390-403.
    13. Ma, Rui & Ban, Xuegang (Jeff) & Szeto, W.Y., 2017. "Emission modeling and pricing on single-destination dynamic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 100(C), pages 255-283.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ma, Rui & Ban, Xuegang (Jeff) & Szeto, W.Y., 2017. "Emission modeling and pricing on single-destination dynamic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 100(C), pages 255-283.
    2. Dung-Ying Lin & Avinash Unnikrishnan & S. Waller, 2011. "A Dual Variable Approximation Based Heuristic for Dynamic Congestion Pricing," Networks and Spatial Economics, Springer, vol. 11(2), pages 271-293, June.
    3. Qixiu Cheng & Zhiyuan Liu & Feifei Liu & Ruo Jia, 2017. "Urban dynamic congestion pricing: an overview and emerging research needs," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 21(0), pages 3-18, August.
    4. Kenneth Small, 2015. "The Bottleneck Model: An Assessment and Interpretation," Working Papers 141506, University of California-Irvine, Department of Economics.
    5. Small, Kenneth A., 2015. "The bottleneck model: An assessment and interpretation," Economics of Transportation, Elsevier, vol. 4(1), pages 110-117.
    6. Li, Zhi-Chun & Huang, Hai-Jun & Yang, Hai, 2020. "Fifty years of the bottleneck model: A bibliometric review and future research directions," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 311-342.
    7. Loukas Dimitriou & Theodore Tsekeris, 2009. "Evolutionary game-theoretic model for dynamic congestion pricing in multi-class traffic networks," Netnomics, Springer, vol. 10(1), pages 103-121, April.
    8. Emilio Carrizosa & Frédéric Messine, 2021. "An interval branch and bound method for global Robust optimization," Journal of Global Optimization, Springer, vol. 80(3), pages 507-522, July.
    9. C. Robin Lindsey & Erik T. Verhoef, 2000. "Traffic Congestion and Congestion Pricing," Tinbergen Institute Discussion Papers 00-101/3, Tinbergen Institute.
    10. Braid, Ralph M., 2018. "Partial peak-load pricing of a transportation bottleneck with homogeneous and heterogeneous values of time," Economics of Transportation, Elsevier, vol. 16(C), pages 29-41.
    11. de Palma, André & Kilani, Moez & Lindsey, Robin, 2005. "Congestion pricing on a road network: A study using the dynamic equilibrium simulator METROPOLIS," Transportation Research Part A: Policy and Practice, Elsevier, vol. 39(7-9), pages 588-611.
    12. Yu Nie, 2015. "A New Tradable Credit Scheme for the Morning Commute Problem," Networks and Spatial Economics, Springer, vol. 15(3), pages 719-741, September.
    13. Feng Xiao & Zhen Qian & H. Zhang, 2011. "The Morning Commute Problem with Coarse Toll and Nonidentical Commuters," Networks and Spatial Economics, Springer, vol. 11(2), pages 343-369, June.
    14. Long, Jiancheng & Szeto, W.Y. & Gao, Ziyou & Huang, Hai-Jun & Shi, Qin, 2016. "The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 179-206.
    15. Erik Verhoef, 1997. "Time-Varying Tolls in a Dynamic Model of Road Traffic Congestion with Elastic Demand," Tinbergen Institute Discussion Papers 97-028/3, Tinbergen Institute.
    16. Liu, Yang & Nie, Yu (Marco) & Hall, Jonathan, 2015. "A semi-analytical approach for solving the bottleneck model with general user heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 56-70.
    17. Verhoef, Erik T. & Koh, Andrew & Shepherd, Simon, 2010. "Pricing, capacity and long-run cost functions for first-best and second-best network problems," Transportation Research Part B: Methodological, Elsevier, vol. 44(7), pages 870-885, August.
    18. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    19. Han, Ke & Szeto, W.Y. & Friesz, Terry L., 2015. "Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance," Transportation Research Part B: Methodological, Elsevier, vol. 79(C), pages 16-49.
    20. Li-Jun Tian & Hai-Jun Huang & Zi-You Gao, 2012. "A Cumulative Perceived Value-Based Dynamic User Equilibrium Model Considering the Travelers’ Risk Evaluation on Arrival Time," Networks and Spatial Economics, Springer, vol. 12(4), pages 589-608, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:46:y:2012:i:10:p:1504-1518. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.