Stable Dynamic & Beckmann models

The project contains implementations of several primal-dual subgradient methods for searching traffic equilibria in the Stable Dynamics model and the Beckmann model. Results of experiments on the Anaheim transportation network are included.

The following methods are implemented:

1. Universal gradient method [ref]
2. Universal method of similar triangles [arXiv:1701.02473]
3. Method of Weighted Dual Averages [ref]
4. Subgradient method with adaptive step size [arXiv:1604.08183].

Convergence rates of UMST, UGM, composite and non-composite WDA-methods for the Stable Dynamics model:

Convergence rates of UMST, UGM, composite and non-composite WDA-methods, and the Frank–Wolfe method for the Beckmann model:

Installing graph-tool

Native installation of graph-tool on Windows isn't supported. But if you have Docker installed, you can easily download the following container image with all the packages required to run the project: https://hub.docker.com/r/ziggerzz/graph-tool-extra

How to Cite

1. Kubentayeva, M.; Gasnikov, A. Finding Equilibria in the Traffic Assignment Problem with Primal-Dual Gradient Methods for Stable Dynamics Model and Beckmann Model. Mathematics 2021, 9, 1217. https://doi.org/10.3390/math9111217
2. The source code: Kubentayeva M. TransportNet. https://github.com/MeruzaKub/TransportNet. Accessed Month, Day, Year.

More Resources

More information about the models can be found in [Nesterov-de Palma] and [Beckmann].

Stochastic Nash-Wardrop Equilibria in the Beckmann model

Agents’ behavior is not completely rational, what is described by the introduction of Markov logit dynamics: any driver selects a route randomly according to the Gibbs’ distribution taking into account current time costs on the edges of the graph. is a stochasticity parameter (when the model boils down to the ordinary Beckmann model). The figure below shows convergence of flows in stochastic equilibrium to equilibrium flows in non-stochastic case as tends to zero.

How to Cite

1. Article: Gasnikov A.V., Kubentayeva M.B. Searching stochastic equilibria in transport networks by universal primal-dual gradient method // Computer Research and Modeling, 2018, vol. 10, no. 3, pp. 335-345. DOI: 10.20537/2076-7633-2018-10-3-335-345.
2. The source code: Kubentayeva M. TransportNet. https://github.com/MeruzaKub/TransportNet. Accessed Month, Day, Year.