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:

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:

# 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{split} \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} \end{split}\]

Note that Frank-Wolfe requires the first derivative of the objective function. Thus, we have to specfiy edge cost \(F_e\) and marginal edge cost \(f_e\).

# 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:

# 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:

fw_ue.x

array([1062.36033884, 1183.74866116,    0.        , ..., 1061.32165241,
          0.        , 4203.83194677])

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*} \]

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:

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

1.00883445011059