<p>Congestion charging is a now accepted means of influencing traffic to behave in a more socio-economic optimal way, like e.g. in the Stockholm project. Already early work, in the 1920’s, showed that road use can be inefficient due externalities, i.e. that users don’t experience their own (negative) effect on other users: an extra car on a traffic link causes delays for other cars, but the driver himself does not experience this cost.In the 1950’s it was further shown - for a congested road network with homogeneous users – that if each user is charged a toll equal to the total value of time loss incurred on other users of the network, then -if we have fixed travel demand - this will induce an equilibrium that is system optimal in the sense that the total cost of network usage is minimal (assuming that all users have fixed and identical time values).  But toll charges need to be levied in monetary units, and different travelers have different values of time. Therefore, to account for the effects of tolls, and to be able to compute equilibria, one needs to introduce different user classes, differing in their time values.</p><p>In this thesis, consisting of four papers, we study congestion pricing of road networks with users differing only in their time values. In particular, we analyze marginal social cost (MSC) pricing, a tolling scheme that charges each user a penalty corresponding to the value of the delays inflicted on other users, as well as its implementation through fixed tolls.</p><p>Paper III contains the main theoretical work of the thesis. In that paper we show that the variational inequalities characterizing the equilibria in question can be stated in symmetric or non-symmetric forms. The symmetric forms correspond to optimization problems, convex in the fixed-toll case and non-convex in the MSC case, which hence may have multiple equilibria. The objective of the latter problem is the total value of travel time, which thus is minimized at the global optima of that problem. Implementing close-to-optimal MSC tolls as fixed tolls leads to equilibria with possibly non-unique class specific flows, but with identical close-to-optimal values of the total value of travel time. Finally we give an adaptation, to the MSC setting, of the Frank-Wolfe algorithm, which is further applied to some test cases, including Stockholm.</p><p>Paper I is an early application using Frank-Wolfe, after having realized the possibility to symmetrize the problem.</p><p>Paper II gives a convexification of non-convex equilibrium problem for MSC tolls. We have used these convexifications to compute lower bounds when computing equilibria.</p><p>Paper IV is a short note commenting some flaws in two papers by Dial on MSC tolls.</p>

Congestion charging is a now accepted means of influencing traffic to behave in a more socio-economic optimal way, like e.g. in the Stockholm project. Already early work, in the 1920’s, showed that road use can be inefficient due externalities, i.e. that users don’t experience their own (negative) effect on other users: an extra car on a traffic link causes delays for other cars, but the driver himself does not experience this cost.In the 1950’s it was further shown - for a congested road network with homogeneous users – that if each user is charged a toll equal to the total value of time loss incurred on other users of the network, then -if we have fixed travel demand - this will induce an equilibrium that is system optimal in the sense that the total cost of network usage is minimal (assuming that all users have fixed and identical time values).  But toll charges need to be levied in monetary units, and different travelers have different values of time. Therefore, to account for the effects of tolls, and to be able to compute equilibria, one needs to introduce different user classes, differing in their time values. In this thesis, consisting of four papers, we study congestion pricing of road networks with users differing only in their time values. In particular, we analyze marginal social cost (MSC) pricing, a tolling scheme that charges each user a penalty corresponding to the value of the delays inflicted on other users, as well as its implementation through fixed tolls. Paper III contains the main theoretical work of the thesis. In that paper we show that the variational inequalities characterizing the equilibria in question can be stated in symmetric or non-symmetric forms. The symmetric forms correspond to optimization problems, convex in the fixed-toll case and non-convex in the MSC case, which hence may have multiple equilibria. The objective of the latter problem is the total value of travel time, which thus is minimized at the global optima of that problem. Implementing close-to-optimal MSC tolls as fixed tolls leads to equilibria with possibly non-unique class specific flows, but with identical close-to-optimal values of the total value of travel time. Finally we give an adaptation, to the MSC setting, of the Frank-Wolfe algorithm, which is further applied to some test cases, including Stockholm. Paper I is an early application using Frank-Wolfe, after having realized the possibility to symmetrize the problem. Paper II gives a convexification of non-convex equilibrium problem for MSC tolls. We have used these convexifications to compute lower bounds when computing equilibria. Paper IV is a short note commenting some flaws in two papers by Dial on MSC tolls. / <p>QC 20100610</p>