Traffic Jams in Javascript

Building bigger roads can make traffic worse. The usual explanation for this counter­intuitive and counterproductive outcome is that bigger roads attract bigger shopping malls, which in turn attract more cars. But that’s not the whole story. In the 1960s Dietrich Braess discovered a theoretical configuration of roadways where building a new connecting road can make everyone’s trip slower even when the number of vehicles is held constant. Conversely, closing a road in the Braess network can allow everyone to get home quicker. The behavior is weird enough to justify the term “Braess’s paradox.”

A few years ago Joel Cohen suggested to me that Braess’s paradox might make a good topic for my “Computing Science” column. I hesitated. There were already plenty of published discussions of the paradox, including excellent ones by Cohen himself, as well as a book by Tim Roughgarden (which I had reviewed for American Scientist). I didn’t think I had anything more to add to the conversation.

Lately, though, I began to consider the problem of visualizing Braess’s paradox—presenting it in such a way that you can watch individual cars navigating through the road network, rather than merely calculating average speeds and travel times. Having an opportunity to play with the model—fiddling with the knobs and switches, trying different routing algorithms—might lead to a clearer understanding of why well-informed and self-interested drivers would choose a route that winds up making everybody late for dinner.

I now have a working JavaScript model of something resembling Braess’s paradox, which I urge you to go take for a test drive. There’s an accompanying “Computing Science” column in the latest issue of American Scientist, available on the magazine website in HTML or PDF. If you’re interested in the source code, it’s on Github. Here I’m going to say a few words about the implementation of the model and what I’ve learned from it.

Adapting Braess’s mathematical model to a more mechanistic and visual medium was trickier than I had expected. The original formulation is quite abstract and not very physical; it’s closer to graph theory than to highway engineering. In the diagrams below the wide, blue roads labeled A and B never become congested; no matter how much traffic they carry, the transit time for these links is always one hour. The narrow red roads a and b offer a transit time of zero when they’re empty, but traffic slows as the load increases; if everyone crowds onto a single red link, the transit time is again one hour. As for the gold route X, this magical thoroughfare offers instantaneous transport for any number of vehicles.

The presence or absence of the X road is what triggers the paradox. Without the golden crosslink (left diagram), traffic splits equally between the Ab and aB routes, and all cars take 90 minutes to complete the trip. When the X link is opened (right diagram) all drivers favor route aXb, and everyone spends a full two hours on the road.

The essential supposition behind the paradox is that everyone follows a selfish routing policy, choosing whichever route offers the quickest trip, and ignoring all factors other than travel time. And, ironically, it’s the insistence that no one else may have a shorter trip that leaves all the drivers in a bumper-to-bump jam on route aXb, while AXB sits empty. Why? If any driver decided to defect to AXB, the departure would marginally lessen the load on aXb, giving the latter route a slight speed advantage. Under the selfish policy, the defecting driver would then have to return to aXb. It’s a stalemate.

Cars moving at infinite speed and roads with infinite capacity may be all right in a mathematical model, but they are troublesome in a simulation that’s supposed to look something like real highway traffic. Seeking a more realistic model, I settled on the road layout shown below, inspired by a diagram in a 1997 paper by Claude M. Pinchina (Braess Paradox: maximum penalty in a minimal critical network. Transportation Research A 31(5):379–388).

The topology is the same as that of Braess’s original network, but the geometry is different, and so is the relation between congestion and speed. The aim is still to get from start to end—or, rather, from Origin to Destination. The A and B road segments are again wide and insensitive to traffic congestion. The a and b roads are straighter and shorter but also narrower. With zero traffic, vehicle speed is the same on a and b as on A and B, but as traffic gets heavier, speed falls off. The analogue of the “golden road” is a short bridge at the center of the map, which has the same speed properties as A and B. In the initial configuration, the bridge is blocked off, but a mouseclick opens it. In the snapshot of the running model shown above, the bridge is open and carrying traffic.

Cars, represented by colored dots, enter the system at the Origin. At the moment of launching, each car chooses one of the available routes. If the bridge is closed, there are just two possibilities: Ab and aB. With the bridge open, drivers also have the option of the ab shortcut or the longer AB. The cars then advance along the selected roadways, governed by the speed restrictions on each segment, until they reach the Destination.

