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
Heuristic algorithms for a second-best congestion pricing problem
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
Centre for Traffic Research, Royal Institute of Technology.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology. (Trafiksystem)ORCID iD: 0000-0001-6405-5914
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.

Place, publisher, year, edition, pages
2009. Vol. 10, no 1, 85-102 p.
Keyword [en]
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: urn:nbn:se:liu:diva-18641DOI: 10.1007/s11066-008-9019-9OAI: oai:DiVA.org:liu-18641DiVA: diva2:220961
Available from: 2009-06-03 Created: 2009-06-03 Last updated: 2017-12-13Bibliographically approved
In thesis
1. Optimization Approaches for Design of Congestion Pricing Schemes
Open this publication in new window or tab >>Optimization Approaches for Design of Congestion Pricing Schemes
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:nbn:se:liu:diva-76287 (URN)978-91-7519-903-0 (ISBN)
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

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Ekström, JoakimRydergren, Clas

Search in DiVA

By author/editor
Ekström, JoakimRydergren, Clas
By organisation
Communications and Transport SystemsThe Institute of Technology
In the same journal
Netnomics
Other Engineering and Technologies not elsewhere specified

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 364 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