Bezoek de website voor leraren en scholieren →

In a preceding article we have used a simple model to demonstrate how selfish behavior can create additional congestion. One way to mitigate the consequences of selfish behavior, is by introducing tolls (or taxes) on certain parts of the road network. This is also known as road pricing, and such a system was first successfully implemented in Singapore (click here for more info).

The idea is that drivers will not only choose their route based on the travel time along a path through the network, but they will also take into account the toll or tax they have to pay on that path. This toll may vary along the day (think of higher tolls during rush hour) or can depend on the amount of traffic congestion on certain parts of the network. The goal is to choose the tolls in such a way so that the traffic spreads out nicely over all paths, leading to an efficient (or even optimal) usage of the network.

In the remainder of this article, we will see how tolls can be used in order to improve the inefficient network usage in Pigou's example from the previous article. The Pigou network is given below. The latency functions on the arcs, describing how long it takes to travel between the two points, are  $l_1(x_1) = x_1$ and $l_2(x_2) = 1$ where $x_i$ is the amount of traffic on arc $a_i$. One unit of flow has to be divided over the two arcs.

In the selfish equilibrium $x$, all flow is sent over the first arc, that is, $x = (x_1,x_2) = (1,0)$. In the social optimum $x^*$, the flow is split among the two arcs, that is, $x^* = (x_1^*,x_2^*) = (1/2,1/2)$ (see the previous article for details).

We now explain how the tolls are modeled. On every arc $a$, we introduce a non-negative (constant) $\tau_a$ representing the toll. The new objective of the drivers is to minimize a combination of latency and toll. At first this might seem somewhat strange, since $l_a(x_a)$ is interpreted in terms of time, and $\tau_a$ in terms of money. We assume that drivers 'transform' the toll into time, e.g., 10 euros might correspond to 30 minutes of travel time. This transformation is modeled by the (sensitivity) parameter $\gamma$. The new objective of the drivers is now to minimize the combined cost $c_a(x_a) = l_a(x_a) + \gamma \cdot \tau_a$. In the example above, we have $\gamma = 3$ (if we measure time in minutes and money in euros). Of course, different drivers might make different transformations, but here we assume they all do this in a similar way, i.e., we say the drivers are homogeneous. If different drivers make different transformations, we call them heterogeneous. This can be represented in the combined cost by introducing parameters $\gamma_i$ that represent the transformation factor of the $i$-th class of drivers, i.e., the combined cost then becomes $l_a(x) + \gamma_i \cdot \tau_a$ for the drivers in class $i$.

Another important modeling assumption is that we assume that (for example) a government is not interested in the profits they make from this toll system, that is, their (quantitative) measure for system performance is still the average travel time. This can be justified in many ways. E.g., it might be the case that the tolls are needed to pay for the implementation of the toll systems. Or, in case the average travel time measure is used as an indication for the emission of green house gasses, the obtained tolls do not play a role, since these do not (directly) decrease the emission of green house gasses.

The main question is now: How should the tolls be chosen in order to decrease the average travel time? Or even better, to achieve the smallest possible average travel time. We call the traffic flow creating the smallest average travel time the social optimum. For Pigou's example, we have seen that the average travel time is minimized for the social optimum $x^* = (x_1^*,x_2^*) = (1/2,1/2)$, meaning that half of the traffic takes the upper road and the other half takes the lower road. This flow $x^*$ is not an equilibrium with respect to the latencies as $l_1(x^*_1)=x^*_1=1/2$ and $l_2(x^*_2)=1$. So, how should we choose the tolls $\tau_1,\tau_2$ such that the combined costs $c_a(x_a)$ are at equilibrium, meaning that

Exercise 4: How to choose the tolls $\tau_1$ and $\tau_2$, such that the both roads are used according to the social optimum $x^* = (x_1^*,x_2^*) = (1/2,1/2)$? Consider that the drivers base there decision on the combined costs, and for simplicity, assume that $\gamma=1$.

How many of combinations of $\tau_1$ and $\tau_2$ can you find? Which combination minimizes the sum of the tolls?

• Article

### Predicting optimal routes in unpredictable networks•

How does your navigation system find the fastest route in a road network, if it does not know where traffic jams occur and how long they last?
Read article
• Article

### Why you may need to reconsider your route selection criterium•

You have a job interview in 20 minutes and you are in a hurry to arrive at your application in time. To make matters even more stressful, there are many routes to your destination, but you have no idea which one to select. Luckily, you have access to a navigation system that can help you in your route selection process.
Read article
• Article

### Ding-Dong! Finally, your delivery driver is at your door••

Why your packages arrive too late: the challenges (and solutions) behind last-mile delivery.
Read article
• Article

### DNA self-assembly gives birth to new mathematics••

At this very moment, the emergent science of DNA self-assembly is giving birth to a new field of mathematics that might be called DNA-mathematics. Cleverly constructed DNA molecules will self-assemble into pre-determined complex structures when placed in solution together.
Read article
• Article

### Picking up 13 different cards from 13 piles (Part 2)••

In Part 1 Jackie explained to her fried Sam how the problem of picking a card from each of the 13 piles so that there is exactly one card with each rank translates to a problem on bipartite graphs. The mathematical problem asks you to find a perfect matching in a regular bipartite graph.
Read article