This scheme differs in several important ways from the original Braess formulation. Does it still exhibit the paradox? In other words, does the travel time increase when the bridge is opened, allowing traffic to flow over routes ab and AB? The answer is yes, for a wide range of parameter values, as shown in these outputs:

The tables show the number of vehicles choosing each route and the average time they spend on the road. (The times are measured in units of the quickest possible trip: taking the shortest route ab with zero traffic.) Note that opening up the bridge slowed down travel on all four routes. Even though the Ab and aB routes carried about 37 percent less traffic when the bridge was open, cars on those routes took 9 to 15 percent longer to complete their journeys. The ab and AB routes were even slower.

But the numbers don’t tell the whole story—that was the first thing I learned when I got the simulation running. In the bridge-closed state, where the total traffic splits into two roughly equal streams, you might imagine successive cars alternating between Ab and aB, so that the system would reach a statistical steady state with equal numbers of cars on each of the two routes at any given moment. That’s not at all what happens! The best way to see what does happen is to go run the simulation, but the graph below also gives a clue.

Instead of settling into a steady state, the system oscillates with a period of a little less than 500 times steps, which is roughly half the time it takes a typical car to make a complete trip from Origin to Destination. The two curves are almost exactly 180 degrees out of phase.

It’s not hard to understand where those oscillations come from. As each car enters the road network, it chooses the route with the shortest expected travel time, based on conditions at that moment. The main determinant of expected travel time is the number of cars occupying the a and b segments, where speed decreases as the roads get more crowded. But when cars choose the less-popular route, they also raise the occupany of that route, making it appear less favorable to the cars behind them. Furthermore, on the Ab route there is a substantial delay before the cars reach the congestion-sensitive segment. The delay and the asymmetry of the network create an instability—a feedback loop in which overshooting and overcorrection are inevitable.

When the connecting bridge is opened, the pattern is more complicated, but oscillations are still very much in evidence:

There seem to be two main alternating phases—one where Ab and ab dominate (the Christmas phase, in this color scheme), and the other where ab and AB take over (the Cub Scout phase). The period of the waves is less regular but mostly longer.

I am not the first to observe these oscillations; they are mentioned, for example, by Daniele Buscema and colleagues in a paper describing a NetLogo simulation of Braess-like road networks. Overall, though, the oscillations and instabilities seem to have gotten little attention in the literature.

The asymmetry of the layout is crucial to generating both the oscillations and the paradoxical slowdown on opening the central connecting link. You can see this for yourself by running a symmetric version of the model. It’s quite dull.

One more bug/feature of the dynamic model is worth a comment. In the original Braess network, the A and B links have unlimited capacity; in effect, the model promises that the time for traversing those roads is a constant, regardless of traffic. In a dynamic model with discrete vehicles of greater-than-zero size, that promise is hard to keep. Consider cars following the Ab route, and suppose the b segment is totally jammed. At the junction where A disgorges onto b, cars have nowhere to go, and so they spill back onto the A segment, which can therefore no longer guarantee constant speed.

In implementing the dynamic model, I discovered there were a lot of choices to be made where I could find little guidance in the mathematical formulation of the original Braess system. The “queue spillback” problem was one of them. Do you let the cars pile up on the roadway, or do you provide invisible buffers of some kind where they can quietly wait their turn to continue their journey? What about cars that present themselves at the origin node at a moment when there’s no room for them on the roadways? Do you queue them up, do you throw them away, do you allow them to block cars headed for another road? Another subtle question concerns priorities and fairness. The two nodes near the middle of the road layout each have two inputs and two outputs. If there are cars lined up on both input queues waiting to move through the node, who goes first? If you’re not careful in choosing a strategy to deal with such contention, one route can be permanently blockaded by another.

You can see which choices I made by reading the JavaScript source code. I won’t try to argue that my answers are the right ones. What’s probably more important is that after a lot of experimenting and exploring alternatives, I found that most of the details don’t matter much. The Braess effect seems to be fairly robust, appearing in many versions of the model with slightly different assumptions and algorithms. That robustness suggests we might want to search more carefully for evidence of paradoxical traffic patterns out on real highways.

