02 - Traffic Assignment Problem - MM

Wardrop's equilibrium principle

We work under the following assumptions:

Users are rational and selfish individuals. They try to maximize their individual utilities
Users have perfect information on network conditions
Operational conditions on the network are stable during the period of time under analysis

wardrop's equilibrium principle

In a transportation network, to go from origin $p$ to destination $q$ , travelers choose their routes unilaterally and flows split between different available routes $p \to q$ , in a way such that, if a traveller would commute to another route, its own O-D trip time would be worse, while other users, also from $p \to q$ , would benefit from this decision.

Consequently, travelers choose their routes such that all the chosen options result in a unique and minimum travel cost $c_{p q}$ . Non-used routes from $p \to q$ all have a travel cost $c \geq c_{p q}$ .

This means that each user decides what route has the lowest cost for themselves. In the end, the total cost of the network will not be the minimum possible, but each user will have chosen their routes to minimize their own cost at the moment they chose the route.

Wardrop's equilibrium principle example

It is considered useful to visualize the problem through an example.

The simple network below is given:

There is a demand $T$ to go from node $A$ to node $B$ . There are 2 possible paths. The flows of the 2 paths are $v_{1}$ and $v_{2}$ .

The flows have to follow the condition:

v_{1} + v_{2} = T v_{1}, v_{2} \geq 0

The Volume delay functions are:

{\begin{cases} s_{1} (v_{1}) = 1 + v_{1}^{2} \\ s_{2} (v_{2}) = 2 + v_{2}^{2} \end{cases}

We can try an intuitive visualization of the problem:

The #Wardrop's equilibrium principle is reached when both delay function are equal. At that point in fact, the last user could choose link indifferently, as its cost would be the same.

s_{1} (v_{1}^{*}) = s_{2} (v_{2}^{*})

In this case, the condition is met for

v_{1}^{*} = \frac{17}{8} v_{2}^{*} = \frac{15}{8}

And

s_{1} (v_{1}^{*}) = s_{2} (v_{2}^{*}) = 5.51

Keep in mind that if this was a min-cost flow problem, the total cost would be lower. but there would be some users with a much higher cost and some with a much lower cost, going against the #Wardrop's equilibrium principle.

The traffic assignment problem

The Traffic Assignment Problem (TAP) can be written as follow:

Minimize the total cumulative cost in the network subject to the usual network constraints (those that define the links and the demand). In maths terms:

traffic assignment problem

$min_{x} f (x)$
subjet to
$A x = b, x \geq 0$
from which we get the solution $\hat{x}$ .

The TAP can be solved through the Frank-Wolfe Method.

Frank-Wolfe Method

The following problem is given:
$min_{x} f (x)$
subjet to
$A x = b, x \geq 0$
from which we get the solution $\hat{x}$ .

where:

$f (x) : R^{n} \to R$
$A \in R^{n} \times R^{n}$
$x \in R^{n}$
$b \in R^{n}$

The Frank-Wolfe is an iterative method to solve the problem with the following steps

0. Find a feasible solution

The first step is to find any feasible solution $x^{(k)}$ . In the first iteration, $k = 0$ .

This solution has to meet the condition $A x = b, x \geq 0$

1. Define the subproblem

The Frank-Wolfe method works generating a new problem, called a subproblem. This is still an optimization problem but is allegedly easier to solve.

In order to define the new problem, we first need to find the Gradient of $f (x)$ . Then, the subproblem is:
$min_{y} \nabla f {(x^{(k)})}^{T} \cdot y$
subj to:
$A y = b, y \geq 0$
from which we get the value $\hat{y}$ .

Calculate the descent direction

The, we need to calculate a new vector, called the direction, that will allow us to get the solution for the next step of the algorithm.

$d^{(k)} = \hat{y} - x^{(k)}$

2. Stopping criteria

We need some sort of stopping criteria to know if the solution $x^{(k)}$ is close enough to the actual solution $\hat{x}$ of the original problem.

We calculate a relative gap, $r$ as
$r = - \frac{\nabla f {(x^{(k)})}^{T} \cdot d^{(k)}}{\nabla f {(x^{(k)})}^{T} \cdot x^{(k)}}$

We define a relative gap that we find suitable. This is going to be a very small value, $ε$ ( $= 10^{- 2}, 10^{- 4}, . . .$ )

If $r < ε$ than we stop and accept $x^{(k)}$ as a solution ( $x^{(k)} \approx \hat{x}$ ). Otherwise, we go the next step

3. Line search

The new solution will be given by
$x^{(k + 1)} = x^{(k)} + α^{*} d^{(k)}$
where $α^{*}$ is the solution to the problem:
$min_{0 \leq α \leq 1} h (α) = min_{0 \leq α \leq 1} f (x^{(k)} + α d^{(k)})$
This can be solved finding the first derivative of $h (α)$ , imposing it equal to 0 and then solving for $α$ . This last step is often impossible to do analitically, so we rely on numeric methods to find $α^{*}$ (like: Metodo di Newton o Il metodo delle Tangenti, Metodo di Bisezione, Il metodo delle Secanti).

In the particular case that all elements of $\nabla f (x^{(k)}) \overset{△}{=} s (x^{(k)})$ are in the form $a + b x$ , then $α^{*}$ can be taken equal to
$min {1, \tilde{α}}$
where:
$\tilde{α} = \frac{\sum_{i} s_{i} (x_{i}) \cdot d_{i}^{(k)}}{\sum_{i} b_{i} \cdot {(d_{i}^{(k)})}^{2}}$

4. Update

After having found $α^{*}$ is time to update the solution to the next step: $x^{(k)}$ and repeat the method from step #0. Find a feasible solution