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

TLDR

The optimal route depends on arrival time, which is unknown at departure, so the final choice can be deferred until later nodes are reached. The paper aims to find the least expected travel time path in networks with random, time‑dependent travel times and to develop a method that identifies the optimal adaptive decision rule. The authors propose a method that computes the optimal adaptive decision rule for selecting routes based on arrival times, overcoming the limitations of standard shortest‑path algorithms. The proposed method successfully finds the minimum expected travel time path and demonstrates that the optimal route is an adaptive decision rule rather than a simple path.

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.