Braess’ Paradox in City Planning: A Mini-Primary Source Project for Multivariable Calculus Students

Optimization, via both the second derivative test and Lagrange multipliers, is a standard topic in undergraduate multivariable calculus courses. There is also a well-known canon of lovely applications of these techniques, including least squares lines of best fit, Cobb-Douglas production functions, and three-dimensional packaging/container problems.

An entirely separate paradigm for optimization—combinatorial optimization—also exists. While it would be excessive to venture heavily into this topic in a multivariable calculus course, it is possible to offer students a small glimpse into the world of graph theory that further allows them to witness a setting in which either discrete or continuous techniques can be used. This easy detour can be accomplished by looking at a fairly recent, but highly accessible, bit of mathematics known as Braess' Paradox. Braess' Paradox is a counterintuitive phenomenon in which the removal of an edge in a congested network strangely results in improved flow. This is often witnessed in traffic flow settings. For example, when New York City's busy 42d Street was closed to automobiles for an Earth Day celebration, it did not generate the gridlock that people expected, but rather resulted in improved flow [Kolata 1990]. In fact, New York City ultimately decided to make this area permanently pedestrian-only.

Opening shot from time-lapse video “Transit Day 1990 Auto-Free 42nd Street," filmed on 22 April 1990.
Uploaded to YouTube by Trainluvr, 21 September 2011. Reprinted with permission.

The primary source project Braess’ Paradox in City Planning: An Application of Multivariable Optimization walks the student through a guided reading of excerpts from the 1968 paper “Uber ein Paradoxon aus der Verkehrsplanung” [Braess 1968] (or, in English, “On a paradox of traffic planning” [Braess 2005]) in which this intriguing phenomenon was first studied. Written by Dietrich Braess, currently professor emeritus at Ruhr Universität Bochum, this paper describes a method for detecting this paradox in a network using the framework of combinatorial optimization. When Braess’ paper first appeared, the application of mathematics to traffic planning was still a relatively new idea.¹ Today, the paradox that bears his name continues to be studied by mathematical researchers who are interested, for example, in exploring the conditions under which it will not occur. Braess’ paradox is also put to practical use by transportation specialists who are responsible for designing today’s real-life traffic networks. As catalogued by Nagurney & Nagurney [forthcoming], additional applications of Braess’ paradox have been introduced into the modeling of telecommunication networks and the Internet, as well as the study and design of electrical power systems and electronic circuits, mechanical and fluid systems, metabolic networks and ecosystems, and even sports analytics!

Braess' Paradox simulation involving four routes, two of which (in yellow and green) cross the creek bridge.
Observe that the average travel time never exceeds 2 units before the bridge roadblock is removed,
then becomes larger than 2 units once the bridge is opened.
Movie produced by author using the interactive traffic simulator developed by Brian Hayes;
see also [Hayes 2015a, 2015b].

In the student project based on his classic paper, we first retrace Braess' work, and then see how the examples he provided can also be analyzed using standard optimization techniques from a multivariable calculus course. Thus, we provide the student simultaneously with exposure to a second optimization framework and with practice applying the standard multivariable calculus optimization techniques.

The complete project Braess' Paradox in City Planning: An Application of Multivariable Optimization (pdf) is ready for student use, and the LaTeX source code is available from the author by request. A set of instructor notes that explain the purpose of the project and guide the instructor through the goals of each of the individual sections is appended at the end of the student project.

This project is the fifteenth in A Series of Mini-projects from TRIUMPHS: TRansforming Instruction in Undergraduate Mathematics via Primary Historical Sources appearing in Convergence, for use in courses ranging from first-year calculus to analysis, number theory to topology, and more. Links to other mini-PSPs in the series appear below, including four additional mini-PSPs on topics from first-year calculus courses. The full TRIUMPHS collection offers a total of eleven mini-PSPs and one more extensive “full-length” PSP for use with students of calculus.

Note

[1] The first efforts to formulate traffic flow problems mathematically began only in the 1950s, and two publications from that decade [Wardrop 1952, Beckmann et al. 1956] represented the state of the art when Braess himself entered the field. Surprisingly, Braess was completely unaware of those important prior works! His interest in the mathematical modeling of traffic flow instead was inspired by a 1967 seminar talk in which German mathematician W. Knödel presented a certain algorithm that roused Braess’ curiosity. At the time, Braess was 29 years old and had only recently turned to the study of mathematics after completing his doctorate in theoretical physics just three years earlier. Nearly 40 years later, in 2006, Braess delivered his first North American lecture on the paradox named in his honor at the Virtual Center for Supernetworks at University of Massachusetts Amherst. In that lecture, he remarked that both his lack of knowledge of the then-current state of transportation science and his background in physics, which had trained him to look for a counterintuitive symmetry-breaking argument, were important factors in shaping the work that led to his discovery of the paradox that now bears his name.

Acknowledgments

The author would like to thank his advisor Alexander Hulpke and former graduate school classmate Cayla McBee for initial exposure to this wonderful topic! Thanks also to Brian Hayes for creating the simulator which was used to generate the animation above, and for granting permission for its use to produce that animation and to provide a link to the related article Hayes 2015a.

The development of the student project Braess' Paradox in City Planning: An Application of Multivariable Optimization has been partially supported by the TRansforming Instruction in Undergraduate Mathematics via Primary Historical Sources (TRIUMPHS) project with funding from the National Science Foundation’s Improving Undergraduate STEM Education Program under Grants No. 1523494, 1523561, 1523747, 1523753, 1523898, 1524065, and 1524098. Any opinions, findings, and conclusions or recommendations expressed in this project are those of the author and do not necessarily reflect the views of the National Science Foundation. The author gratefully acknowledges this support, with special thanks to TRIUMPHS PI Janet Heine Barnett, who provided assistance with the historical content of the project.

References

Beckmann, Martin J., McGuire, C. B. and Winsten, C. B. 1956. Studies in the Economics of Transportation. New Haven, CT: Yale University Press.

Braess, Dietrich. 1968. Uber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12:258–268.

Braess,Dietrich. 2005. On a Paradox of Traffic Planning. Transportation Science 39(4):446–450. Translation of the original 1968 paper “Uber ein Paradoxon aus der Verkehrsplanung” into English by Anna Nagurney and Tina Wakolbinger.

Hayes, Brian. 2015a. Traffic Jams in Javascript. bit-player blog entry, posted 18 June 2015.

Hayes, Brian. 2015b. Playing in Traffic. American Scientist 103(July–August):260–263.

Kolata, Gina. 1990. What if They Closed 42d Street and Nobody Noticed? New York Times, December 25, 1990, page 38.

Nagurney, Anna and Boyce, David. 2005. Preface to “On a Paradox of Traffic Planning”. Transportation Science 39(4): 443–445.

Nagurney, Anna and Nagurney, Ladimer. ForthThe Braess Paradox. In International Encyclopedia of Transportation, edited by B. Noland, R. Vickerman, and Dick Ettema. Elsevier. Invited chapter, pre-print available at https://supernet.isenberg.umass.edu/articles/braess-encyc.pdf.

Wardrop, John G. 1952. Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institution of Civil Engineers, Part II, 1, no. 2 (August): 325–378.