The problem of computing shortest paths in time-dependent networks is considered. This computational problem is at the heart of solution methods to a variety of dynamic network models that arise in the context of intelligent transportation systems applications. The design, implementation, and computational testing are reported for parallel algorithms that exploit possibilities offered by low-cost, commonly available, parallel, and distributed computing platforms to solve many-to-many shortest path problems in time-dependent networks. Five shared-memory implementations and five message-passing implementations are developed. The parallel implementations adopt three decomposition strategies based on the sets of destination nodes, origin nodes, and departure times at origin nodes. The algorithms are coded with two types of parallel computing environments: a message-passing environment based on the parallel virtual machine library and a multithreading environment based on the Sun Microsystems Multi-Threads library. Numerical results are obtained with large-sized dynamic networks and two types of parallel computing platforms: a distributed network of Unix workstations and a Sun shared-memory machine containing eight processors. Satisfactory speedups of sequential algorithms are achieved. Numerical results obtained indicate that, overall, shared-memory platforms appear to be the most appropriate type of parallel computing platforms to solve dynamic shortest path problems that arise in the context of intelligent transportation systems applications.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Design and Implementation of Parallel Dynamic Shortest Path Algorithms for Intelligent Transportation Systems Applications


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:


    Publication date :

    2001-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Design and Implementation of Parallel Dynamic Shortest Path Algorithms for Intelligent Transportation Systems Applications

    Chabini, I. / Ganugapati, S. / National Research Council | British Library Conference Proceedings | 2001




    Shortest Path Optimization Algorithm in Intelligent Transportation System

    Wang, Hao Yu ;Zheng, Yi ;Ji, Xiao Juan | Trans Tech Publications | 2013


    Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time

    Chabini, I. / National Research Council; Transportation Research Board | British Library Conference Proceedings | 1998