IDEAS home Printed from https://ideas.repec.org/p/cdl/uctcwp/qt4jm4j2d9.html
   My bibliography  Save this paper

Reversibility of the Time-Dependent Shortest Path Problem

Author

Listed:
  • Daganzo, Carlos F.

Abstract

Time-dependent shortest path problems arise in a variety of applications; e.g., dynamic traffic assignment (DTA), network control, automobile driver guidance, ship routing and airplane dispatching. In the majority of cases one seeks the cheapest (least generalized cost) or quickest (least time) route between an origin and a destination for a given time of departure. This is the “forward” shortest path problem. In some applications, however, e.g., when dispatching airplanes from airports and in DTA versions of the “morning commute problem”, one seeks the cheapest or quickest routes for a given arrival time. This is the “backward” shortest path problem. It is shown that an algorithm that solves the forward quickest path problem on a network with first-in-first-out (FIFO) links also solves the backward quickest path problem on the same network. More generally, any algorithm that solves forward (or backward) problems of a particular type is shown also to solve backward (forward) problems of a conjugate type.

Suggested Citation

  • Daganzo, Carlos F., 2001. "Reversibility of the Time-Dependent Shortest Path Problem," University of California Transportation Center, Working Papers qt4jm4j2d9, University of California Transportation Center.
    • Handle: RePEc:cdl:uctcwp:qt4jm4j2d9
    as

    Download full text from publisher

    File URL: https://www.escholarship.org/uc/item/4jm4j2d9.pdf;origin=repeccitec
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Daganzo, Carlos, 1994. "The Cell Transmission Model: Network Traffic," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt9pz309w7, Institute of Transportation Studies, UC Berkeley.
    Full references (including those not matched with items on IDEAS)

    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. Menendez, Monica & Daganzo, Carlos F., 2007. "Effects of HOV lanes on freeway bottlenecks," Transportation Research Part B: Methodological, Elsevier, vol. 41(8), pages 809-822, October.
    2. Daganzo, Carlos F., 2002. "A behavioral theory of multi-lane traffic flow. Part II: Merges and the onset of congestion," Transportation Research Part B: Methodological, Elsevier, vol. 36(2), pages 159-169, February.
    3. Daganzo, Carlos F., 1999. "A Behavioral Theory of Multi-Lane Traffic Flow Part II: Merges and the Onset of Congestion," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt3qj018c9, Institute of Transportation Studies, UC Berkeley.
    4. Cayford, Randall & Lin, Wei-Hua & Daganzo, Carlos F., 1997. "The Netcell Simulation Package: Technical Description," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt4j27j106, Institute of Transportation Studies, UC Berkeley.
    5. Zheng, Liang & Jin, Peter J. & Huang, Helai, 2015. "An anisotropic continuum model considering bi-directional information impact," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 36-57.
    6. Daganzo, Carlos F., 1995. "Requiem for second-order fluid approximations of traffic flow," Transportation Research Part B: Methodological, Elsevier, vol. 29(4), pages 277-286, August.
    7. Nicholas B. Taylor & Benjamin G. Heydecker, 2015. "Estimating probability distributions of dynamic queues," Transportation Planning and Technology, Taylor & Francis Journals, vol. 38(1), pages 3-27, February.
    8. Li, Anna C.Y. & Nozick, Linda & Xu, Ningxiong & Davidson, Rachel, 2012. "Shelter location and transportation planning under hurricane conditions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(4), pages 715-729.
    9. Ngoduy, D., 2021. "Noise-induced instability of a class of stochastic higher order continuum traffic models," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 260-278.
    10. Daganzo, Carlos F., 2002. "Reversibility of the time-dependent shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 36(7), pages 665-668, August.

    More about this item

    Keywords

    Social and Behavioral Sciences;

    Statistics

    Access and download statistics

    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:cdl:uctcwp:qt4jm4j2d9. 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: Lisa Schiff (email available below). General contact details of provider: https://edirc.repec.org/data/itucbus.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.