The Method of Successive Averages

The Method of Successive Averages (MSA) is an iterative algorithm for solving the user-equilibrium traffic assignment problem. Like Frank-Wolfe, MSA performs an all-or-nothing (AON) assignment at each iteration. Unlike Frank-Wolfe, MSA uses a predetermined step size rather than a line search.

At iteration $k,$ let $\mathbf{x}^{(k)}$ denote the current vector of link flows and let $\mathbf{y}^{(k)}$ denote the AON assignment computed at the current link costs $c_a(x_a^{(k)}).$ The MSA update rule is

$$\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \dfrac{1}{k}\left(\mathbf{y}^{(k)} - \mathbf{x}^{(k)}\right).$$

Equivalently,

$$\mathbf{x}^{(k+1)} = \left(1 - \dfrac{1}{k}\right)\mathbf{x}^{(k)} + \dfrac{1}{k}\,\mathbf{y}^{(k)}.$$

Because the step size $\alpha_k = 1/k$ does not depend on any property of the objective function, MSA can be applied even when the objective is hard or impossible to evaluate (e.g., stochastic user equilibrium, simulation-based assignment). The price for this simplicity is slower convergence than Frank-Wolfe.

For instance, at iteration $k=5$ with $\mathbf{x}^{(5)} = (70,30)$ and $\mathbf{y}^{(5)} = (0,100),$

$$\begin{align*} \mathbf{x}^{(6)} &= (70,30) + \dfrac{1}{5}\big((0,100)-(70,30)\big) \\[3pt] &= (70,30) + (-14,14) \\[3pt] &= (56,44). \end{align*}$$