Toward Faster Algorithms for Dynamic Traffic Assignment. I. Parametric Quickest-Path Trees

摘要

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: (ⅰ) the traversal time of an arc i → j is a piecewise linear function of the arrival time at its i-node; (ⅱ) the traversal time of a path is the sum of its arcs' traversal times; and (ⅲ) 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.