On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems

This paper investigates the cell-transmission model (CTM)-based single destination system optimum dynamic traffic assignment (SO-DTA) problem, focusing attention on a case where the cell properties are time-invariant. We show the backward propagation of congestion in CTM does not affect the optimal arrival flow pattern of SO-DTA, if the fundamental diagram is of triangular/trapezoidal shape as in the CTM. We mathematically prove that the set of earliest arrival flows (EAFs) not constrained by the traffic wave propagation equations obtained on the node-arc network without cell division is a subset of the SO-DTA. This finding leads to a new approach to the SO-DTA that solves the EAF. Such an EAF can be obtained by merely applying static flow techniques and turning the static flows into dynamic flows over time. Therefore, SO-DTA can theoretically be solved with a run time at the link level depending polynomially on log T. We use numerical examples to verify the results and report the computational benefits of the proposed method by solving SO-DTA on a real-world network.