Minimal-revenue congestion pricing part I: A fast algorithm for the single-origin case

This paper derives a simple fast algorithm for computing minimal-revenue tolls in a single-origin network. It assumes that trips have the same value of time, that they make user-optimizing path choices, and they have multiple destinations-but come from the same origin. The algorithm finds tolls that induce a traffic pattern minimizing average time per trip at a minimal average toll per trip. Formally, let X be the set of all feasible traffic assignments and assume all trips have the same value of time alpha > 0; then the algorithm inputs a network with the system-optimizing flow x(o) vector and associated are times t(x(o)). It outputs an optimal are toll vector c*greater than or equal to 0 such that for x is an element of X: (alpha t(x(o)) + c*)(T)(x - x(o))greater than or equal to 0 for x is an element of X(user optimal) (1) alpha t(x(o))(T)x(o) = min(x is an element of X)alpha t(x)(T)x(system optimal) (2) c*(T) x(o) = min(c greater than or equal to 0)c(T)x(o)(revenue minimal). (3) That is, x(o)is an element of X becomes user-optimal, too. Compared to marginal-cost tolls, which would also produce this same effect, the min-revenue tolls c* possess important practical advantages. Perforce, they provide the same system-optimal network usage, but at a much cheaper price to the traveler-remarkably, they assure at least one toll-free path to every destination. In addition, min-revenue tolls have admirable stability: even large increases in travel demand can leave the solution c* virtually unchanged-an important feature since traffic volume can change continuously but tolls cannot. Finally, they provide guidance regarding potential network improvements. The algorithm presented is very efficient, easily able to solve networks with tens of thousands of nodes. A greedy potentials calculator, its expected running time for an n-node road network is a speedy O(n), while its worst case time for any network is O(m), where m is the number of arcs. (C) 1999 Elsevier Science Ltd. All rights reserved.