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 timeinvariant. 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 logT. 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.