Quasi-variational inequality formulations and solution approaches for dynamic user equilibria

Abstract

Dynamic User Equilibrium (DUE) is one of the most challenging problems of Dynamic Traffic Assignment (DTA), aiming to predict the optimal dynamic traffic flow pattern in a given transportation network by assuming that each motorist is trying to minimize his/her individual travel cost. Existing methodologies for the DUE study can not capture rigorously the dynamic nature of the problem and produce results with reasonable accuracy. This research is motivated by such a need and in particular, we apply the Quasi-Variational Inequality (QVI) technique to formulate the problem and derive solution algorithms based on certain merit functions. This research uses two major approaches for modeling and solving DUE. Firstly, the path-based DUE model is presented. Three reformulations to this model are developed. One reformulation is a VI model from which we can establish the solution existence condition of the problem. The other two are QVI formulations which can be used to derive the solution algorithm for the path-based mode. It turns out that by temporarily fixing the path flow pattern, the QVI formulation can be reduced to a well-defined Nonlinear Complementarity Problem (NCP). This NCP sub-problem is further studied, including its model and solution properties. To solve the sub-problem, we use the GAMS (General Algebraic Modeling Systems) language and PATH solver which can produce results with high accuracy (e.g., 1.0e-6). The inherent path-numeration requirement prohibits the possibility of applying the path-based model to practical transportation networks. Therefore, we propose the link-node DUE model based on individual destinations. Two QVI formulations, defined on the disaggregated and aggregated link inflows respectively, are developed. Furthermore, the solution existence and uniqueness conditions are discussed. We then design an iterative scheme for solving the models, in which an NCP sub-problem is formulated and solved in each iteration. To facilitate the convergence of the iterative process, we devise an approximate merit function which can be used to monitor the convergence and help to construct the step sizes of the algorithm. Numerical results show such a scheme can generate an optimal or approximate solution with high accuracy.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 10 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.