A solution method

Constrained optimization is a large area of mathematics, with very sophisticated techniques. Some of these techniques can be used for the static assignment problem (95).

Here we want to outline one well-known technique. It is known as Frank-Wolfe algorithm, or convex combinations method. It can be explained in a general way, and then be applied to static assignment, but it can also be applied directly to static assignment, which allows to take advantage of some simplifications right from the beginning. Here we will do the latter.

The idea is to iteratively apply three steps:

Linearize $z(\vec q)$ around some operating point $\vec q^n$, where $n$ denotes the iteration. That is, approximate $z(\vec q) \equiv z(\vec q^n + y)$ by

$$z(\vec q^n) + \vec y \cdot \nabla z \, (\vec q^n) \ .$$ (28.10)

The result of this is that the fitness landscape $z(\vec q)$ is replaced by a hyperplane which goes through $z(\vec q^n)$ and which has the correct slope at $\vec q^n$.

Search, on that hyperplane, for the best solution. On a plane, the best solution is necessarily at the border, so it is sufficient to search the border. Denote this solution by $\vec x^n = \vec q^n + \vec y^n$.

Use a convex combination of $\vec q^n$ and $\vec x^n$ for a new solution:

$$\vec q^{n+1} = \alpha \, \vec q^n + (1-\alpha) \, \vec x^n \ .$$

Ad Item 1: Let us calculate $\nabla z$ when applied to $z(\vec q)$ as defined in Eq. (28.7). Let us do that by component, i.e. $(\nabla z)_b \equiv \partial_b \equiv \frac{\partial}{\partial q_b}$. This is the partial derivative with respect to the $b$th link flow. Only one contribution of the sum depends on $q_b$ at all, and for this one the derivative is trivial:

$$\partial_b \sum_a \, \int_0^{q_a} \, t_a(\omega) \, d\omega = \partial_b \int_0^{q_b} \, t_b(\omega) \, d\omega = t_b \ .$$

Therefore, Eq. (28.12) becomes

$$\tilde z := z(\vec q^n) + \sum_a y_a \, t_a(q_a^n) \ .$$ (28.11)

Ad Item 2: Eq. (28.15) is maybe a little difficult to interpret at first sight, but it is actually rather straightforward. The task is to minimize $\tilde z$ such that the constraints are fulfilled. The constraints are that $\vec q^n + \vec y$ fulfills the OD flow conditions. Note that there is no difference if one minimizes $\tilde z$ or

$$\hat z := \sum_a (\vec q^n + \vec y) \, t_a(\vec q^n) \ .$$

$\hat z$ just means that one has to find feasible flows $\vec x = \vec q^n + \vec y$ such that the sum of all link travel times is minimized, together with the property that link travel times do not depend on the flows. This is achieved when every flow takes the fastest path through the network. In other words, $\tilde z$ is minimized when OD flows are assigned according to fastest paths based on the last iteration.

Interpret that in terms of our agent-based approach: one finds that, given an iteration, progress is made be rerouting some of the OD flows according to what would have been fastest in the last iteration. This is exactly the same in both approaches.

Ad Item 3: The remaining task is to combine the previous solution $\vec q^n$ and the solution, let us call it $\vec x^n$, which minimizes $\tilde z$. As said above, this is done via a convex combination, i.e.

$$\vec q^{n+1} = \alpha \, \vec q^n + (1-\alpha) \, \vec x^n \ .$$

In the agent-based approach, $\alpha$ was just set to 10%, corresponding to a replanning rate of 10%. Because of the analytic formulation in Static Assignment, one can actually search systematically for an optimal $\alpha$. Alternatively, it is possible to make $\alpha$ dependent on the iteration number via $\alpha^n = 1/n$ (method of successive averages, MSA). For MSA one can prove that the method converges towards the correct solution, although convergence may be slow.^28.2