A Massively Parallel Time‐Dependent Least‐Time‐Path Algorithm for Intelligent Transportation Systems Applications
Athanasios K. Ziliaskopoulos, Dimitrios Kotzinos · Computer-Aided Civil and Infrastructure Engineering · 2001
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.