A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations

In this paper, we propose a link-node complementarity model for the basic deterministic dynamic user equilibrium (DUE) problem with single-user-class and fixed demands. The model complements link-path formulations that have been widely studied for dynamic user equilibria. Under various dynamic network constraints, especially the exact flow propagation constraints, we show that the continuous-time dynamic user equilibrium problem can be formulated as an infinite dimensional mixed complementarity model. The continuous-time model can be further discretized as a finite dimensional non-linear complementarity problem (NCP). The proposed discrete-time model captures the exact flow propagation constraints that were usually approximated in previous studies. By associating link inflow at the beginning of a time interval to travel times at the end of the interval, the resulting discrete-time model is predictive rather than reactive. The solution existence and compactness condition for the proposed model is established under mild assumptions. The model is solved by an iterative algorithm with a relaxed NCP solved at each iteration. Numerical examples are provided to illustrate the proposed model and solution approach. We particularly show why predictive DUE is preferable to reactive DUE from an algorithmic perspective.