Optimal multi-step toll design under general user heterogeneity

Hongyu Chen, Yu Marco Nie*, Yafeng Yin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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 solutions within a relatively small number of iterations.

Original languageEnglish (US)
Pages (from-to)775-793
Number of pages19
JournalTransportation Research Part B: Methodological
StatePublished - Nov 1 2015


  • Bottleneck model
  • General user heterogeneity
  • Mathematical program with equilibrium constraint
  • Quadratic program
  • Step toll

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'Optimal multi-step toll design under general user heterogeneity'. Together they form a unique fingerprint.

Cite this