# Price of Anarchy - Barcelona

## 1. Imports and network readin

First, we import the *paminco* and some other packages and download the traffic data for Barcelona from [GitHub](https://github.com/bstabler/TransportationNetworks/tree/master/Barcelona):


```python
import os
import requests

import paminco

URL = "https://raw.githubusercontent.com/bstabler/TransportationNetworks/master/Barcelona/"
netfile = "Barcelona_net.tntp"
tripsfile = "Barcelona_trips.tntp"

# Load from GitHub and save locally
for f in [netfile, tripsfile]:
    url = os.path.join(URL, f)
    response = requests.get(url)
    with open(f, 'wb') as fh:
        fh.write(response.content)
```

Note that the power factor $p_e$ for the link travel time $l_e(x_e) = \text{fft}_e \cdot \left( 1 + B_e \cdot \left(\frac{x}{\text{cap}_e}\right) ^ {p_e} \right)$ is ``not`` an integer for the Barcelona network, where we find power factors such  ``4.446, 4.924, ...``.

However, we can equip a network with custom cost functions by setting ``cost_type=symbolic``:


```python
# Setup network
net = paminco.Network.from_tntp(netfile, tripsfile=tripsfile, cost_type="symbolic")

# Cleanup
for f in [netfile, tripsfile]:
    os.remove(f)
```

## 2. Setting up network cost

Second, we set up SymbolicCost, defining the edge cost $F_e$ and thus the objective function to calculate both user equilibrium (UE) and system optimum (SO).
We find minimum cost flows for user equilibrium and system optimum if we transform the edge cost by:

$$
\begin{align}
    \text{User equilibrium:} \quad F_e &= \int_0^{x_e} l_e(s) ds \\ 
    \text{System optimum:} \quad F_e &= x_e \cdot l_e \\ 
\end{align}
$$

Note that [Frank-Wolfe](https://en.wikipedia.org/wiki/Frank%E2%80%93Wolfe_algorithm) requires the first derivative of the objective function.
Thus, we have to specfiy edge cost $F_e$ and marginal edge cost $f_e$.



```python
# User equilibrium cost funcs (egde cost and marginal edge cost)
ue_F = "fft * (x + b * x / (p + 1) * (x / c)**p)"
ue_f = "fft * (1 + b * (x / c)**p)"

# System optimum cost funcs (egde cost and marginal edge cost)
so_F = "x * fft * (1 + b * x**p * c**(-p))"
so_f = "fft + fft * b * (p + 1) * c**(-p) * x**(p)"

net.cost.coeffs["fft"] = net.cost.coeffs["free_flow_time"]
net.cost.coeffs["c"] = net.cost.coeffs["capacity"]
net.cost.coeffs["p"] = net.cost.coeffs["power"]
```

## 3. Find UE and SO flow

Finally, we equip our network with both cost functions instances and run Frank-Wolfe to find a minimum cost flow:


```python
# copy networks
from copy import deepcopy

# user equilibrium
net_ue = deepcopy(net)
net_ue.cost.funcs["F"] = ue_F
net_ue.cost.funcs["f"] = ue_f
fw_ue = paminco.NetworkFW(net_ue)
fw_ue.run(max_iter=10, print=False)

# system optimum
net_so = deepcopy(net)
net_so.cost.funcs["F"] = so_F
net_so.cost.funcs["f"] = so_f
fw_so = paminco.NetworkFW(net_so)
fw_so.run(max_iter=10, print=False)
```

For example, we can easily access the user equilibrium flow by:


```python
fw_ue.x
```




    array([1062.3604087 , 1183.7485913 ,    0.        , ..., 1061.32166004,
              0.        , 4203.83150619])



## 4. Price of Anarchy

The objective function to calculate the system optimum is the total system travel time (TSTT):

$$
\begin{equation*}
    \text{TSTT}(\mathbf{x}) = \sum_{e \in E} x_{e} \cdot l_{e}(x_e)
\end{equation*}
$$


```python
def TTST(x):
    return net_so.cost(x).sum()
```

We find that the total system travel time for Barcelona is increased by about ``0.9 percent`` if users behave selfishly:


```python
poa = TTST(fw_ue.flow) / TTST(fw_so.flow)
poa
```




    1.0088344480937708



c454d75f649d5f9b80ee74772d60aab6cbf6b9ca
ipynb
Jupyter Notebook
docs/source/user_guide/applications/traffic/barcelona_poa.ipynb
paminco/paminco
2b8da7cc83adde3c72af5150cf6d7294ff6fd29e
MIT
2021-12-30T06:25:09.000Z
2022-01-06T17:28:57.000Z
docs/source/user_guide/applications/traffic/barcelona_poa.ipynb
paminco/paminco
2b8da7cc83adde3c72af5150cf6d7294ff6fd29e
MIT
2021-12-13T07:38:13.000Z
2021-12-21T16:43:15.000Z
docs/source/user_guide/applications/traffic/barcelona_poa.ipynb
paminco/paminco
2b8da7cc83adde3c72af5150cf6d7294ff6fd29e
MIT
Qwen/Qwen-72B
1. YES
2. YES