Braess’ Paradox in Networks with Microscopic Stochastic Dynamics and Traffic Information

Abstract

Braess’ paradox describes the counterintuitive situation when the addition of a new road to a network leads to higher travel times for all users. Typically it occurs for selfish drivers that try to minimize their own travel times. Here we investigate whether the occurrence of Braess’ paradox can be prevented if the drivers have access to more detailed traffic information, e.g. as provided by modern navigation apps.

1 Introduction

Nowadays commuters spend up to more than 100 h per year in congestions [1]. However, building new roads is not necessarily a solution to this problem! According to the Fundamental Law of Road Congestion [1] more roads will lead to more road users and thus the new roads will also be congested. But even without an increased traffic volume new roads do not necessarily improve the situation for the drivers. This is exemplified by the so-called Braess paradox [2]:

In road networks of selfish users additional roads can lead to higher travel times for all users.

It can occur in transport networks [3,4,5] and other systems as well [6].

The paradox originates in situations where the user optimum (uo, also called Nash equilibrium), reflecting the driver’s perspective, and the system optimum (so), reflecting a global perspective, are not identical. This can drive the network into a state, the user optimum, in which no driver can improve his/her travel time by choosing an alternative route. For certain network types the user optimum with an additional road may have higher travel times than that of the same network without the new road. Braess presented a mathematical model [2] based on simple networks with 4 and 5 links (where links represent roads), respectively. He showed that for adequately chosen travel time functions for the roads and selfish drivers, the paradoxical situation described above can occur.

The paradox was since observed in several real world situations [7] where newly built roads led to a worse traffic situation or, inversely, where the closing of roads led to an improvement of the traffic situation. It is related to the concept of the price of anarchy which is a measure for the reduced efficiency of a system due to the selfish behavior of agents [8].

Here we extend our previous work [9, 10] in which we have shown that Braess’ paradox occurs in networks of stochastic transport models in the following two cases: (1) routes are chosen stochastically by each driver. In this case, so-called mixed user optima (muo)/mixed Nash equilibria are observed [9], and (2) drivers use fixed strategies for their route choices. In this case, so-called pure user optima (puo)/pure Nash equilibria are observed [10]. We address the question whether Braess’ paradox can be avoided by providing traffic information, i.e. with more realistic decisions by the drivers. Modern traffic information systems provide drivers with up-to-date information about the traffic state on different routes or even predictions of travel times. We have introduced such information into the model to study its effects on the occurrence of the paradox.

2 Model

Braess’ original model is based on a macroscopic and deterministic traffic model for which the travel time depends only on the number of cars on the road. We have generalized this previously to more realistic microscopic stochastic dynamics [9, 10] without changing the structure of the original simple network (Fig. 69.1).

Fig. 69.1

Structure of the network. All particles are considered to move from the start at $j_1$ to the finish at $j_4$. In Braess’ original network the link $E_0$, ensuring periodic boundary conditions, is missing. Without the link $E_5$ we call the network 4link, with link $E_5$ 5link network. The dynamics on each link is modeled by TASEPs

Link $E_5$ is the new link that is considered to be added to the network and the network without/with that link is from here on called the 4link/5link network (corresponding variable names are marked by the superscripts (4)/(5)). All drivers want to go from the start at $j_1$ to the finish at $j_4$. For this they can use 2 (3) different routes in the 4link (5link) network: routes 14, 23 and 153 (the latter is only available in the 5link network). Route 14 leads from $j_1$ to $j_4$ via $E_1$, $j_2$, $E_4$ (routes 23 and 153 accordingly). The traffic on the network is modeled by the paradigmatic totally asymmetric exclusion process (TASEP) (Fig. 69.2).

Fig. 69.2

TASEP of length L with open boundary conditions. In the case of random sequential update rules a site is chosen randomly. If it is occupied, the particle can jump to the right neighbor site if this next site is empty. Particles are added (removed) at the left (right) boundary with rate $\alpha$ ($\beta$)

The TASEP is based on stochastic dynamics which allows including fluctuations and provides a mechanism for spontaneous formation of jams. It is the $v_\mathrm{max}=1$ limit of the Nagel-Schreckenberg cellular automaton model of highway traffic. Note that we consider here the TASEP with random-sequential update.

