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

Optimal multi-step toll design under general user heterogeneity

Author

Listed:
  • Chen, Hongyu
  • Nie, Yu (Marco)
  • Yin, Yafeng

Abstract

This paper studies the optimal multi-step toll design problem for the bottleneck model with general user heterogeneity. The design model is formulated as a mathematical program with equilibrium constraints (MPEC), which is NP-hard due to non-convexity in both the objective function and the feasible set. An analytical method is proposed to solve the MPEC by decomposing it into smaller and easier quadratic programs, each corresponding to a unique departure order of different user classes. The quadratic programs are defined on a polyhedral set, which makes it easier to identify a local optimum. Importantly, each quadratic program is constrained by a set of linear feasibility cuts that define the presence of each user class in the arrival window. We prove that the proposed method ensures global optimality provided that each quadratic program can be solved globally. To obviate enumerating all departure orders, a heuristic method is developed to navigate through the solution space by using the multipliers associated with the feasibility cuts. Numerical experiments are conducted on several small examples to validate the proposed methodology. These experiments show that the proposed heuristic method is effective in finding near-optimal solutions within a relatively small number of iterations.

Suggested Citation

  • Chen, Hongyu & Nie, Yu (Marco) & Yin, Yafeng, 2015. "Optimal multi-step toll design under general user heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 775-793.
    • Handle: RePEc:eee:transb:v:81:y:2015:i:p3:p:775-793
    DOI: 10.1016/j.trb.2015.06.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515001459
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2015.06.016?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. van den Berg, Vincent A.C., 2014. "Coarse tolling with heterogeneous preferences," Transportation Research Part B: Methodological, Elsevier, vol. 64(C), pages 1-23.
    2. Robin Lindsey, C. & van den Berg, Vincent A.C. & Verhoef, Erik T., 2012. "Step tolling with bottleneck queuing congestion," Journal of Urban Economics, Elsevier, vol. 72(1), pages 46-59.
    3. Liu, Yang & Nie, Yu (Marco), 2011. "Morning commute problem considering route choice, user heterogeneity and alternative system optima," Transportation Research Part B: Methodological, Elsevier, vol. 45(4), pages 619-642.
    4. Robin Lindsey, 2004. "Existence, Uniqueness, and Trip Cost Function Properties of User Equilibrium in the Bottleneck Model with Multiple User Classes," Transportation Science, INFORMS, vol. 38(3), pages 293-314, August.
    5. Kenneth A. Small & Clifford Winston & Jia Yan, 2005. "Uncovering the Distribution of Motorists' Preferences for Travel Time and Reliability," Econometrica, Econometric Society, vol. 73(4), pages 1367-1382, July.
    6. Vickrey, William S, 1969. "Congestion Theory and Transport Investment," American Economic Review, American Economic Association, vol. 59(2), pages 251-260, May.
    7. Yang, Hai & Meng, Qiang, 1998. "Departure time, route choice and congestion toll in a queuing network with elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 32(4), pages 247-260, May.
    8. Arnott, Richard & de Palma, Andre & Lindsey, Robin, 1990. "Economics of a bottleneck," Journal of Urban Economics, Elsevier, vol. 27(1), pages 111-130, January.
    9. Arnott Richard & Kraus Marvin, 1995. "Financing Capacity in the Bottleneck Model," Journal of Urban Economics, Elsevier, vol. 38(3), pages 272-290, November.
    10. Xiao, Feng & Shen, Wei & Michael Zhang, H., 2012. "The morning commute under flat toll and tactical waiting," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1346-1359.
    11. van den Berg, Vincent & Verhoef, Erik T., 2011. "Congestion tolling in the bottleneck model with heterogeneous values of time," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 60-78, January.
    12. Laih, Chen-Hsiu, 1994. "Queueing at a bottleneck with single- and multi-step tolls," Transportation Research Part A: Policy and Practice, Elsevier, vol. 28(3), pages 197-208, May.
    13. 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.
    14. Arnott, Richard & de Palma, Andre & Lindsey, Robin, 1992. "Route choice with heterogeneous drivers and group-specific congestion costs," Regional Science and Urban Economics, Elsevier, vol. 22(1), pages 71-102, March.
    15. Gordon F. Newell, 1987. "The Morning Commute for Nonidentical Travelers," Transportation Science, INFORMS, vol. 21(2), pages 74-88, May.
    16. 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.
    17. van den Berg, Vincent & Verhoef, Erik T., 2011. "Winning or losing from dynamic bottleneck congestion pricing?: The distributional effects of road pricing with heterogeneity in values of time and schedule delay," Journal of Public Economics, Elsevier, vol. 95(7-8), pages 983-992, August.
    18. Small, Kenneth A., 1983. "The incidence of congestion tolls on urban highways," Journal of Urban Economics, Elsevier, vol. 13(1), pages 90-111, January.
    19. Ramadurai, Gitakrishnan & Ukkusuri, Satish V. & Zhao, Jinye & Pang, Jong-Shi, 2010. "Linear complementarity formulation for single bottleneck model with heterogeneous commuters," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 193-214, February.
    20. Chris Hendrickson & George Kocur, 1981. "Schedule Delay and Departure Time Decisions in a Deterministic Model," Transportation Science, INFORMS, vol. 15(1), pages 62-77, February.
    21. van den Berg, Vincent & Verhoef, Erik T., 2011. "Winning or losing from dynamic bottleneck congestion pricing?," Journal of Public Economics, Elsevier, vol. 95(7), pages 983-992.
    22. Doan, Kien & Ukkusuri, Satish & Han, Lanshan, 2011. "On the existence of pricing strategies in the discrete time heterogeneous single bottleneck model," Transportation Research Part B: Methodological, Elsevier, vol. 45(9), pages 1483-1500.
    23. Small, Kenneth A, 1982. "The Scheduling of Consumer Activities: Work Trips," American Economic Review, American Economic Association, vol. 72(3), pages 467-479, June.
    24. 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.
    25. Chen-Hsiu Laih, 2004. "Effects of the optimal step toll scheme on equilibrium commuter behaviour," Applied Economics, Taylor & Francis Journals, vol. 36(1), pages 59-81.
    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. Li, Zhi-Chun & Lam, William H.K. & Wong, S.C., 2017. "Step tolling in an activity-based bottleneck model," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 306-334.
    2. Zhu, Tingting & Li, Yao & Long, Jiancheng, 2022. "Departure time choice equilibrium and tolling strategies for a bottleneck with continuous scheduling preference," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    3. Xu, Da & Guo, Xiaolei & Zhang, Guoqing, 2019. "Constrained optimization for bottleneck coarse tolling," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 1-22.
    4. Khan, Zaid & Amin, Saurabh, 2018. "Bottleneck model with heterogeneous information," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 157-190.
    5. Amirgholy, Mahyar & Shahabi, Mehrdad & Gao, H. Oliver, 2017. "Optimal design of sustainable transit systems in congested urban networks: A macroscopic approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 261-285.
    6. Vincent van den Berg, "undated". "Self-financing roads under coarse tolling and heterogeneous preferences," Tinbergen Institute Discussion Papers 22-045/VIII, Tinbergen Institute.
    7. Gonzales, Eric J., 2016. "Demand responsive transit systems with time-dependent demand: User equilibrium, system optimum, and management strategyAuthor-Name: Amirgholy, Mahyar," Transportation Research Part B: Methodological, Elsevier, vol. 92(PB), pages 234-252.
    8. 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.

    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. 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.
    2. Chen, Hongyu & Liu, Yang & Nie, Yu (Marco), 2015. "Solving the step-tolled bottleneck model with general user heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 210-229.
    3. Takayama, Yuki, 2020. "Who gains and who loses from congestion pricing in a monocentric city with a bottleneck?," Economics of Transportation, Elsevier, vol. 24(C).
    4. Li, Zhi-Chun & Lam, William H.K. & Wong, S.C., 2017. "Step tolling in an activity-based bottleneck model," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 306-334.
    5. Vincent van den Berg, "undated". "Self-financing roads under coarse tolling and heterogeneous preferences," Tinbergen Institute Discussion Papers 22-045/VIII, Tinbergen Institute.
    6. van den Berg, Vincent A.C., 2014. "Coarse tolling with heterogeneous preferences," Transportation Research Part B: Methodological, Elsevier, vol. 64(C), pages 1-23.
    7. 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.
    8. Wu, Wen-Xiang & Huang, Hai-Jun, 2015. "An ordinary differential equation formulation of the bottleneck model with user heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 34-58.
    9. Kenneth Small, 2015. "The Bottleneck Model: An Assessment and Interpretation," Working Papers 141506, University of California-Irvine, Department of Economics.
    10. Takayama, Yuki, 2018. "Time-varying congestion tolling and urban spatial structure," MPRA Paper 89896, University Library of Munich, Germany.
    11. Small, Kenneth A., 2015. "The bottleneck model: An assessment and interpretation," Economics of Transportation, Elsevier, vol. 4(1), pages 110-117.
    12. 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.
    13. Takayama, Yuki & Kuwahara, Masao, 2017. "Bottleneck congestion and residential location of heterogeneous commuters," Journal of Urban Economics, Elsevier, vol. 100(C), pages 65-79.
    14. Akamatsu, Takashi & Wada, Kentaro & Iryo, Takamasa & Hayashi, Shunsuke, 2021. "A new look at departure time choice equilibrium models with heterogeneous users," Transportation Research Part B: Methodological, Elsevier, vol. 148(C), pages 152-182.
    15. Amirgholy, Mahyar & Shahabi, Mehrdad & Gao, H. Oliver, 2017. "Optimal design of sustainable transit systems in congested urban networks: A macroscopic approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 261-285.
    16. Li, Zhi-Chun & Lam, William H.K. & Wong, S.C., 2014. "Bottleneck model revisited: An activity-based perspective," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 262-287.
    17. Liu, Yang & Li, Yuanyuan & Hu, Lu, 2018. "Departure time and route choices in bottleneck equilibrium under risk and ambiguity," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 774-793.
    18. Zhu, Tingting & Li, Yao & Long, Jiancheng, 2022. "Departure time choice equilibrium and tolling strategies for a bottleneck with continuous scheduling preference," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    19. Vincent A.C. van den Berg & Erik T. Verhoef, 2015. "Robot Cars and Dynamic Bottleneck Congestion: The Effects on Capacity, Value of Time and Preference Heterogeneity," Tinbergen Institute Discussion Papers 15-062/VIII, Tinbergen Institute, revised 11 Jul 2016.
    20. Xu, Da & Guo, Xiaolei & Zhang, Guoqing, 2019. "Constrained optimization for bottleneck coarse tolling," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 1-22.

    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:81:y:2015:i:p3:p:775-793. 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.