IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v49y2015i1p13-27.html
   My bibliography  Save this article

On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems

Author

Listed:
  • Hong Zheng

    (Department of Civil Engineering and Engineering Mechanics, University of Arizona, Tucson, Arizona 85721)

  • Yi-Chang Chiu

    (Department of Civil Engineering and Engineering Mechanics, University of Arizona, Tucson, Arizona 85721)

  • Pitu B. Mirchandani

    (School of Computing, Informatics and Decision Systems Engineering, Arizona State University, Tempe, Arizona 85287)

Abstract

This paper investigates the cell-transmission model (CTM)-based single destination system optimum dynamic traffic assignment (SO-DTA) problem, focusing attention on a case where the cell properties are time-invariant. We show the backward propagation of congestion in CTM does not affect the optimal arrival flow pattern of SO-DTA, if the fundamental diagram is of triangular/trapezoidal shape as in the CTM. We mathematically prove that the set of earliest arrival flows (EAFs) not constrained by the traffic wave propagation equations obtained on the node-arc network without cell division is a subset of the SO-DTA. This finding leads to a new approach to the SO-DTA that solves the EAF. Such an EAF can be obtained by merely applying static flow techniques and turning the static flows into dynamic flows over time. Therefore, SO-DTA can theoretically be solved with a run time at the link level depending polynomially on log T . We use numerical examples to verify the results and report the computational benefits of the proposed method by solving SO-DTA on a real-world network.