Previously, we have considered two different cases in which the driver’s route choices are tuned externally, i.e. each driver chooses routes (1) stochastically [9], and (2) using fixed strategies [10]. In the stochastic case, on junction $j_1$, particles turn left (i.e. onto $E_1$) with probability $\gamma$ or right (i.e. onto $E_2$) with probability $1-\gamma$. On junction $j_2$, particles turn left (i.e. onto $E_4$) with probability $\delta$ or right (i.e. onto $E_5$) with probability $1-\delta$. In the case of fixed strategies, fixed subsets of $N_{14}$ / $N_{23}$ / $N_{153}$ particles choose routes 14 / 23 /153. These three parameters can be encoded in the two variables $n_\mathrm{l}^{(j_1)}=1-\frac{N_{23}}{M}$ and $n_\mathrm{l}^{(j_2)}=\frac{N_{14}}{N_{14}+N_{153}}$ that denote the fractions of particles turning left at $j_1$ and $j_2$, respectively, with M being the total number of particles in the network. Mixed and pure user optima can be found by varying the $\gamma$, $\delta$ or the $n_\mathrm{l}^{(j_1)}$, $n_\mathrm{l}^{(j_2)}$, respectively.

Both model versions with externally tuned strategies show rich phase diagrams that include extended regions where the Braess paradox occurs (Fig. 69.3). The shown phase diagrams were obtained for a network with edges $E_i$ of the lengths $L_0=1$, $L_1=L_3=100$, $L_2=L_4=500$. The length of a route i (i.e. the sum of the lengths of the TASEPs that make up the route and the number of junction sites on the route) is denoted by $\hat{L}_i$. The network was studied for different lengths of $E_5$ that lead to different lengths of the new route 153 ($\hat{L}_{153}$) compared to the lengths of the two old routes 14 and 23 ($\hat{L}_{14}=\hat{L}_{23}$), as denoted by the route length ratio $\hat{L}_{153}/\hat{L}_{14}$. The phase the system is in depends on $\hat{L}_{153}/\hat{L}_{14}$ and the global density $\rho _\mathrm{global}$, which is M divided by the total number of sites (sum of all TASEP sites and junction sites).

Fig. 69.3

Phase diagrams for externally tuned strategies via a fixed route choices [10] and b turning probabilities [9]. Sub-phases can be found in [9, 10]. The points $\star 1,...,\star 4$ indicated have been studied for the influence of traffic information [12]

Here we will study the effect of traffic information on the occurrence of Braess’ paradox. Generically one can distinguish between public information, as e.g. provided by navigational systems, and personal information which could e.g. be based on personal experience. Furthermore, in networks one can distinguish (1) historical information based on existing data, (2) current information based on the up-to-date traffic state determined by measurements, and (3) predictive information, e.g. based on computer simulations.

We have implemented two different route choice algorithms where all agents choose their routes intelligently based on

• 1. travel time predictions based upon the current network state, i.e. public predictive information,

• 2. their own memory of travel times, i.e. personal historical information.

Algorithm 1 captures the effects of modern navigation apps in a simple way whereas algorithm 2 corresponds to a commuter scenario where the agents drive each day from their home to their office relying only on their past experiences.

To find out whether user optima in the 4link and 5link networks that are obtained by externally tuning the particles’ strategies are realized by intelligently deciding agents, we implemented the following route choice algorithm. First, M agents are placed randomly on the routes. Each agent is assigned an initial pure strategy (choosing either route 14, 23 or 153) randomly. After a relaxation procedure that depends on the type of information used [11, 12], all particles have information about the expected travel times $T_{14,\mathrm {info}}$, $T_{23,\mathrm {info}}$ and $T_{153,\mathrm {info}}$ of all three routes 14, 23 and 153. After relaxation is complete, route choice decisions can occur at three points: before starting a new round (i.e. on edge $E_0$) and during a round on sites $j_1$ and $j_2$ when a jump to the desired target site is not possible. Before a new round, when sitting on $E_0$ before jumping to $j_1$, each particle generally chooses the route i with the lowest $T_{i,\mathrm {info}}$. To make such a decision more realistic, it contains a stochastic component [11, 12].

3 Results

In order to reduce the required computational load we have chosen four interesting points from the phase diagrams determined previously for stochastic route choice [9] and fixed strategies [10] (see Fig. 69.3). Here we only present results for point $\star 3$, which is in the Braess phase in both previously studied situations, and the case of public predictive information. The parameters for point $\star 3$ in the phase diagram are the length of the new road, $L_5=37$, and a total of $M=248$ particles in the system. This corresponds to a route length ratio of $\hat{L}_{153}/\hat{L}_{14}\approx 0.4$ and global densities $\rho ^{(4)}_\mathrm{{global}}\approx 0.21$ and $\rho ^{(5)}_\mathrm{{global}}\approx 0.20$ in the 4link and 5link systems. As detailed in [11, 12], the 5link system of state $\star 3$ with externally tuned parameters has two pure user optima (puo(i) and puo(ii)) and one mixed user optimum (muo). For a more detailed discussion of the other points and other types of traffic information, we refer to [11, 12].

