Intuitively, it seems that a larger number of alternative routes in a traffic network would reduce traffic congestion. This PRL paper, though, suggests that the removal of some roads would actually reduce congestion. This comes about because the presence of these roads can create a game-theoretic situation in which the Nash equilibrium is less optimal than the socially optimal solution. When the choice of using these roads is removed, so is that Nash equilibrium, and road users end up in a more socially optimal state.
A toy example illustrates how the Nash equilibrium is easily an undesirable outcome. Suppose two points are connected by a short but narrow bridge and a long but broad freeway. The narrowness of the former means that the delay on it is proportional to the flow, while the delay on the freeway is flow independent. For a fixed number of users, the social optimum would be obtained by a mix of users on the bridge and on the freeway — even though the delay on the freeway is higher for the individual user, because fewer users on the bridge reduce the delays on the bridge for others, the total social cost is minimized if some people ’sacrifice’ their time to use the freeway. (See the paper for the exact parameters of their equations.) However, the Nash equilibrium, in which all individuals choose the option that minimises their own marginal costs, is one where all users take the bridge.
That example simply illustrates how the Nash equilibrium can deviate from the socially optimal solution. For such a simple example, it is clear that removing the bridge, and leaving only the freeway as an option, isn’t going to improve things. But in a more complex network of roads, it is possible that removing a road might shift the Nash equilibrium in such a way that it is closer to the socially optimal solution. The authors studied the road networks of Boston, London and New York City to find such scenarios. For Boston, they considered journeys from Harvard Square to Boston Common. They then plotted the ratio of the cost of the Nash equilibrium to the cost of the social optimum (they called this the POA — price of anarchy), for varying rates of vehicular flow. Except for very small flow rates, this ratio was always above one — the Nash equilibrium is almost always more costly than the social optimum:
POA is the ratio of the cost of the Nash equilibrium to the cost of the social optimum. Note that it is more than one for almost all values of the flow.
After obtaining the initial POA versus flow graphs, they then experimented with eliminating certain roads from the networks. Most roads increased the POA when cut, but 6 out of the 246 roads in the Boston network actually reduced the POA when cut. Similar results were obtained with the networks of London and NYC. So it seems that as a general rule of thumb, removing roads does increase delays, but there are certain roads for which the reverse is true. (One wonders if these roads have anything in common.)
One severe limitation of these results is that they were obtained by considering only travel from one origin to one destination. The authors claim that they remain robust for several origin/destination combinations, but it is nevertheless the case that for any one simulation, the costs are calculated by assuming that all drivers are going from a common origin to a common destination. In a real city, other directions of travel have to be thrown into the mix, and it’s not clear that similar effects will necessarily be found then.
Cute results, but why did this paper appear in PRL? At the end, the authors suggest possible applications to systems like electrical circuits, which have to satisfy Kirchoff’s Laws but do not necessarily minimise the dissipated energy in the process. They point to a couple of papers which show that removing wires can increase the conductance of a circuit.
References:
Cohen, J. E. and P. Horowitz (1991). Paradoxical behaviour of mechanical and electrical networks. Nature 352 (6337), 699-701.
Penchina, C. M. and L. J. Penchina (2003). The braess paradox in mechanical, traffic, and other networks. American Journal of Physics 71 (5), 479-482.
Youn, H., M. T. Gastner, and H. Jeong (2008). Price of anarchy in transportation networks: Efficiency and optimality control. Physical Review Letters 101 (12).
Filed under: mathematics, physics | Leave a Comment
Tags: networks, simulation, traffic
No Responses Yet to “Blocking streets to reduce congestion delays”