Suggested Citation

  • Hong Zheng & Yi-Chang Chiu & Pitu B. Mirchandani, 2015. "On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems," Transportation Science, INFORMS, vol. 49(1), pages 13-27, February.
    • Handle: RePEc:inm:ortrsc:v:49:y:2015:i:1:p:13-27
    DOI: 10.1287/trsc.2013.0485
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2013.0485
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2013.0485?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
    ---><---

    References listed on IDEAS

    as
    1. Georgia Perakis & Guillaume Roels, 2006. "An Analytical Model for Traffic Delays and the Dynamic User Equilibrium Problem," Operations Research, INFORMS, vol. 54(6), pages 1151-1171, December.
    2. Edward Minieka, 1973. "Maximal, Lexicographic, and Dynamic Network Flows," Operations Research, INFORMS, vol. 21(2), pages 517-527, April.
    3. Malachy Carey & Y. E. Ge & Mark McCartney, 2003. "A Whole-Link Travel-Time Model with Desirable Properties," Transportation Science, INFORMS, vol. 37(1), pages 83-96, February.
    4. Lo, Hong K. & Szeto, W. Y., 2002. "A cell-based variational inequality formulation of the dynamic user optimal assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 36(5), pages 421-443, June.
    5. 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.
    6. Georgios Kalafatas & Srinivas Peeta, 2009. "A Common Modeling Framework for Dynamic Traffic Assignment and Supply Chain Management Systems with Congestion Phenomena," Springer Books, in: William H. K. Lam & S. C. Wong & Hong K. Lo (ed.), Transportation and Traffic Theory 2009: Golden Jubilee, chapter 0, pages 541-557, Springer.
    7. Bruce Hoppe & Éva Tardos, 2000. "The Quickest Transshipment Problem," Mathematics of Operations Research, INFORMS, vol. 25(1), pages 36-62, February.
    8. So, Stella K. & Daganzo, Carlos F., 2010. "Managing evacuation routes," Transportation Research Part B: Methodological, Elsevier, vol. 44(4), pages 514-520, May.
    9. Zhang, H.M. & Shen, Wei, 2010. "Access control policies without inside queues: Their properties and public policy implications," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1132-1147, September.
    10. 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.
    11. 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.
    12. W. L. Wilkinson, 1971. "An Algorithm for Universal Maximal Dynamic Flows in a Network," Operations Research, INFORMS, vol. 19(7), pages 1602-1612, December.
    13. L. R. Ford & D. R. Fulkerson, 1958. "Constructing Maximal Dynamic Flows from Static Flows," Operations Research, INFORMS, vol. 6(3), pages 419-433, June.
    14. Athanasios K. Ziliaskopoulos, 2000. "A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem," Transportation Science, INFORMS, vol. 34(1), pages 37-49, February.
    15. John J. Jarvis & H. Donald Ratliff, 1982. "Note---Some Equivalent Objectives for Dynamic Network Flow Problems," Management Science, INFORMS, vol. 28(1), pages 106-109, January.
    16. 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.
    17. A. B. Philpott, 1990. "Continuous-Time Flows in Networks," Mathematics of Operations Research, INFORMS, vol. 15(4), pages 640-661, November.
    18. Nimrod Megiddo, 1979. "Combinatorial Optimization with Rational Objective Functions," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 414-424, November.
    19. Hong Zheng & Yi-Chang Chiu, 2011. "A Network Flow Algorithm for the Cell-Based Single-Destination System Optimal Dynamic Traffic Assignment Problem," Transportation Science, INFORMS, vol. 45(1), pages 121-137, February.
    20. Daganzo, Carlos F., 1995. "Properties of link travel time functions under dynamic loads," Transportation Research Part B: Methodological, Elsevier, vol. 29(2), pages 95-98, April.
    21. Nadine Baumann & Martin Skutella, 2009. "Earliest Arrival Flows with Multiple Sources," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 499-512, May.
    22. Lin, Wei-Hua & Lo, Hong K., 2000. "Are the objective and solutions of dynamic user-equilibrium models always consistent?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 34(2), pages 137-144, February.
    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. Wang, Jian & He, Xiaozheng & Peeta, Srinivas & Wang, Wei, 2022. "Globally convergent line search algorithm with Euler-based step size-determination method for continuous network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 119-144.
    2. Long, Jiancheng & Wang, Chao & Szeto, W.Y., 2018. "Dynamic system optimum simultaneous route and departure time choice problems: Intersection-movement-based formulations and comparisons," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 166-206.
    3. Xiaozheng He & Hong Zheng & Srinivas Peeta & Yongfu Li, 2018. "Network Design Model to Integrate Shelter Assignment with Contraflow Operations in Emergency Evacuation Planning," Networks and Spatial Economics, Springer, vol. 18(4), pages 1027-1050, December.
    4. Jiancheng Long & Wai Yuen Szeto, 2019. "Link-Based System Optimum Dynamic Traffic Assignment Problems in General Networks," Operations Research, INFORMS, vol. 67(1), pages 167-182, January.
    5. 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.
    6. Bayram, Vedat & Yaman, Hande, 2024. "A joint demand and supply management approach to large scale urban evacuation planning: Evacuate or shelter-in-place, staging and dynamic resource allocation," European Journal of Operational Research, Elsevier, vol. 313(1), pages 171-191.

    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. Urmila Pyakurel & Tanka Nath Dhamala, 2017. "Continuous Dynamic Contraflow Approach for Evacuation Planning," Annals of Operations Research, Springer, vol. 253(1), pages 573-598, June.
    2. Hong Zheng & Yi-Chang Chiu, 2011. "A Network Flow Algorithm for the Cell-Based Single-Destination System Optimal Dynamic Traffic Assignment Problem," Transportation Science, INFORMS, vol. 45(1), pages 121-137, February.
    3. Georgia Perakis & Guillaume Roels, 2006. "An Analytical Model for Traffic Delays and the Dynamic User Equilibrium Problem," Operations Research, INFORMS, vol. 54(6), pages 1151-1171, December.
    4. Nadine Baumann & Martin Skutella, 2009. "Earliest Arrival Flows with Multiple Sources," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 499-512, May.
    5. Jian Li & Kaan Ozbay, 2015. "Evacuation Planning with Endogenous Transportation Network Degradations: A Stochastic Cell-Based Model and Solution Procedure," Networks and Spatial Economics, Springer, vol. 15(3), pages 677-696, September.
    6. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    7. Xiaozheng He & Srinivas Peeta, 2014. "Dynamic Resource Allocation Problem for Transportation Network Evacuation," Networks and Spatial Economics, Springer, vol. 14(3), pages 505-530, December.
    8. Bish, Douglas R. & Sherali, Hanif D., 2013. "Aggregate-level demand management in evacuation planning," European Journal of Operational Research, Elsevier, vol. 224(1), pages 79-92.
    9. Chi Xie & Jennifer Duthie, 2015. "An Excess-Demand Dynamic Traffic Assignment Approach for Inferring Origin-Destination Trip Matrices," Networks and Spatial Economics, Springer, vol. 15(4), pages 947-979, December.
    10. Ban, Xuegang (Jeff) & Liu, Henry X. & Ferris, Michael C. & Ran, Bin, 2008. "A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations," Transportation Research Part B: Methodological, Elsevier, vol. 42(9), pages 823-842, November.
    11. 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.
    12. Islam, Tarikul & Vu, Hai L. & Hoang, Nam H. & Cricenti, Antonio, 2018. "A linear bus rapid transit with transit signal priority formulation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 163-184.
    13. Kachani, Soulaymane & Perakis, Georgia, 2006. "Fluid dynamics models and their applications in transportation and pricing," European Journal of Operational Research, Elsevier, vol. 170(2), pages 496-517, April.
    14. Jiancheng Long & Wai Yuen Szeto, 2019. "Link-Based System Optimum Dynamic Traffic Assignment Problems in General Networks," Operations Research, INFORMS, vol. 67(1), pages 167-182, January.
    15. Satsukawa, Koki & Wada, Kentaro & Watling, David, 2022. "Dynamic system optimal traffic assignment with atomic users: Convergence and stability," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 188-209.
    16. Hoang, Nam H. & Vu, Hai L. & Panda, Manoj & Lo, Hong K., 2019. "A linear framework for dynamic user equilibrium traffic assignment in a single origin-destination capacitated network," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 329-352.
    17. Bretschneider, S. & Kimms, A., 2012. "Pattern-based evacuation planning for urban areas," European Journal of Operational Research, Elsevier, vol. 216(1), pages 57-69.
    18. Wang, Peirong (Slade) & Li, Pengfei (Taylor) & Chowdhury, Farzana R. & Zhang, Li & Zhou, Xuesong, 2020. "A mixed integer programming formulation and scalable solution algorithms for traffic control coordination across multiple intersections based on vehicle space-time trajectories," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 266-304.
    19. Urmila Pyakurel & Hari Nandan Nath & Stephan Dempe & Tanka Nath Dhamala, 2019. "Efficient Dynamic Flow Algorithms for Evacuation Planning Problems with Partial Lane Reversal," Mathematics, MDPI, vol. 7(10), pages 1-29, October.
    20. Long, Jiancheng & Gao, Ziyou & Szeto, W.Y., 2011. "Discretised link travel time models based on cumulative flows: Formulations and properties," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 232-254, January.

    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:inm:ortrsc:v:49:y:2015:i:1:p:13-27. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.