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

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.