Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem

Chung Cheng Lu, Hani S Mahmassani*, Xuesong Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

A variety of analytical and simulation-based models and algorithms have been developed for the dynamic user equilibrium (DUE) traffic assignment problem. This paper aims to develop a theoretically sound simulation-based DUE model and its solution algorithm, with particular emphasis on obtaining solutions that satisfy the DUE conditions. The DUE problem is reformulated, via a gap function, as a nonlinear minimization problem (NMP). The NMP is then solved by a column generation-based optimization procedure which embeds (i) a simulation-based dynamic network loading model to capture traffic dynamics and determine experienced path travel costs for a given path flow pattern and (ii) a path-swapping descent direction method to solve the restricted NMP defined by a subset of feasible paths. The descent direction method circumvents the need to compute the gradient of the objective function in finding search directions, or to determine suitable step sizes, which is especially valuable for large-scale simulation-based DUE applications. Computational results for both small and large real road networks confirm that the proposed formulation and solution algorithm are effective in obtaining near-optimal solutions to the DUE problem.

Original languageEnglish (US)
Pages (from-to)345-364
Number of pages20
JournalTransportation Research Part B: Methodological
Volume43
Issue number3
DOIs
StatePublished - Jan 1 2009

Keywords

  • Column generation algorithm
  • Dynamic traffic assignment
  • Dynamic user equilibrium
  • Gap function
  • Traffic simulation

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint Dive into the research topics of 'Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem'. Together they form a unique fingerprint.

Cite this