direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprint 36-2008

Computing Optimal Network Tolls

Source file is available as :  

Author(s) : Tobias Harks, Guido Schäfer, Martin Sieg

Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 36-2008

MSC 2000

90B20 Traffic problems
90C11 Mixed integer programming

Abstract :
We consider the problem of computing tolls in non-atomic network routing games such that a predetermined flow is realized as Nash flow. It is a well-known fact that marginal cost tolls give rise to a Nash flow that minimizes the total travel time. In this paper, we study the problem of computing such tolls such that an additional toll-dependent objective function is optimized. We consider a broad class of objective functions, including convex and min-max functions, and show that such tolls can be computed in polynomial time. We also consider the problem of computing tolls such that the number of tolled arcs is minimized. We prove that this problem is NP-hard and APX-hard, even for very restricted single-commodity networks, and give first approximation results.

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe