Change search
ReferencesLink to record
Permanent link

Direct link
Optimizing Toll Locations and Levels Using a Mixed Integer Linear Approximation Approach
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
Department of Civil and Structural Engineering, Hong Kong Polytechnic University, Kowloon, Hong Kong, China.
Department of Civil and Environmental Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong.
2012 (English)In: Transportation Research Part B: Methodological, ISSN 0191-2615, 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. Vol. 46, no 7, 834-854 p.
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-76641DOI: 10.1016/j.trb.2012.02.006ISI: 000305435600004OAI: diva2:515575
Available from: 2012-04-13 Created: 2012-04-13 Last updated: 2014-11-19Bibliographically 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.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1443
National Category
Transport Systems and Logistics
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)
Available from: 2012-04-13 Created: 2012-04-02 Last updated: 2013-09-12Bibliographically approved

Open Access in DiVA

fulltext(403 kB)77 downloads
File information
File name FULLTEXT01.pdfFile size 403 kBChecksum SHA-512
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
In the same journal
Transportation Research Part B: Methodological
Engineering and Technology

Search outside of DiVA

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

Altmetric score

Total: 569 hits
ReferencesLink to record
Permanent link

Direct link