Frank-Wolfe Traffic Assignment

The Frank-Wolfe algorithm solves the user-equilibrium traffic assignment problem by minimizing the Beckmann objective

$$Z(\mathbf{x}) = \sum_{a \in A} \int_0^{x_a} c_a(s)\, ds,$$

where $A$ is the set of links (or routes), $x_a$ is the flow on link $a$, and $c_a(\cdot)$ is its cost function. The minimizer of $Z$ over the set of demand-feasible flows is the user-equilibrium flow.

For a linear cost $c_a(x_a) = t_a + b_a x_a,$ the link contribution is

$$\int_0^{x_a}(t_a + b_a s)\, ds = t_a\, x_a + \dfrac{b_a}{2}\, x_a^2.$$

For example, if a single link has $c(x) = 2 + 0.5\, x$ and carries flow $x = 4,$ then

$$\int_0^4 (2 + 0.5\, s)\, ds = 2(4) + \dfrac{0.5}{2}(4^2) = 8 + 4 = 12.$$

Frank-Wolfe minimizes $Z$ iteratively. Each iteration has two parts:

1. A direction-finding step (all-or-nothing assignment), and
2. A line search for the step size along that direction.