Optimizing toll locations and levels using a mixed integer linear approximation approach

Joakim Ekström, Agachai Sumalee, Hong K. Lo

Research output: Journal article publicationJournal articleAcademic researchpeer-review

41 Citations (Scopus)

Abstract

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 non-linear 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.
Original languageEnglish
Pages (from-to)834-854
Number of pages21
JournalTransportation Research Part B: Methodological
Volume46
Issue number7
DOIs
Publication statusPublished - 1 Jan 2012

Keywords

  • Bi-level optimization
  • Congestion pricing
  • Global optimization
  • Network design

ASJC Scopus subject areas

  • Transportation
  • Management Science and Operations Research

Cite this