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:
- Universal gradient method [ref]
- Universal method of similar triangles [arXiv:1701.02473]
- Method of Weighted Dual Averages [ref]
- 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:
T-SWSF
for stable dynamic problem
Usage of One can substitute the Dijkstra
algorithm when performing flow reconstruction phase (see Alogorithm 1
of the original article) with the T-SWSF
algorithm [ref] aimed at solving the Dynamic Single-Source Shortest-Path problem. The general idea behind this problem is to utilize the knowledge of shortest paths and shortest distances computed on the previous step for computing the shortest paths and shortest distances on the current step (after graph edge's weights perturbation due to gradient step of a stable dynamic problem solver).
T-SWSF
analysis
Our experimental study shows, that for arbitrary graph perturbations the T-SWSF
performs worse than Dijkstra
(for fair comparison we implement both methods in python, our implementations are in the following file). However, if the ratio of the number of perturbed edges to the number of all edges is sufficiently small, the T-SWSF
works faster than recomputation of shortest paths and distances from scratch using Dijkstra
algorithm. We use the ratio
constant equals to
T-SWSF
application
Our experiment study shows that in the stable dynamic model when using Universal Method of Similar Triangles
(ustm
) and Universal gradient method
(ugm
) solvers (see sections T-SWSF
in such cases seems profitable.
In order to validate the profitability of the T-SWSF
when solving stable dynamic model using ustm
and ugm
we compare the time needed to achieve fixed duality gaps Kubentayeva et. al.
). Our experiments are available in the notebook. The final chart is the following:
The _dijkstra
suffix means, that we solve the SSSP problems by recomputing all paths from scratch using Dijkstra
algorithm, the _t_swsf
suffix means, that we apply T-SWSF
for arbitrary graph perturbations (even for $r > r^$). The _tradeoff
means, that we use Dijkstra
if $r > r^$ and T-SWSF
if T-SWSF
could improve the time complexity in the considered cases.
Further directions
The T-SWSF
is not the only choice for solving Dynamic Single-Source Shortest-Path problem (and not the most efficient one, especially given our implementation). The potential algorithms which could solve the problem (probably, more efficient) are as follows:
(It is not the full list, just what we have found)
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
- 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
- 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
- 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.
- The source code: Kubentayeva M. TransportNet. https://github.com/MeruzaKub/TransportNet. Accessed Month, Day, Year.