A massively parallel time-dependent least-time-path algorithm for intelligent transportation systems applications

This article is concerned with the problem of computing in parallel time-dependent least-time paths that can be used in real-time intelligent transportation systems applications. A message-passing scheme is presented, and its correctness is proved. The algorithm's computational complexity is shown to be O(\T \ (2)\V \ (2)), an improvement by \V \ over the best-known sequential algorithm. The algorithm is implemented, coded, and computationally tested on actual and random networks with promising results. The algorithm is implemented on a CRAY-T3D supercomputer using a Parallel Virtual Machine environment that allows portability to lower-end multiprocessor machines.