Design and implementation of parallel time-dependent least time path algorithms for intelligent transportation systems applications

The development of Intelligent Transportation Systems (ITS) and the resulting need for real-time traffic management and route guidance models require fast shortest-path algorithms that can account for the dynamics of traffic networks. The objective of this paper is to introduce parallel designs for time-dependent shortest-path algorithms that can be used in real-time ITS applications. In this paper, two shared-memory and one message-passing algorithms are designed, implemented, coded and computationally tested on actual and random networks. The reported tests are performed on CRAY supercomputers, but the algorithms can be readily ported to lower-end multiprocessor machines.