A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem

Yu Marco Nie*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

46 Scopus citations


A cell-based variant of the Merchant-Nemhauser (M-N) model is proposed for the system optimum (SO) dynamic traffic assignment (DTA) problem. Once linearized and augmented with additional constraints to capture cross-cell interactions, the model becomes a linear program that embeds a relaxed cell transmission model (CTM) to propagate traffic. As a result, we show that CTM-type traffic dynamics can be derived from the original M-N model, when the exit-flow function is properly selected and discretized. The proposed cell-based M-N model has a simple constraint structure and cell network representation because all intersections and cells are treated uniformly. Path marginal costs are defined using a recursive formula that involves a subset of multipliers from the linear program. This definition is then employed to interpret the necessary condition, which is a dynamic extension of the Wardrop's second principle. An algorithm is presented to solve the flow holding back problem that is known to exist in many discrete SO-DTA models. A numerical experiment is conducted to verify the proposed model and algorithm.

Original languageEnglish (US)
Pages (from-to)329-342
Number of pages14
JournalTransportation Research Part B: Methodological
Issue number2
StatePublished - Feb 2011


  • Cell transmission model
  • Flow holding back
  • Marginal cost analysis
  • System optimum dynamic traffic assignment
  • The Merchant-Nemhauser (M-N) model

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem'. Together they form a unique fingerprint.

Cite this