Optimal Intervention in Traffic Networks

We present an efficient algorithm to identify which edge should be improved in a traffic network to minimize the total travel time. Our main result is to show that it is possible to approximate the variation of total travel time obtained by changing the congestion coefficient of any given edge, by performing only local computations, without the need of recomputing the entire equilibrium flow. To obtain such a result, we reformulate our problem in terms of the effective resistance between two adjacent nodes and suggest a new approach to approximate such effective resistance. We then study the optimality of the proposed procedure for recurrent networks, and provide simulations over synthetic and real transportation networks.