liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimization Approaches for Design of Congestion Pricing Schemes
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology. (Trafiksystem)ORCID iD: 0000-0002-1367-6793
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In recent years, there has been a growing interest in congestion pricing as a tool for solving traffic congestion problems in urban areas. However, the transportation system is complex and to design a congestion pricing scheme, i.e. to decide where and how much to charge the road users, is not trivial. This thesis considers congestion pricing schemes based on road tolls, and the efficiency of a pricing scheme is evaluated by a social welfare measure. To assist in the process of designing congestion pricing schemes, the toll design problem (TDP) is formulated as an optimization problem with the objective function describing the change in social welfare. In the TDP, the road users are assumed to be distributed in the traffic network according to a Wardrop equilibrium. The TDP is a non-convex optimization problem, and its objective function is non-smooth. Thus, the TDP is considered as a hard optimization problem to solve.

This thesis aims to develop methods capable of optimizing both toll locations and their corresponding toll levels for real world traffic networks; methods which can be used in a decision support framework when designing new congestion pricing schemes or tuning already implemented ones. Also, this thesis addresses the global optimality of the TDP. '

In this thesis, a smoothening technique is applied which approximates the discrete toll location variables by continuous functions (Paper I). This allows for simultaneous optimization of both toll locations and their corresponding toll levels, using a sensitivity analysis based ascent algorithm. The smoothening technique is applied in a Stockholm case study (Paper II), which shows the potential of using optimization when designing congestion pricing schemes.

Global optimality of the TDP is addressed by piecewise linear approximations of the non-linear functions in the TDP (Papers III and IV), resulting in a mixed integer linear program (MILP). The MILP can be solved to global optimality by branch and bound/cut methods which are implemented in commercially available software.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2012. , 48 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1443
National Category
Transport Systems and Logistics
Identifiers
URN: urn:nbn:se:liu:diva-76287ISBN: 978-91-7519-903-0 (print)OAI: oai:DiVA.org:liu-76287DiVA: diva2:514129
Public defence
2012-05-09, K3, Kåkenhus, Campus Norrköping, Linköpings universitet, Norrköping, 10:00 (English)
Opponent
Supervisors
Available from: 2012-04-13 Created: 2012-04-02 Last updated: 2013-09-12Bibliographically approved
List of papers
1. Heuristic algorithms for a second-best congestion pricing problem
Open this publication in new window or tab >>Heuristic algorithms for a second-best congestion pricing problem
2009 (English)In: Netnomics, ISSN 1385-9587, E-ISSN 1573-7071, Vol. 10, no 1, 85-102 p.Article in journal (Refereed) Published
Abstract [en]

Designing a congestion pricing scheme involves a number of complex decisions.Focusing on the quantitative parts of a congestion pricing system with link tolls, the problem involves findingthe number of toll links, the link toll locations and their corresponding toll level and schedule.In this paper, we develop and evaluate methods for finding the most efficient design for a congestion pricing scheme in a road network model with elastic demand. The design efficiency is measured by the net social surplus, which is computed as the difference between the social surplus and the collection costs (i.e. setup and operational costs) of the congestion pricing system. The problem of finding such a scheme is stated as a combinatorial bi-level optimization problem. At the upper level, we maximize the net social surplus and at the lower level we solve a user equilibrium problem with elastic demand, given the toll locations and toll levels,to simulate the user response. We modify a known heuristic procedure for finding the optimal locations and toll levels given a fixed number of tolls to locate, to find the optimal number of toll facilities as well. A new heuristic procedure, based on repeated solutions of a continuous approximation of the combinatorial problem is also presented. Numerical results for two small test networks are presented. Both methods perform satisfactorily on the two networks. Comparing the two methods, we find that the continuous approximation procedure is the one which shows the best results.

Keyword
transport modeling, congestion pricing, network design, bi-level optimization, toll locations, traffic assignment, user equilibrium, collection cost
National Category
Other Engineering and Technologies not elsewhere specified
Identifiers
urn:nbn:se:liu:diva-18641 (URN)10.1007/s11066-008-9019-9 (DOI)
Available from: 2009-06-03 Created: 2009-06-03 Last updated: 2017-12-13Bibliographically approved
2. Optimal Toll Locations and Levels in Congestion Pricing Schemes: a Case Study of Stockholm
Open this publication in new window or tab >>Optimal Toll Locations and Levels in Congestion Pricing Schemes: a Case Study of Stockholm
2014 (English)In: Transportation planning and technology (Print), ISSN 0308-1060, E-ISSN 1029-0354, Vol. 37, no 4, 333-353 p.Article in journal (Refereed) Published
Abstract [en]

As congestion pricing has moved from theoretical ideas in the literature to real world implementations, the need for decision support when designing the pricing schemes has become evident. This paper deals with the problem of finding optimal toll levels and locations in a road traffic network, and presents a case study of Stockholm. The optimization problem of finding optimal toll levels, given a predetermined cordon, and the problem of finding both optimal toll locations and levels are presented, and previously developed heuristics are used for solving these problems. For the Stockholm case study, the possible welfare gains of optimizing the toll levels in the current cordon, and optimizing both the toll locations and their corresponding toll levels are evaluated. It is shownthat by tuning the toll levels in the current congestion pricing cordon used in Stockholm, the welfare gain can be significantly increased, and furthermore improved by allowing a toll on the bypass highway “Essingeleden”. It is also shown that by optimizing both the toll locations and levels, a congestion pricing scheme with welfare gain close to what can be achieved by marginal social cost pricing, can be designed with tolls being located on only a forth of the tollable links.

