New toll setting methods improve revenue in traffic networks
Single-level reformulations for network pricing under Wardrop equilibrium with separable affine costs
Computer Science and Game Theory
Summary
Setting tolls on roads to maximize revenue is tricky because drivers choose routes to minimize their own travel times, leading to a network-wide balance called Wardrop equilibrium. The authors study this problem assuming simple, linear travel time costs on roads. They develop new mathematical ways to rewrite the problem into single-level forms that are easier to solve exactly or approximately. Their methods work better than prior ones, especially on large networks, and can provide good solutions quickly even when exact methods struggle.
What this means in practice
- •For transportation planners: Optimize toll placement and pricing on road networks to increase revenue while anticipating drivers' route choices under traffic equilibrium.
- •For urban traffic engineers: Use efficient computational methods to quickly estimate near-optimal tolls in large urban road networks to manage congestion and revenues.
Authors
Miguel F. Anjos, José Neto
Abstract
We consider the problem of setting tolls on a subset of the arcs of a congested network so as to maximize the revenue of a network authority, anticipating that users route according to a Wardrop equilibrium. This problem is naturally cast as a bilevel program in which the leader sets tolls while the followers respond by choosing an equilibrium routing. We focus on the important special case of separable affine arc cost functions. Under this assumption, Wardrop equilibria admit Beckmann's convex characterization, from which we derive three new single-level reformulations of the bilevel problem, exploiting both Beckmann's formulation and its dual: an arc-based formulation, which we solve exactly, and two path-based formulations, solved by column-and-constraint generation. Beyond the reformulations, we further derive from Beckmann's potential an upper bound on the optimal revenue that can be used to certify optimality gaps across all formulations. An extensive computational study on instances derived from the Sioux Falls and Eastern Massachusetts networks compares our formulations with the recent mixed-integer nonlinear formulation of Beck, Labbé and Schmidt. The arc-based formulation solves substantially more instances to proven optimality (within a time limit of 1800 s) than this formulation and, unlike it, returns a feasible solution on every instance. It remains effective on the largest, 74-node network, on which the formulation of Beck et al. solves none. The magnitude of the upper bounds on the tolls proves to be a major driver of tractability: the genuinely hard core of the benchmark emerges once the regulatory cap on tolls is removed. The two path-based formulations, used as heuristics, return a solution within one percent of the optimum on every instance whose optimal value is known, often in seconds where exact formulations reach the time limit.