Efficient modeling of travel in networks with time-varying link speeds

This paper investigates exact and approximate methods for estimating time-minimizing vehicular movements in road network models where link speeds vary over time. The assumptions made about network conditions recognize the intrinsic relationship between speed and travel duration and are substantiated by elementary methods to obtain link travel duration. The assumptions also imply a condition of first-in-first-out consistency, which (as shown by work of Kaufman and Smith) justifies the use of Dijkstra's algorithm for path-finding purposes. The paper describes several adaptations of the Dijkstra algorithm, including new variants that are addressed specifically to the dynamic conditions mentioned above. Computational tests indicate that these procedures will be useful for scheduling, modeling and other purposes, when applied to networks of substantial size.