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

A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem

Author

Listed:
  • Nie, Yu (Marco)

Abstract

A cell-based variant of the Merchant-Nemhauser (M-N) model is proposed for the system optimum (SO) dynamic traffic assignment (DTA) problem. Once linearized and augmented with additional constraints to capture cross-cell interactions, the model becomes a linear program that embeds a relaxed cell transmission model (CTM) to propagate traffic. As a result, we show that CTM-type traffic dynamics can be derived from the original M-N model, when the exit-flow function is properly selected and discretized. The proposed cell-based M-N model has a simple constraint structure and cell network representation because all intersections and cells are treated uniformly. Path marginal costs are defined using a recursive formula that involves a subset of multipliers from the linear program. This definition is then employed to interpret the necessary condition, which is a dynamic extension of the Wardrop's second principle. An algorithm is presented to solve the flow holding back problem that is known to exist in many discrete SO-DTA models. A numerical experiment is conducted to verify the proposed model and algorithm.

Suggested Citation

  • Nie, Yu (Marco), 2011. "A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 329-342, February.
  • Handle: RePEc:eee:transb:v:45:y:2011:i:2:p:329-342
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(10)00096-2
    Download Restriction: Full text for ScienceDirect subscribers only

    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. Shen, Wei & Zhang, H. Michael, 2009. "On the Morning Commute Problem in a Corridor Network with Multiple Bottlenecks: Its System-optimal Traffic Flow Patterns and the Realizing Tolling Scheme," Institute of Transportation Studies, Working Paper Series qt9bs815sq, Institute of Transportation Studies, UC Davis.
    2. 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.
    3. Daganzo, Carlos F., 1995. "The cell transmission model, part II: Network traffic," Transportation Research Part B: Methodological, Elsevier, vol. 29(2), pages 79-93, April.
    4. Carey, Malachy & Subrahmanian, Eswaran, 2000. "An approach to modelling time-varying flows on congested networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(3), pages 157-183, April.
    5. Chiu, Yi-Chang & Zheng, Hong, 2007. "Real-time mobilization decisions for multi-priority emergency response resources and evacuation groups: Model formulation and solution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 43(6), pages 710-736, November.
    6. Muñoz, Juan Carlos & Laval, Jorge A., 2006. "System optimum dynamic traffic assignment graphical solution method for a congested freeway and one destination," Transportation Research Part B: Methodological, Elsevier, vol. 40(1), pages 1-15, January.
    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. Nie, Xiaojian & Zhang, H.M., 2005. "Delay-function-based link models: their properties and computational issues," Transportation Research Part B: Methodological, Elsevier, vol. 39(8), pages 729-751, September.
    9. Smith, M. J., 1993. "A new dynamic traffic model and the existence and calculation of dynamic user equilibria on congested capacity-constrained road networks," Transportation Research Part B: Methodological, Elsevier, vol. 27(1), pages 49-63, February.
    10. Carey, Malachy, 1992. "Nonconvexity of the dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 26(2), pages 127-133, April.
    11. Daganzo, Carlos F., 1994. "The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory," Transportation Research Part B: Methodological, Elsevier, vol. 28(4), pages 269-287, August.
    12. Ghali, M. O. & Smith, M. J., 1995. "A model for the dynamic system optimum traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 29(3), pages 155-170, June.
    13. Shen, Wei & Zhang, H.M., 2009. "On the morning commute problem in a corridor network with multiple bottlenecks: Its system-optimal traffic flow patterns and the realizing tolling scheme," Transportation Research Part B: Methodological, Elsevier, vol. 43(3), pages 267-284, March.
    14. May, A. D. & Milne, D. S., 2000. "Effects of alternative road pricing systems on network performance," Transportation Research Part A: Policy and Practice, Elsevier, vol. 34(6), pages 407-436, August.
    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. 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.
    2. Douglas Bish & Edward Chamberlayne & Hesham Rakha, 2013. "Optimizing Network Flows with Congestion-Based Flow Reductions," Networks and Spatial Economics, Springer, vol. 13(3), pages 283-306, September.
    3. Ukkusuri, Satish V. & Han, Lanshan & Doan, Kien, 2012. "Dynamic user equilibrium with a path based cell transmission model for general traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1657-1684.
    4. Byung Chung & Tao Yao & Bo Zhang, 2012. "Dynamic Traffic Assignment under Uncertainty: A Distributional Robust Chance-Constrained Approach," Networks and Spatial Economics, Springer, vol. 12(1), pages 167-181, March.
    5. repec:eee:transb:v:104:y:2017:i:c:p:272-289 is not listed on IDEAS
    6. Doan, Kien & Ukkusuri, Satish V., 2012. "On the holding-back problem in the cell transmission based dynamic traffic assignment models," Transportation Research Part B: Methodological, Elsevier, vol. 46(9), pages 1218-1238.
    7. Zhong, R.X. & Sumalee, A. & Friesz, T.L. & Lam, William H.K., 2011. "Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 1035-1061, August.
    8. van der Gun, Jeroen P.T. & Pel, Adam J. & van Arem, Bart, 2017. "Extending the Link Transmission Model with non-triangular fundamental diagrams and capacity drops," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 154-178.
    9. Wada, Kentaro & Akamatsu, Takashi, 2013. "A hybrid implementation mechanism of tradable network permits system which obviates path enumeration: An auction mechanism with day-to-day capacity control," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 94-112.
    10. Zhengfeng Huang & Pengjun Zheng & Gang Ren & Yang Cheng & Bin Ran, 2016. "Simultaneous optimization of evacuation route and departure time based on link-congestion mitigation," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 83(1), pages 575-599, August.
    11. Parry, Katharina & Hazelton, Martin L., 2013. "Bayesian inference for day-to-day dynamic traffic models," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 104-115.
    12. repec:eee:transb:v:100:y:2017:i:c:p:222-254 is not listed on IDEAS
    13. Hussein Tarhini & Douglas R. Bish, 2016. "Routing Strategies Under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 16(2), pages 665-685, June.
    14. Ma, Rui & Ban, Xuegang (Jeff) & Pang, Jong-Shi, 2014. "Continuous-time dynamic system optimum for single-destination traffic networks with queue spillbacks," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 98-122.
    15. Long, Jiancheng & Szeto, W.Y. & Huang, Hai-Jun & Gao, Ziyou, 2015. "An intersection-movement-based stochastic dynamic user optimal route choice model for assessing network performance," Transportation Research Part B: Methodological, Elsevier, vol. 74(C), pages 182-217.

    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:45:y:2011:i:2:p:329-342. See general information about how to correct material in RePEc.

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

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.