The Fastest Path through a Network with Random Time-Dependent Travel Times

Randolph W. Hall
Additional contact information
Randolph W. Hall: University of California, Berkeley, California

Transportation Science, 1986, vol. 20, issue 3, 182-188

Abstract: This paper introduces the problem of finding the least expected travel time path between two nodes in a network with travel times that are both random and time-dependent (e.g., a truck, rail, air or bus network). It first shows that standard shortest path algorithms (such as the Dijkstra algorithm) do not find the minimum expected travel time path on such a network, then proposes a method which does find the minimum path. Next, this paper shows that the optimal “route choice” is not a simple path but an adaptive decision rule. The best route from any given node to the final destination depends on the arrival time at that node. Because the arrival time is not known before departing the origin, a better route can be selected by deferring the final choice until later nodes are reached. A method for finding the optimal adaptive decision rule is proposed.

Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (68)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.20.3.182 (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:inm:ortrsc:v:20:y:1986:i:3:p:182-188

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().