Mathematical and Computational Models for Congestion Charging (eBook)

Contents 6
Preface 8
List of Contributors 10
Improving Traffic Flows at No Cost 12
1 Introduction 12
2 Notation and Definition of the Equilibrium Problem 14
3 The Existence of Improved Flows 17
4 A Computational Approach for Local Improvements 19
5 Computational Results 21
6 Conclusions 25
References 26
Appendix 28
Relaxed Toll Sets for Congestion Pricing Problems 34
1 Introduction 34
2 System and Non-System Toll Sets 35
3 Relaxed Toll Set 40
4 Disaggregate Representation of Relaxed Toll Sets 44
5 Numerical Results 46
6 Conclusions 48
References 48
Appendix 50
Dynamic Pricing: A Learning Approach 56
1 Introduction 56
2 A Learning Approach for Dynamic Pricing, Part I: Without Competition 61
3 A Learning Approach for Dynamic Pricing, Part 11: With Competition 74
4 Conclusions 85
References 85
Appendix 89
Congestion Pricing of Road Networks with Users Having Different Time Values 91
1 Introduction 91
2 User equilibria in networks with several user classes 94
3 Fixed-Toll Multi-Class Equilibria with Class Specific Time Values 97
4 Tolls based on marginal social costs 101
5 Nonconvexity of V 105
6 A Frank-Wolfe algorithm for the multi-class MSC equilibria 109
7 Some experimental results 109
8 Concluding remarks 112
References 113
Network Equilibrium Models for Analyzing Toll Highways 115
1 Introduction 115
2 Notation and Definitions 116
3 Models Based on Generalized Cost Path Choice 117
4 Models Based on Explicit Choice of Tolled Facilities 118
5 A Small Numerical Example 122
6 Some Large-Scale Applications 123
7 CONCLUSIONS 124
References 124
On the Applicability of Sensitivity Analysis Formulas for Traffic Equilibrium Models 126
1 Introduction 127
2 The Traffic Model 128
3 The basis for our sensitivity analysis 130
4 Sensitivity analysis of separable traffic equilibria 133
5 An illustrative example 136
6 A sensitivity analysis tool 139
7 A dissection of the sensitivity analysis of Tobin and Friesz 141
Park and Ride for the Day Period and Morning-Evening Commute 151
1 Introduction 151
2 Notations and generalities 154
3 Park and ride models 157
4 Pricing policy 160
5 Simple illustration of the model 161
6 Discussion and concluding remarks 163
References 164
Bilevel Optimisation of Prices and Signals in Transportation Models 166
1 Introduction 166
2 The Model 169
3 Variable Demand Equilibrium 170
4 An Equilibration Method 175
5 Dynamic Armijo-Like Step Lengths 177
6 Convergence to Equilibrium 179
7 Optimising Prices 180
8 Convergence to a Stationary Point 187
9 Allowing for the Boundary of H 189
10 Convergence to a Stationary Point in H 195
11 Optimisation in the Payne-Thompson Model 196
12 Conclusion 198
References 199
Appendix 203
Minimal Revenue Network Tolling: System Optimisation under Stochastic Assignment. 207
1 Introduction 207
2 Stochastic Assignment Models 210
3 System Optimal Road Tolls 212
4 Stochastic Social Optimum Road Tolls 219
6 Future Work 221
References 222
Appendix 224
An Optimal Toll Design Problem with Improved Behavioural Equilibrium Model: The Case of the Probit Model 225
1 Introduction 225
2 Problem Formulation of Optimal Toll Design with Stochastic User Equilibrium 227
3 Probit Equilibrium with Variable Demand: Formulation and Solution Algorithm 229
4 Implicit Programming Approach to Optimal Toll Design 231
5 Numerical Experiments 232
6 Conclusions 242
References 243
Appendix 246

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.