Public predictive information is provided on the basis of the current positions of all cars in the network. It is a simplified version of the traffic information provided by navigation apps. The algorithm predicts travel times on the basis of the total number of vehicles on each link of the network, i.e. the global densities $\rho _i$ on each link i. The predicted travel time for link i with length $L_i$ is then

$$\begin{aligned} T_{i,\mathrm{pred}}= \frac{L_i}{1-\rho _i}\,, \end{aligned}$$

(69.1)

which is based on the exact travel time of a particle in the stationary state of a TASEP with periodic boundary conditions at density $\rho _i$ [9]. These $T_{i,\mathrm{pred}}$ are then used as the $T_{i,\mathrm{info}}$ for the route choice processes of the particles.

Fig. 69.4

Results for public predictive information in state $\star 3$. a Mean travel times realized by intelligently deciding agents (coloured lines). The expected travel times in the pure and mixed user optima found by externally tuning the strategies are shown by the dotted lines with $T_\mathrm{max,muo}^{(4)}=\tau _1$, $T_\mathrm{max,puo}^{(4)}=\tau _2$, $T_\mathrm{max,muo}^{(5)}=\tau _3$, $T_\mathrm{max,puo(i)}^{(5)}=T_\mathrm{max,puo(ii)}^{(5)}=\tau _4$. b Particle strategies realized by the route choice algorithm (coloured lines). The strategies realizing the user optima by externally tuning the strategies are given for comparison with $n_\mathrm{l,puo}^{(j_1)(4)}=\sigma _3$, $\gamma _\mathrm{muo}^{(4)}=\sigma _3$, $\left( n_\mathrm{l,puo(i)}^{(j_1)(5)},n_\mathrm{l,puo(i)}^{(j_2)(5)}\right) =\left( \sigma _3,\sigma _1\right)$, $\left( n_\mathrm{l,puo(ii)}^{(j_1)(5)},n_\mathrm{l,puo(ii)}^{(j_2)(5)}\right) =\left( \sigma _5,\sigma _3\right)$, $\left( \gamma _\mathrm{muo}^{(5)},\delta _\mathrm{muo}^{(5)}\right) =\left( \sigma _4,\sigma _2\right)$

Figure 69.4 shows results for the case of public predictive information for the state $\star 3$ indicated in Fig. 69.3. The result of a single Monte Carlo simulation of the system is shown. The general behavior has been confirmed in numerous test runs. The shared x-axes of Fig. 69.4 show the system time. All times are measured in units of the number of performed Monte Carlo sweeps. Figure 69.4a shows the mean travel times $\bar{T}_i$ on the routes i, as realized by the intelligently deciding agents. The maximum travel times $T_\mathrm{max}$ in the user optima found by externally tuning the decisions are shown for comparison. Figure 69.4b shows which routes the particles take. The $m_\mathrm{l}^{(j_1)}$ and $m_\mathrm{l}^{(j_2)}$ show the fractions of agents turning left at junctions $j_1$ and $j_2$. The strategies of the accessible pure and mixed user optima realized by externally tuning the decisions are shown for comparison. We see that the user optimum of the 4link system is realized. Figure 69.4b shows that half of the agents use routes 14 and 23, respectively. Figure 69.4a indicates that the travel times of both routes equalize at the expected value. Interestingly, in the 5link system the route choice algorithm leads to strong fluctuations around the pure user optimum $\mathrm {puo(ii)}$ (Fig. 69.4b). In this state route 23 is not used and half the agents choose route 14 and the other half route 153. Due to the fluctuations around the user optimum the travel times of the two used routes 14 and 153 are close to each other but not exactly equal (Fig. 69.4a). All travel times are higher than those of the two routes in the 4link system. Thus indeed a Braess state is realized. Route 23, which is almost not used, has an even higher travel time, as expected.

4 Summary

We have studied the effects of traffic information on the occurrence of Braess’ paradox in a network with microscopic, stochastic traffic dynamics. Modern traffic information systems provide drivers with up-to-date information about the traffic state on different routes or even predicted travel times. We have introduced such information into the model and find that Braess’ paradox still occurs.