Time dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications

Abstract

An algorithm is introduced that calculates the time-dependent shortest paths from all nodes in a network to a given destination node for every time step over a given time horizon in a network with time-dependent arc costs. Unlike other time-dependent algorithms, this approach can handle networks where the travel cost is not necessarily the travel time itself. The algorithm is based on the general Bellman's principle of optimality. It descretizes the horizon of interest into small time intervals. Starting from the destination node, it calculates the paths operating backwards. A proof of the correctness of the proposed algorithm is presented. The algorithm is efficiently implemented and coded on a CRAY Y/MP-8 supercomputer and tested on a large actual street network as well as several random networks. The motivation for this study was the need to compute time-dependent shortest paths in a real-time environment in connection with intelligent vehicle highway systems. The suitability of the proposed algorithm for such applications is demonstrated.