Traffic Optimization

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 G = (V, E) whereby V are the set of nodes and E are the set of roads that connect nodes. Further, denote V_{endpoint} as the start and end nodes of the vertex, and V_{internal} as all other nodes in the system. Let t_{i,j} be the decision variables in the system: how many travelers use route i\rightarrow j. Let N be the total number of commuters in the system. Let x_{i,j} be the “fixed travel time” associated with each road, and let y_{i,j} 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:

\min \quad \sum_E x_{i,j}t_{i,j} + \sum_E t_{i,j}^2y_{i,j}
\text{subject to} \quad \sum_{i\in Nbrs(j)} t_{i,j} = \sum_{k\in Nbrs(j)} t_{j,k}\quad\forall j\in V_{internal}
\sum_{i\in Nbrs(start)} t_{start, i} = T
\sum_{i\in Nbrs(end)} t_{i, end} = T
t_{i,j} \geq 0\quad\forall (i,j)\in E

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!

Braess’s Paradox

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 A\rightarrow C and routes B\rightarrow D 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 A\rightarrow B and C\rightarrow D are variable, based on the number of cars that choose that route.

braess

If the dashed route from B\rightarrow C 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 T = 4000\Big(\frac{2000}{100} + 45\Big) = 260,000 minutes.

Now, imagine that a new road is built between B\rightarrow C, with a travel time of 0 (to be more realistic, this can be some small \varepsilon > 0 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 B\rightarrow C, resulting in a total travel time of T = 2\Big(2250\cdot\frac{2250}{100} + 1750\cdot 45\Big) = 258,750 minutes.

However, the commuters who are taking the paths with fixed times could improve their time if they went the route A\rightarrow B\rightarrow C\rightarrow D. Thus, if commuters act in their own self-interest, they will all take this route (even if all 4000 commuters go from A\rightarrow B\rightarrow C, it takes 40 minutes versus 45 minutes going from A directly to C). The resulting total travel time, however, is T = 4000\Big(2\cdot\frac{4000}{100}\Big) = 320,000, 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.

Citations

http://homepage.rub.de/Dietrich.Braess/Paradox-BNW.pdf
http://tigger.uic.edu/~hagstrom/Research/Braess/index.html
http://en.wikipedia.org/wiki/Braess’s_paradox
http://www.nytimes.com/1990/12/25/health/what-if-they-closed-42d-street-and-nobody-noticed.html

Written by Arjun Mody and Michael Zochowski

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s