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

Meruza Kubentayeva and Alexander Gasnikov
Additional contact information
Meruza Kubentayeva: Institute for Information Transmission Problems, RAS, Bolshoy Karetny Per. 19, Build.1, 127051 Moscow, Russia
Alexander Gasnikov: Institute for Information Transmission Problems, RAS, Bolshoy Karetny Per. 19, Build.1, 127051 Moscow, Russia

Mathematics, 2021, vol. 9, issue 11, 1-17

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.

Keywords: stable dynamics model; Beckmann model; traffic equilibrium; universal gradient method; universal method of similar triangles; method of weighted dual averages; duality gap (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/11/1217/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/11/1217/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:11:p:1217-:d:563377

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().