Computing Network Tolls with Support Constraints

Tobias Harks, Ingo Kleinert, Max Klimm, and Rolf H. Möhring

not available

constrained network tolls, Wardrop equilibria, inefficiency

Reducing traffic congestion via toll pricing has been a central topic in the operations re- search and transportation literature and, recently, it has been implemented in several cities all over the world. Since in practice it is not feasible to impose tolls on every edge of a given traffic network, we study the resulting mathematical problem of computing tolls on a pre- defined subset of edges of the network so as to minimize the total travel time of the induced equilibrium flow. We first present an analytical study for the special case of parallel edge networks highlighting the intrinsic complexity and non-convexity of the resulting optimiza- tion problem. We also present algorithms for general networks for which we systematically test the solution quality for large-scale network instances. Finally the related optimization problem of computing tolls subject to a cardinality constraint on the number of edges that have tolls is discussed.

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de