Finding Equilibria in the Traffic Assignment Problem with Primal-Dual Gradient Methods for Stable Dynamics Model and Beckmann Model

Abstract

In this paper, we consider the application of several gradient methods to the traffic assignment problem: we search equilibria in the stable dynamics model (Nesterov and De Palma, 2003) and the Beckmann model. Unlike the celebrated Frank–Wolfe algorithm widely used for the Beckmann model, these gradients methods solve the dual problem and then reconstruct a solution to the primal one. We deal with the universal gradient method, the universal method of similar triangles, and the method of weighted dual averages and estimate their complexity for the problem. Due to the primal-dual nature of these methods, we use a duality gap in a stopping criterion. In particular, we present a novel way to reconstruct admissible flows in the stable dynamics model, which provides us with a computable duality gap.

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 — 6 citations exist upstream.

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