Did you know that-

When 42nd street was closed in New York City, instead of the predicted traffic gridlock, traffic flow actually improved?
or
when a new road was constructed in Stuttgart, Germany, traffic flow worsened and only improved after the road was torn up?

These paradoxical phenomena are but two real examples of the Braess paradox, named after Dietrich Braess who, in 1968, noted that in a user-optimized network, when a new link is added, the change in equilibrium flows might result in a higher cost, implying that users were better off without that link.

The Braess paradox is as follows: Consider a simple network with 4 nodes, a single origin node 1, and a single destination node 4, as illustrated by the first network in the figure below. There are 2 paths available to the travelers: path p₁ consists of links a and c, whereas path p₂ consists of links b and d. Let the user link cost functions for the links be given by:
 

where f_a denotes the flow on link a, f_b denotes the flow on link b, and so on.  If the travel demand for the origin/destination node pair of nodes (1,4) is 6, the equilibrium path flows are: x_p1* = x_p2* = 3, the equilibrium link flows are, hence, f_a* = f_b* = f_c* = f_d* = 3, and the incurred travel costs on the paths are: C_p1 = C_p2 = 83. Thus, no traveller/user has any incentive to alter his path since doing so would increase his travel cost.

Now, add a link e from node 2 to node 3 as shown in the second network above. Let the link cost function for link e be c_e(f_e) = f_e + 10. The network is no longer in equilibrium with the original flow pattern, since a path p₃ is now available consisting of  links a, e, and d with a cost of C_p3 = 70. Since 70 is less than 83, the travellers would utilize the new path, resulting in a new equilibrium flow pattern. The equilibrium flow pattern for the new network is  x_p1* = x_p2* = x_p3* = 2. The link flows become f_a* = f_d* = 4 and f_b* = f_c* = f_e* =2. The incurred travel costs on the used paths are: C_p1 = C_p2  = C_p3 = 92. Since the new equilibrium travel cost of 92 is greater that the original one of 83, the addition of the link makes every traveller worse off!

To learn more about Braess Paradox, see Professor Braess' home page.

The Articles: Braess published his article in German, Über ein Paradoxon aus der Verkehrsplanung, in Unternehmensforschung (12, 258–268) in 1968. A Copy of the German Article is available on Professor Braess' homepage.

In 2005, Professor Braess asked Professor Anna Nagurney of UMass to assist him in preparing an English translation of the article. Ms. Tina Wakolbinger, then a Doctoral Student in Management Science at UMass (Dr. Tina Wakolbinger is currently an Assistant Professor at the University of Memphis) and a native of Austria, assisted in the translation. The translated article was published in the November 2005 issue of the journal Transportation Science. Click for a copy of the translation.

The Editor-in-Chief of Transportation Science at that time, Professor Hani S. Mahmassani, asked Professor Nagurney and Professor David Boyce of Northwestern University to write a Preface to the translation.

Links

Homepage of Professor Dietrich Braess

Homepage of Professor Anna Nagurney

Homepage of Professor David E. Boyce

Last Update: February 28, 2009