Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
Solving a Mixed Integer Linear Program Approximation of the Toll Design Problem Using Constraint Generation within a Branch and Cut Algorithm
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-1367-6793
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
Department of Civil and Structural Engineering, Hong Kong Polytechnic University, Kowloon, Hong Kong, China.
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. Vol. 10, no 9, 791-819 p.
Keyword [en]
global optimisation; bilevel optimisation; toll design; road pricing
National Category
Civil Engineering
Identifiers
URN: urn:nbn:se:liu:diva-76642DOI: 10.1080/23249935.2013.813988ISI: 000340257500002OAI: oai:DiVA.org:liu-76642DiVA: diva2:515579
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
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

fulltext(424 kB)221 downloads
File information
File name FULLTEXT01.pdfFile size 424 kBChecksum SHA-512
c2fef0fc02b5711603189686cec376fd56bf85a46dc749a8384e18788aad838defe6702b226438e42870346561dbcf4d6ec1a3a0142ccf2b6f7e7ce419de0ae1
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 792 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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