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

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.