An algorithm operating on a new and compact representation of link exit times to solve the one-to-all fastest path problem in dynamic networks is presented. The new space-efficient representation that exploits the first-in, first-out property of link travel times in dynamic networks is developed. The algorithm is described, and its working on a simple network is presented. The algorithm directly operates on bit streams of data representing time-dependent link travel times and performs logical operations on 0 and 1 bits only. Computational results are presented for large dynamic networks. The ideas behind the development of this algorithm are extendable to the development of algorithms operating at the bit level to solve other variants of dynamic shortest path problems and other dynamic network flow problems. These developments then open new research possibilities in the development of solution algorithms for dynamic network problems.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Bitwise Algorithm for Fastest Paths in Time-Dependent Networks


    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



    Bitwise Algorithm for Fastest Paths in Time-Dependent Networks

    Chabini, I. / Yadappanavar, V. / National Research Council | British Library Conference Proceedings | 2001




    FASTEST PATHS IN TIME-DEPENDENT NETWORKS FOR INTELLIGENT VEHICLE-HIGHWAY SYSTEMS APPLICATION

    Kaufman, David E. / Smith, Robert L. | Taylor & Francis Verlag | 1993