Traffic presents a nightmare for city planners. As well as being a pain for commuters, the environmental, financial and social cost of traffic is huge. Cities are still plagued with traffic jams, with rush ‘hour’ being a far too kind a name for the three hour period during which many of the roads are gridlocked. A possible solution to seemingly never ending traffic jams is to add additional infrastructure, but is this always the best solution? Consider the following (made up) scenario.
The school run
Every weekday, 8am sharp, 40 people drive their children from Aelston (A) to Deephurst (D). As things stand, there are two possible routes, going north via Byfair (B) or south via Churchgate (C). The roads connecting AB and CD have lots of lights and a slow speed limit, fixing the flux of traffic, with both roads taking 27 minutes to traverse. The roads connecting BD and AC have no traffic lights but are more prone to jams, taking 5 minutes to travel, plus half a minute for every other car using the road.
The local council, keen to win votes for the upcoming election, have tarmacked the local green space and built a new multilane motorway connecting BC. This 4-lane monstrosity is very fast and only takes 2 minutes to traverse. To the council’s dismay, the travel time for the school run has increased for everyone! Disgruntled and embarrassed, the council have brought in a mathematician to explain what has happened.
Networks and Braess’ paradox
When considering how to present the information above, one might quite naturally draw a network (often called a graph). We represent the areas A to D as ‘nodes’ and the roads as ‘edges’. We assign ‘weights’ to each road, the value being the number of minutes it takes to go from one end of the road to the other. Allowing the edges to have directions, we obtain the following graphs for the pre and post-motorway systems:
Traffic assignment before building the road
Traffic assignment after building the road
where T represents the number of cars on the road.
Now for both systems, we shall seek the user-optimised configuration. This models the selfish nature of individuals using the network. Every driver will, if possible, change their route to the quickest path,
without concern whether the change will slow down everyone else’s journey. This is in contrast with the system-optimised configuration: the routes are assigned by someone who determines the optimal way to minimise the amount of time cars are collectively on the road.
Before the motorway was constructed, it is clear that the user-optimised configuration is to have 20 cars take ABD and 20 take ACD. In this case:
\begin{equation}
\lvert ABD \rvert = \lvert ACD \rvert = 5 + \frac{20}{2} + 27 = 42 ,
\end{equation}
where $\lvert – \rvert$ represents the time taken to complete the route $-$.
After the motorway was constructed, people taking the southern route noticed that avoiding CD would at worst take the same amount of time as going via CBD. This is because T satisfies $T\leq 40$, and hence
\begin{equation*}
\lvert CBD \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert CD \rvert .\\
\end{equation*}
The drivers initially taking the northern route also noticed that the slow road AB could be avoided in a similar manner:
\begin{equation*}
\lvert ACB \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert AB \rvert .\\
\end{equation*}
Hence, no matter what the other 39 cars are doing, it is always beneficial for the selfish driver to take the route ACBD. But, since all the drivers think the same thing, these roads are more congested than before, and the new travel time is
\begin{equation*}
\lvert ACBD \rvert = 5+\frac{40}{2} +2+5+\frac{40}{2} = 52,
\end{equation*}
10 minutes slower than before! However, no driver is willing to change, since any other route in this network with such a configuration is slower! Only if all the drivers cooperate, and agree to resist the temptation of avoiding the slow roads, can the previous system-optimised configuration be achieved. Hence, we see that in user-optimised networks, improved connectivity between two points does not imply a more efficient system. This phenomenon in networks was first demonstrated by Dietrich Braess in 1968, and is aptly named “Braess’ paradox”.
Concluding remarks
In our model, before the new motorway, there were two balanced options. The addition of the motorway then created a new preferable route, with the negative result that all traffic chose to take it, causing congestion. Although this model may seem far from realistically modelling roads, it demonstrates that networks can have this characteristic. Braess’ paradox is seriously discussed in traffic flow literature, and real life examples of this phenomenon are documented. In New York, there were reports of improved traffic when 42nd Street was shut for Earth Day in 1990. In Seoul, South Korea, the government went as far as demolishing a highway near the centre of the city to avoid the road being overused.
Picture of Seoul before and after the destruction of the freeway.
This result is a nice example of how our intuition can be tricked.
More from Chalkdust
Star polynomials
Natalya Silcott introduces us to star polynomials!
Should you buy a Valentine’s day present?
For those of you tackling this dilemma, here's your answer...
Binary magic card trick
Behind today's door... A binary magic card trick!
Killing by numbers: the mathematics of warfare
A blast from the past. Modelling battle grounds from ancient Greece.
The doodle theorem, and beyond…
Colin Wright juggles Euler, doodling and Millennium problems
Cracking the Guess Who? board game
Maths and Decision Theory to be the best at playing Guess Who?
Pingback: 21st of February: I Feel Like Peter | Too Much Time