On the Convergence of the Method of Successive Averages for Calculating Equilibrium in Traffic Networks

Mounce, Richard; Carey, Malachy · 2014 · OpenAlex-citations

DOI: 10.1287/trsc.2014.0517

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper investigates the convergence properties of the Method of Successive Averages (MSA), a widely used algorithm for calculating user equilibrium in traffic networks. The authors address the theoretical conditions required for discrete dynamical systems, derived from continuous descent directions, to converge to equilibrium. While previous work required objective functions to be twice continuously differentiable, this study establishes convergence under weaker conditions: the objective function need only be continuously differentiable, and the rate of descent must be bounded below by a multiple of the cube of the descent vector’s norm. The study formulates traffic assignment as a minimization problem where equilibrium corresponds to a zero of the objective function. The authors analyze two discrete update schemes: one with a fixed step length and another with a decreasing step length sequence (MSA). Theoretically, they prove that a fixed step length system approaches within a certain distance of equilibrium, with the error decreasing as the step size shrinks. Conversely, they demonstrate that if the step lengths tend to zero and their sum diverges, the system converges exactly to equilibrium. These results apply to steady-state models provided the route cost vector is a continuously differentiable and monotone function of the route flow vector. However, the authors show that these necessary conditions fail in dynamic vertical queueing models due to discontinuities in the cost derivative when inflow equals capacity. Numerical experiments were conducted on three networks: a simple 6-node network, the Sioux Falls network, and the large Austin network. The authors compared MSA against fixed-step algorithms using two descent vectors: pairwise swapping and swapping to the least costly route. Results indicated that MSA combined with pairwise swapping performed poorly and was computationally expensive, particularly on larger networks. In contrast, MSA combined with swapping to the least costly route demonstrated efficient convergence on the Sioux Falls and Austin networks. Fixed-step algorithms with pairwise swapping were faster on the small network but less effective on larger ones compared to MSA with least-cost swapping. The significance of this work lies in relaxing the differentiability requirements for proving MSA convergence, thereby broadening its theoretical justification for steady-state traffic assignment. The findings clarify that while MSA is theoretically sound for steady-state models with smooth, monotone cost functions, its applicability to dynamic models is limited by the lack of continuous differentiability in cost derivatives. Practically, the study suggests that MSA is most effective when paired with a descent direction that swaps flow to the least costly routes, rather than pairwise swapping, especially for large-scale networks.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• traffic density