Computing network tolls with support constraints
Authors:
Abstract
Reducing traffic congestion via toll pricing has been a central topic in the operations research 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 predefined 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 nonconvexity of the resulting optimization problem. We then present algorithms for general networks for which we systematically test the solution quality for large‐scale network instances. Finally, we discuss the related optimization problem of computing tolls subject to a cardinality constraint on the number of edges that have tolls. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(3), 262–285 2015Keywords
Funding Information
- the Federal Ministry of Education and Research (03MOPAI1.)
- The Deutsche Forschungsgemeinschaft within the research training group ‘Methods for Discrete Structures' (GRK 1408.)
This publication has 25 references indexed in Scilit:
- Decomposition techniques for the minimum toll revenue problemNetworks, 2004
- The multi-class, multi-criteria traffic network equilibrium and systems optimum problemTransportation Research Part B: Methodological, 2004
- Second-best congestion pricing in general networks. Heuristic algorithms for finding second-best optimal toll levels and toll pointsTransportation Research Part B: Methodological, 2002
- How bad is selfish routing?Journal of the ACM, 2002
- Side constrained traffic equilibrium models— analysis, computation and applicationsTransportation Research Part B: Methodological, 1999
- Minimal-revenue congestion pricing part I: A fast algorithm for the single-origin caseTransportation Research Part B: Methodological, 1999
- The marginal cost taxation of a transportation networkTransportation Research Part B: Methodological, 1979
- An algorithm for quadratic programmingNaval Research Logistics Quarterly, 1956
- The Economics of Welfare.The Economic Journal, 1933
- Some Fallacies in the Interpretation of Social CostThe Quarterly Journal of Economics, 1924