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

Robert B. Dial

Transportation Research Part B: Methodological, 1999, vol. 33, issue 3, 189-202

Abstract: 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 xo vector and associated arc times t(xo). It outputs an optimal arc toll vector c*[greater-or-equal, slanted]0 such that for x[set membership, variant]X:([alpha]t(xo)+c*)T(x-xo)[greater-or-equal, slanted]0  for x[set membership, variant]X (user  optimal) That is, xo[set membership, variant]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.

Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(98)00026-5
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:33:y:1999:i:3:p:189-202

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().