This entry was posted in computing, featured, mathematics, modern life.

12 Responses to Traffic Jams in Javascript

1. John Cowan says:

It seems to me that the main deficiency in realism is the assumption that cars choose a route based on knowledge of the current global transit time. In reality, unaided cars choose a route based on the local situation (are most cars choosing a or A at the moment?), or if they have access to traffic-and-transit reports, based on information about the most congested segment.

• Brian Hayes says:

It was surely true when Braess wrote in 1968 that drivers could only guess or extrapolate from local conditions. But now? Everybody has live traffic info on a GPS unit or smartphone, no? One of the big questions is whether more complete information leads to more extreme oscillations.

• John Cowan says:

Doubtless. But unless it can predict the future, it doesn’t tell you how long it will take you to traverse a particular pathway starting now.

• Mike C says:

While it may not be able to predict the future, Google Maps does give people an approximation of travel time based on it’s understanding of traffic conditions. I know a number of people who use it for this very purpose.

2. Anne L says:

Fascinating subject and article. It appears cars in this simulation choose a complete travel route (“color”) when leaving the origin, and then do not update that choice as traffic conditions change. This situation does not appear optimal (cars choose B vs. b using out-of-date information) nor necessarily reflective of current and future driver behavior (aided by continuously updating GPS and smart phone). I wonder if the apparent synchronicity of Ab/ab vs. aB/AB depends on this assumption, leaving open the possibility of even more complicated system behavior in a perfectly selfish, perfectly informed world.

• Brian Hayes says:

In the first version of the program, cars re-evaluated the expected travel time at each node and chose their next segment accordingly. I switched to the current scheme — with an irrevocable commitment at the point of departure — for two reasons. First, it seemed a little more in the spirit of the original Braess model. Second, I intended the program mainly as a tool for visualization, not research, and having cars change color in mid course turned out to be visually confusing.

Of course real drivers do have opportunities to change their minds, so you clearly have verisimilitude on your side. I could probably add it as yet another option in the already comically busy control panel.

But let me also note that I did not see any qualitative difference in the outcome when I switched from one protocol to the other. Cars did revise their choices; occasionally they even changed their mind twice, crossing the bridge and then making a U turn to go the way they originally planned. But the overall statistics were not much affected.

3. Carl Anderson says:

Really fascinating article. I’d love to see a comparative analysis of the different approaches mentioned (perfectly selfish, perfectly informed vs perfectly selfish, poorly informed). There should be some difference, but how much and in what way? Do the oscillations even out, or become more extreme, etc?

• Brian Hayes says:

One data point: Choosing routes at random consistently outperforms any selfish routing algorithm.

• Nick l says:

Usually when something at random outperforms an alternative, there is a deficiency of knowledge. I am surprised you mentioned the node revising algorithm was similar to not. What information is missing at the node to fully inform the vehicle and make a “proper” choice?

4. James Hatfield says:

Seems like this will in fact become a potentially bigger problem as we begin putting autonomous vehicles on the roads. I wonder what if any guards are available to prevent this from happening. With humans at least you have people who always follow the same route because it’s familiar. With ai there will always need to be a min or max function based on time. If adding a road can cause pile ups then adding a new route could do the same, e.g. When the best routes available are already at capacity adding a new route between destinations could actually make things worse. Would a route finding algo be able to determine that its fallen into a local maximum “saddle ridge” because of this paradox?

5. Simeon Pilgrim says:

I like the simulation, but it seems wrong that the AB traffic is blocked on the A section due to the Ab traffic unable to enter the b section. If AB is infinite, it should seem there would be a “turning laying” that the b bound traffic gets stuck in, but as it stands in the bridge open case, I observed AB get the worse time, which it should not be the case according to the theory.

• Brian Hayes says:

It’s yet another choice one has to make when implementing the model. I chose to view the nodes of the graph as ordinary surface-road intersections, which can be occupied by only one car at a time. One could think instead of highways with overpasses and underpasses. That would also be a valid model, but it’s not the model I built.

As for cars on the AB route taking a longer time, that’s the case even without contention for resources at intersections. AB is roughly twice as long as ab, and 1.5 times the length of Ab and aB.