Optimal Multi-Step Toll Design under General User Heterogeneity

Hongy Chen, Yu Nie*, Yafeng Yin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

This paper studies the optimal multi-step toll design problem for the bottleneck model with general user heterogeneity. The design model is formulated as a mathematical program with equilibrium constraints (MPEC), which is NP-hard due to non-convexity in both the objective function and the feasible set. An analytical method is proposed to solve the MPEC by decomposing it into smaller and easier quadratic programs, each corresponding to a unique departure order of different user classes. The quadratic programs are defined on a polyhedral set, which makes it easier to identify a local optimum. Importantly, each quadratic program is constrained by a set of linear feasibility cuts that define the presence of each user class in the arrival window. We prove that the proposed method ensures global optimality provided that each quadratic program can be solved globally. To obviate enumerating all departure orders, a heuristic method is developed to navigate through the solution space by using the multipliers associated with the feasibility cuts. Numerical experiments are conducted on several small examples to validate the proposed methodology. These experiments show that the proposed heuristic method is effective in finding near-optimal solution within a relatively small number of iterations.

Original languageEnglish (US)
Pages (from-to)341-361
Number of pages21
JournalTransportation Research Procedia
Volume7
DOIs
StatePublished - 2015

Funding

The work was supported by National Science Foundation under the award numbers CMMI-1256021 and CMMI-1256106. Constructive comments of three anonymous reviewers are greatly appreciated. The mistakes are those of the authors alone.

Keywords

  • bottleneck model
  • general user heterogeneity
  • mathematical program with equilibrium constraint
  • quadratic program
  • step toll

ASJC Scopus subject areas

  • Transportation

Fingerprint

Dive into the research topics of 'Optimal Multi-Step Toll Design under General User Heterogeneity'. Together they form a unique fingerprint.

Cite this