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

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.