Being first in a three-part series promising a practical solution to the user-equilibrium dynamic traffic assignment problem, this paper devises a parametric quickest-path tree algorithm, whose model makes three practical assumptions: (i) the traversal time of an arc i to j is a piecewise linear function of the arrival time at its i-node; (ii) the traversal time of a path is the sum of its arcs' traversal times; and (iii) the FIFO constraint holds, that is, later departure implies later arrival. The algorithm finds a quickest path, and its associated earliest arrival time, to every node for every desired departure time from the origin. Its parametric approach transforms a min-path tree for one departure-time interval into another for the next adjacent interval, whose shared boundary the algorithm determines on the fly. By building relatively few trees, it provides the topology explicitly and the arrival times implicitly of all min-path trees. Tests show the algorithm running upward of 10 times faster than the conventional brute-force approach, which explicitly builds a min-path tree for every departure time. Besides dynamic traffic assignment, other applications for which these findings have utility include traffic control planning, vehicle routing and scheduling, real-time highway route guidance, etc.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Toward faster algorithms for dynamic traffic assignment. I. Parametric quickest-path trees


    Contributors:
    Dial, R.B. (author)

    Published in:

    Networks ; 41 , 1 ; 36-43


    Publication date :

    2003


    Size :

    8 Seiten, 6 Quellen




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English




    Faster Path-Based Algorithm for Traffic Assignment

    Jayakrishnan, R. | Online Contents | 1994


    Quickest Paths in a Dynamic Network: A Faster Algorithm

    Dial, R. B. / American Society of Civil Engineers | British Library Conference Proceedings | 2002


    Dynamic Traffic Assignment: Genetic Algorithms Approach

    Sadek, A. W. / Smith, B. L. / Demetsky, M. J. et al. | British Library Conference Proceedings | 1997


    Dynamic Traffic Assignment: Genetic Algorithms Approach

    Sadek, Adel W. / Smith, Brian L. / Demetsky, Michael J. | Transportation Research Record | 1997


    Dynamic Traffic Assignment: Genetic Algorithms Approach

    Sadek, Adel W. | Online Contents | 1997