Dynamic Shortest-Path Algorithm for Continuous Arc Travel Times

To achieve the desired computational speed, existing algorithms for time-dependent (or dynamic) shortest-path problems call for the unrealistic aggregation of travel time as multiples of a given time increment. While the time increment can be varied between, say, peak and off-peak periods, it still has its obvious limitation on granularity. An improved solution algorithm is proposed for the all-to-one or one-to-all time-dependent versions of the problem. The algorithms are solidly founded on Bellman's principle of optimality and apply to continuous or real-value arc travel times (rather than the current practice of discrete-time specifications). The new algorithms are practical in computational speed, and they capture a more realistic metric for route choice. In this case, a relatively coarse time increment can be used throughout the analysis, yet it is compatible with any continuous or real-value arc travel times. To support these claims, computational results that consider various network sizes, densities, and numbers of time increments are provided. For future extensions, a non-first-in-first-out fastest-path and minimum-cost-path algorithm is proposed. A generalized cost (or disutility arc function) is defined to combine the two, on the basis of which route choices are made. For route-choice decisions, it is stipulated that adoption of such a disutility specification mandates a continuous valuation of arc time and cost. Instead of an all-to-one implementation, a one-to-all implementation is suggested under these circumstances. The latter approach, when complemented by the speed of algorithmic execution, facilitates real-world applications. It allows the driver to value incident delay and risks in route choice on a real-time basis.