Quickest Paths in a Dynamic Network: A Faster Algorithm

This paper presents a quickest path tree algorithm designed for real-time use with urban road networks. Using piecewise linear functions to model arc times as a function of time-of-day, the algorithm finds a quickest path and its associated earliest arrival time from the origin node to every other node in the network, and for every desired departure time from the origin. Using sensitivity analysis, it transforms the min path tree for one departure-time interval into another for the next adjacent interval, whose width the algorithm determines on the fly. By building trees for only relatively few departure times, it determines quickest paths for every departure time. Preliminary tests show the algorithm running upwards of ten times faster than the conventional approach.