Abstract We consider a network pricing game on a parallel network with congestion effects in which link owners set tolls for travel so as to maximize profit. A central authority is able to regulate this competition by means of a (uniform) price cap. The first question we want to answer is how such a cap should be designed in order to minimize the total congestion. We provide an algorithm that finds an optimal price cap for networks with affine latency functions and a full support Wardrop equilibrium. Second, we consider the induced network performance at an optimal price cap. We show that for two link networks with affine latency functions, the congestion costs at the optimal price cap are at most 8 7 times the optimal congestion costs. For more general latency functions, this bound goes up to 2 under the assumption that an uncapped Nash equilibrium exists. However, in general such an equilibrium need not exist and this can be used to show that optimal price caps can induce arbitrarily inefficient flows.
Instead of improving efficiency, tolls can also be used to minimize or maximize the profit of one or multiple leaders. The model that computes tolls that induce the optimal flow at minimal profit was analyzed by Dial @cite_41 @cite_13 . The model with one profit maximizing leader and no congestion effects, was first analyzed by Labb ' e et al @cite_43 and later by @cite_20 .
@cite_41 @cite_43 @cite_13 @cite_20
2048523876 1974835443 2111240209 2035893651
The second of a two-part series, this paper derives an efficient solution to the minimal-revenue tolls problem. As introduced in Part I, this problem can be defined as follows: Assuming each trip uses only a path whose generalized cost is smallest, find a set of arc tolls that simultaneously minimizes both average travel time and out-of-pocket cost. As a point of departure, this paper first re-solves the single-origin problem of Part I, modeling it as a linear program. Then with a change of variable, it transforms the LP's dual into a simple longest-path problem on an acyclic network. The multiple-origin problem - where one toll for each arc applies to all origins - solves analogously. In this case, however, the dual becomes an elementary linear multi-commodity max-cost flow problem with an easy bundling constraint and infinite arc capacities. After a minor reformulation that simplifies the model's input to better accommodate output from common traffic assignment software, a solution algorithm is exemplified with a numerical example. 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. We consider a bilevel model where the leader wants to maximize revenues from a taxation scheme, while the follower rationally reacts to those tax levels. We focus our attention on the special case of a toll-setting problem defined on a multicommodity transportation network. We show that the general problem is NP-complete, while particular instances are polynomially solvable. Numerical examples are given. We consider the problem of determining a set of optimal tolls on the arcs of a multicommodity transportation network. The problem is formulated as a bilevel mathematical program where the upper level consists in a firm that raises revenues from tolls set on arcs of the network, while the lower level is represented by a group of users travelling on shortest paths with respect to a generalized travel cost.