Place, publisher, year, edition, pages
Routledge, 2014
Keyword
congestion pricing; road tolls; bilevel optimisation; user equilibrium; network design; Stockholm
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-76640 (URN)10.1080/03081060.2014.897129 (DOI)000334158100002 ()
Note

On the day of the defence date of the Thesis the status of this article was Manuscript.

Available from: 2012-04-13 Created: 2012-04-13 Last updated: 2017-12-07Bibliographically approved
3. Optimizing Toll Locations and Levels Using a Mixed Integer Linear Approximation Approach
Open this publication in new window or tab >>Optimizing Toll Locations and Levels Using a Mixed Integer Linear Approximation Approach
2012 (English)In: Transportation Research Part B: Methodological, ISSN 0191-2615, E-ISSN 1879-2367, Vol. 46, no 7, 834-854 p.Article in journal (Refereed) Published
Abstract [en]

This paper addresses the toll design problem of finding the toll locations and levels in a congestion pricing scheme, which minimize the total travel time and the toll-point cost (set-up and operational costs of the toll collecting facilities). Road users in the network are assumed to be distributed according to the principle of user equilibrium, with the demand assumed to be fixed and given a priori. The toll design problem is commonly formulated as a nonlinear program, which in general is non-convex and non-smooth, and thus difficult to solve for a global optimum. In this paper, the toll design problem is approximated by a mixed integer linear program (MILP), which can be solved to its globally optimal solution. The MILP also gives a lower bound estimation of the original non-linear problem, and the accuracy of the approximation is improved by iteratively updating the MILP. To demonstrate the approach, we apply the algorithm to two networks: a smaller network with 18 links and 4 OD-pairs to illustrate the properties of the approach, and the Sioux Falls network with 87 links and 30 OD-pairs to demonstrate the applicability of the approach.

Place, publisher, year, edition, pages
Elsevier, 2012
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-76641 (URN)10.1016/j.trb.2012.02.006 (DOI)000305435600004 ()
Available from: 2012-04-13 Created: 2012-04-13 Last updated: 2017-12-07Bibliographically approved
4. Solving a Mixed Integer Linear Program Approximation of the Toll Design Problem Using Constraint Generation within a Branch and Cut Algorithm
Open this publication in new window or tab >>Solving a Mixed Integer Linear Program Approximation of the Toll Design Problem Using Constraint Generation within a Branch and Cut Algorithm
2014 (English)In: Transportmetrica A: Transport Science, ISSN 2324-9935, Vol. 10, no 9, 791-819 p.Article in journal (Refereed) Published
Abstract [en]

This paper addresses the global optimality of the toll design problem (TDP) by a mixed integer linear program (MILP) approximation. In the TDP, the objective is to maximize the social surplus by adjusting toll locations and levels in a road traffic network. The resulting optimization problem can be formulated as a mathematical program with equilibrium constraints (MPEC).

A MILP is obtained by piecewise linear approximation of the non-linear functions in the TDP, and we present a domain reduction scheme to reduce the error introduced by these approximations. Previous approaches for solving the MILP approximation have been relying on a large number of MILPs to be solved iteratively within a cutting constraint algorithm (CCA). This paper instead focuses on the development of a solution algorithm for solving the MILP approximation in which the CCA is integrated within a branch and cut algorithm, which only requires one MILP to be solved.

Place, publisher, year, edition, pages
Taylor & Francis Group, 2014
Keyword
global optimisation; bilevel optimisation; toll design; road pricing
National Category
Civil Engineering
Identifiers
urn:nbn:se:liu:diva-76642 (URN)10.1080/23249935.2013.813988 (DOI)000340257500002 ()
Note

The original titel in manuscript form was Solving a MILP Approximation of the Toll Design Problem Using Constraint Generation within a Branch and Cut Algorithm.

Available from: 2012-04-13 Created: 2012-04-13 Last updated: 2014-10-23

Open Access in DiVA

Optimization Approaches for Design of Congestion Pricing Schemes(419 kB)1356 downloads
File information
File name FULLTEXT01.pdfFile size 419 kBChecksum SHA-512
29fe07886654d767f653c77c1ab54185da6bd859e001fdf012dd5c4bc1cc9c0f914c3a111176e24c7840a6c4dbaeb274a3744f0fbb6010cc2c2e2465bba056e9
Type fulltextMimetype application/pdf
omslag(153 kB)89 downloads
File information
File name COVER01.pdfFile size 153 kBChecksum SHA-512
27e3d55ac7241c4a18533ea3e33a005ec3db181679e3af870850636f3e4c529e9c931df67dbbf0529c6896d51159f6074d8890f303e4a47abced830486f4ab57
Type coverMimetype application/pdf

Authority records BETA

Ekström, Joakim

Search in DiVA

By author/editor
Ekström, Joakim
By organisation
Communications and Transport SystemsThe Institute of Technology
Transport Systems and Logistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1358 downloads
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1586 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf