Lawphongpanich / Hearn / Smith Mathematical and Computational Models for Congestion Charging

1. Auflage 2006
ISBN: 978-0-387-29645-6
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 101, 240 Seiten

Reihe: Applied Optimization

Rigorous treatments of issues related to congestion pricing are described in this book. It examines recent advances in areas such as mathematical and computational models for predicting traffic congestion, determining when, where, and how much to levy tolls, and analyzing the impact on transportation systems. The book follows recent schemes judged to be successful in London, Singapore, Norway, as well as a number of projects in the United States.

Autoren/Hrsg.

Lawphongpanich, Siriphong

Hearn, Donald W.

Smith, Michael J.

Inhaltsverzeichnis

1;Contents;6
2;Preface;8
3;List of Contributors;10
4;Improving Traffic Flows at No Cost;12
4.1;1 Introduction;12
4.2;2 Notation and Definition of the Equilibrium Problem;14
4.3;3 The Existence of Improved Flows;17
4.4;4 A Computational Approach for Local Improvements;19
4.5;5 Computational Results;21
4.6;6 Conclusions;25
4.7;References;26
4.8;Appendix;28
5;Relaxed Toll Sets for Congestion Pricing Problems;34
5.1;1 Introduction;34
5.2;2 System and Non-System Toll Sets;35
5.3;3 Relaxed Toll Set;40
5.4;4 Disaggregate Representation of Relaxed Toll Sets;44
5.5;5 Numerical Results;46
5.6;6 Conclusions;48
5.7;References;48
5.8;Appendix;50
6;Dynamic Pricing: A Learning Approach;56
6.1;1 Introduction;56
6.2;2 A Learning Approach for Dynamic Pricing, Part I: Without Competition;61
6.3;3 A Learning Approach for Dynamic Pricing, Part 11: With Competition;74
6.4;4 Conclusions;85
6.5;References;85
6.6;Appendix;89
7;Congestion Pricing of Road Networks with Users Having Different Time Values;91
7.1;1 Introduction;91
7.2;2 User equilibria in networks with several user classes;94
7.3;3 Fixed-Toll Multi-Class Equilibria with Class Specific Time Values;97
7.4;4 Tolls based on marginal social costs;101
7.5;5 Nonconvexity of V;105
7.6;6 A Frank-Wolfe algorithm for the multi-class MSC equilibria;109
7.7;7 Some experimental results;109
7.8;8 Concluding remarks;112
7.9;References;113
8;Network Equilibrium Models for Analyzing Toll Highways;115
8.1;1 Introduction;115
8.2;2 Notation and Definitions;116
8.3;3 Models Based on Generalized Cost Path Choice;117
8.4;4 Models Based on Explicit Choice of Tolled Facilities;118
8.5;5 A Small Numerical Example;122
8.6;6 Some Large-Scale Applications;123
8.7;7 CONCLUSIONS;124
8.8;References;124
9;On the Applicability of Sensitivity Analysis Formulas for Traffic Equilibrium Models;126
9.1;1 Introduction;127
9.2;2 The Traffic Model;128
9.3;3 The basis for our sensitivity analysis;130
9.4;4 Sensitivity analysis of separable traffic equilibria;133
9.5;5 An illustrative example;136
9.6;6 A sensitivity analysis tool;139
9.7;7 A dissection of the sensitivity analysis of Tobin and Friesz;141
10;Park and Ride for the Day Period and Morning-Evening Commute;151
10.1;1 Introduction;151
10.2;2 Notations and generalities;154
10.3;3 Park and ride models;157
10.4;4 Pricing policy;160
10.5;5 Simple illustration of the model;161
10.6;6 Discussion and concluding remarks;163
10.7;References;164
11;Bilevel Optimisation of Prices and Signals in Transportation Models;166
11.1;1 Introduction;166
11.2;2 The Model;169
11.3;3 Variable Demand Equilibrium;170
11.4;4 An Equilibration Method;175
11.5;5 Dynamic Armijo-Like Step Lengths;177
11.6;6 Convergence to Equilibrium;179
11.7;7 Optimising Prices;180
11.8;8 Convergence to a Stationary Point;187
11.9;9 Allowing for the Boundary of H;189
11.10;10 Convergence to a Stationary Point in H;195
11.11;11 Optimisation in the Payne-Thompson Model;196
11.12;12 Conclusion;198
11.13;References;199
11.14;Appendix;203
12;Minimal Revenue Network Tolling: System Optimisation under Stochastic Assignment.;207
12.1;1 Introduction;207
12.2;2 Stochastic Assignment Models;210
12.3;3 System Optimal Road Tolls;212
12.4;4 Stochastic Social Optimum Road Tolls;219
12.5;6 Future Work;221
12.6;References;222
12.7;Appendix;224
13;An Optimal Toll Design Problem with Improved Behavioural Equilibrium Model: The Case of the Probit Model;225
13.1;1 Introduction;225
13.2;2 Problem Formulation of Optimal Toll Design with Stochastic User Equilibrium;227
13.3;3 Probit Equilibrium with Variable Demand: Formulation and Solution Algorithm;229
13.4;4 Implicit Programming Approach to Optimal Toll Design;231
13.5;5 Numerical Experiments;232
13.6;6 Conclusions;242
13.7;References;243
13.8;Appendix;246

