Reversibility of the Time-Dependent Shortest Path Problem

Carlos F. Daganzo

University of California Transportation Center, Working Papers from University of California Transportation Center

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.

Keywords: Social; and; Behavioral; Sciences (search for similar items in EconPapers)
Date: 2001-03-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.escholarship.org/uc/item/4jm4j2d9.pdf;origin=repeccitec (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cdl:uctcwp:qt4jm4j2d9

Access Statistics for this paper

More papers in University of California Transportation Center, Working Papers from University of California Transportation Center Contact information at EDIRC.
Bibliographic data for series maintained by Lisa Schiff ().