Premium
Toward faster algorithms for dynamic traffic assignment. I. Parametric quickest‐path trees
Author(s) -
Dial Robert B.
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10056
Subject(s) - tree traversal , computer science , algorithm , path (computing) , fast path , node (physics) , tree (set theory) , scheduling (production processes) , mathematical optimization , shortest path problem , mathematics , theoretical computer science , graph , combinatorics , structural engineering , engineering , programming language
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 → 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. © 2002 Wiley Periodicals, Inc.