Leseproben

Relaxed Toll Sets for Congestion Pricing Problems (p. 23-24)

Lihui Bail, Donald W. Hearn and Siriphong Lawphongpanich3
College of Business Administration, Valparaiso University, Valparaiso, IN 46383,
U.S.A., Lihui BaiQvalpo. edu
Industrial and Systems Engineering Department, University of Florida,
Gainesville, FL 32611, U.S.A., Industrial and Systems Engineering Department, University of Florida,
Gainesville, FL 32611, U.S.A.,
Summary. Congestion or toll pricing problems in [HeR98] require a solution to the system problem (the traffic assignment problem that minimizes the total travel delay) to define the set of all valid tolls or the toll set. For practical problems, it may not be possible to obtain an exact solution to the system problem and the inaccuracy in an approximate system solution may render the toll set empty. When this occurs, this paper offers alternative toll sets based on relaxed optimality conditions. With carefully chosen parameters, tolls from the relaxed toll sets are shown theoretically and empirically (using four transportation networks in the literature) to induce route choices that are nearly system optimal.

Key words: Congestion Pricing, Traffic Equilibrium, Perturbation Analysis

1 Introduction

To encourage each traveller to choose a route in a transportation network that would collectively benefit all travellers, Hearn and Ramana [HeR98] proposed in 1998 a framework for determining the prices and locations a t which to toll the network. This framework requires solving a congestion or toll pricing problem, an optimization problem with linear constraints that describe the set of all valid tolls or the toll set. Coefficients for the constraints depend on an optimal solution to the system problem, i.e., the traffic assignment problem (see, e.g., Florian and Hearn, [FlH95]) that minimizes the total travel delay among all travellers.

For small transportation networks, it is possible to compute an exact op- timal solution to the system problem. However, obtaining such a solution for larger networks may be either impossible or impractical. When implemented on computers, algorithms for the system problem must perform all numerical computations using finite precision. This naturally induces small numerical inaccuracies because to perform some mathematical operations precisely requires infinite precision. Furthermore, the system problem is generally a non- linear program for which most algorithms require in theory an infinite number of iterations to reach an exact optimal solution. In practice, it is common to terminate these algorithms when they find a solution with a small optimality gap, e.g., 10E-4.

On the other hand, using an approximate solution for the system problem (or an approximate system solution) to determine the coefficients for the constraints defining the toll set may cause the toll pricing problem to become infeasible, numerically (e.g., because of finite precision) or otherwise. To over- come this infeasibility, Hearn and Ramana [HeR98] employ a penalty function approach and Hearn et al. [HYROl] relax one of the constraints defining the toll set. For the latter, the relaxation is based on a parameter defined by an optimal solution to the penalty problem in [HeR98].

This paper studies the viability of using an approximate system solution in defining the toll set. Specifically, when an approximate system solution makes the toll set empty, this paper alleviates this inconsistency by relaxing one or more constraints, some of which are similar to those used in [HYROl]. How- ever, our approach to relaxation does not require solving a penalty problem. Moreover, this paper also addresses three issues relating to the use of an ap- proximate system solution. The first issue is whether an approximate system solution yields a consistent set of constraints defining the toll set. When it does not, the second issue is to find practical methods for relaxing the constraints in order to generate tolls that causes travellers to use the transportation net- work in nearly the most efficient manner. Finally, the last issue is to ascertain how well these methods work theoretically and empirically.

The remainder of the paper assumes that the travel demands are fixed. Results for the elastic demand case are similar and given in the Appendix. Section 2 defines two types of toll sets, system and non-system, and discusses their properties. Section 3 derives a relaxed toll set using an approximate system solution and shows that the tolls from this set have the desirable property. Section 4 gives an alternate representation of the relaxed toll set. Section 5 reports encouraging results for four transportation networks from the literature and Section 6 concludes the paper.