TY - JOUR

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

AU - Lu, Chung-Cheng

AU - Mahmassani, Hani S.

AU - Zhou, Xuesong

PY - 2009/1/1

Y1 - 2009/1/1

N2 - 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.

AB - 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.

KW - Column generation algorithm

KW - Dynamic traffic assignment

KW - Dynamic user equilibrium

KW - Gap function

KW - Traffic simulation

UR - http://www.scopus.com/inward/record.url?scp=58249110601&partnerID=8YFLogxK

U2 - 10.1016/j.trb.2008.07.005

DO - 10.1016/j.trb.2008.07.005

M3 - Article

AN - SCOPUS:58249110601

SN - 0191-2615

VL - 43

SP - 345

EP - 364

JO - Transportation Research Part B: Methodological

JF - Transportation Research Part B: Methodological

IS - 3

ER -