Change search
ReferencesLink to record
Permanent link

Direct link
Convexification of the Traffic Equilibrium Problem with Social Marginal Cost Tolls
Linköpings Universitet.ORCID iD: 0000-0002-4531-8659
KTH, School of Architecture and the Built Environment (ABE), Transport Science, Transport and Location Analysis.
2004 (English)In: Operations Research Proceedings 2003: Selected Papers of the International Conference on Operations Research (OR 2003) Heidelberg, September 3–5, 2003, Springer Berlin/Heidelberg, 2004, 141-148 p.Conference paper (Other academic)
Abstract [en]

In an earlier paper, we have demonstrated that traffic equilibria under social marginal cost tolls can be computedas a local optima of a nonconvex optimization problem. The nonconvexity of this problem implies in particular that linearizations, e.g. the Frank-Wolfe method, do not give underestimates of the optimal value. In this paper we derive the convex hull of nonconvex arc cost functions of BPR type. These convexifications can be used to get underestimates of the optimal value, or get better search directions in the initial phase of the Frank-Wolfe method. Computational results for the Sioux Falls and Stockholm networks are reported.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2004. 141-148 p.
, Operations Research Proceedings, ISSN 0721-5924 ; 2003
National Category
Transport Systems and Logistics
URN: urn:nbn:se:kth:diva-116090DOI: 10.1007/978-3-642-17022-5_19ISBN: Operations Research ProceedingsOAI: diva2:588672
International Conference on Operations Research (OR 2003) Heidelberg, September 3–5, 2003

TSC import 2268 2013-01-15 QC 20130620

Available from: 2013-01-15 Created: 2013-01-15 Last updated: 2013-12-06Bibliographically approved
In thesis
1. Aspects of Static Multi-Class Traffic equilibria under Congestion Pricing
Open this publication in new window or tab >>Aspects of Static Multi-Class Traffic equilibria under Congestion Pricing
2010 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2010. 7 p.
Trita-TEC-LIC, ISSN 1653-445X ; 10-002
traffic, congestion pricing, equilibria, marginal social cost
National Category
Other Civil Engineering
urn:nbn:se:kth:diva-12963 (URN)978-91-85539-54-3 (ISBN)
2010-06-11, E35, Lindstetsv. 3, Stockholm, 09:00 (English)

QC 20100610

Available from: 2010-06-10 Created: 2010-05-20 Last updated: 2013-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Engelson, LeonidLindberg, Per Olov
By organisation
Transport and Location Analysis
Transport Systems and Logistics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 28 hits
ReferencesLink to record
Permanent link

Direct link