Traffic flows present many interesting cases for optimization. In this blog post, we describe a simple model of convex optimization (unfortunately, not an LP) to represent optimizing traffic flows through a network, and then discuss a paradox that can arise whereby adding roads to the network can actually increase the commuting time in a system.
A Traffic Optimization Model
We want to model the following problem: there are two points of interest that a given number of people want to travel between. For simplicity, we will only consider one way, giving us a start point and an end point. In addition to these two points, there are several intermediate points between which we can build roads. We must decide which roads to build to minimize total travel time between the points.
Model the road network as a graph whereby are the set of nodes and are the set of roads that connect nodes. Further, denote as the start and end nodes of the vertex, and as all other nodes in the system. Let be the decision variables in the system: how many travelers use route . Let be the total number of commuters in the system. Let be the “fixed travel time” associated with each road, and let be the “variable travel time” associated with each road (usually travel time per person using the road). The fixed time corresponds to the minimum time required to travel on a road, while the variable time accounts for traffic. Thus, our optimization formulation is:
Although this isn’t a LP, the objective is convex in our decision variables, so hopefully we will learn tools throughout the semester to solve such problems!
In normal cases of convex optimization (such as our model above), increasing the “feasible set” of solutions can never lead to a worse optimal solution. However, introducing individual agents that selfishly try to maximize their own utility into a model can paradoxically cause the introduction of more options to lead to worse results. This paradox, as originally applied to traffic, is known as Braess’s Paradox, which states that adding additional capacity to a network with selfish agents can reduce overall performance.
A Theoretical Example
Consider the following network, in which 4000 commuters are trying to get from point A to point B: The travel times for routes and routes are fixed (we can imagine these perhaps as wide freeways where the number of lanes does not limit the rate of flow), while the times for routes and are variable, based on the number of cars that choose that route.
If the dashed route from does not exist, then the optimal solution is symmetric. Half of the commuters would take the top route, and half the commuters would take the bottom route, resulting in a total travel time of minutes.
Now, imagine that a new road is built between , with a travel time of (to be more realistic, this can be some small and the scenario still works). Of course, our old solution is still feasible, and we can now do even better by having 500 commuters take the path from , resulting in a total travel time of minutes.
However, the commuters who are taking the paths with fixed times could improve their time if they went the route . Thus, if commuters act in their own self-interest, they will all take this route (even if all 4000 commuters go from , it takes 40 minutes versus 45 minutes going from directly to ). The resulting total travel time, however, is , or an increase in 15 minutes per commuter! The astounding thing is that the introduction of more options for the drivers results in a worse solution when individuals are optimizing their own travel time (in the first example, drivers are also optimizing their own travel time; the solution happens to coincide with optimizing total travel time as well). An important takeaway seems to be this characteristic difference between systems where there is one agent optimizing a function over the entire system, versus a system where individual agents optimize their own benefits. In the former, an increase in the “feasible set” of solutions can never weaken the optimal solution, while in the latter, it seems that an increase in the “feasible set” of actions can lead to worse outcomes for everyone when agents are self-interested.
A Real-World Example
While the simple examples of Braess’s paradox seem contrived, it occasionally pops up in the real world. This link is an interesting read on a situation in Manhattan where this paradox actually occurred. By disallowing traffic on 42nd street during Earth Day, traffic congestion in the city actually improved, despite fears of massive congestion. The paradox has also been observed in Seoul, Stuttgart, Boston, and London.
Written by Arjun Mody and Michael Zochowski