On the system optimum dynamic traffic assignment and earliest arrival flow problems

Hong Zheng, Yi Chang Chiu, Pitu Mirchandani

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)13-27
Number of pages15
JournalTransportation Science
Issue number1
StatePublished - Feb 1 2015


  • Cell-transmission model
  • Dynamic traffic assignment
  • Earliest arrival flows
  • Flows over time
  • System optimum

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'On the system optimum dynamic traffic assignment and earliest arrival flow problems'. Together they form a unique fingerprint.

Cite this