An efficient algorithm for dynamic traffic equilibrium assignment with queues

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


This paper presents an efficient algorithm for solving the dynamic user equilibrium (DUE) traffic assignment with a one-to-many origin-destination (OD) pattern. To achieve the efficiency of the algorithm, we employ the following three strategies. First, we exploit the decomposition property of the DUE assignment with respect to the departure time from an origin; we consider the algorithm that solves each of the decomposed DUE assignments sequentially. Second, we represent the decomposed DUE assignment by an arc-node formulation, not by using path variables. Third, we take advantage of the fact that the decomposed DUE assignment reduces to (finite dimensional) nonlinear complementarity problems (NCPs); we develop the algorithm based on the globally convergent Newton's method for general NCPs. These strategies, together with graph theoretic devices, enable us to design a new algorithm which does not require path enumeration and is capable of dealing with very large-scale networks. Numerical experiments disclose that the proposed algorithm solves the DUE assignment very rapidly, even in large-scale networks with some thousands of links and nodes where conventional heuristic algorithms do not converge to the accurate equilibrium solution.

Original languageEnglish
Pages (from-to)389-404
Number of pages16
JournalTransportation Science
Issue number4
Publication statusPublished - 2001 Nov


Dive into the research topics of 'An efficient algorithm for dynamic traffic equilibrium assignment with queues'. Together they form a unique fingerprint.

Cite this