Optimal multi-step toll design under general user heterogeneity

• 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).
• An analytical method is proposed to solve the MPEC by decomposing it into smaller and easier quadratic programs.
• We prove that the proposed method ensures global optimality if that each quadratic program can be solved globally.
• To obviate enumerating all departure orders, an efficient heuristic method is developed.

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.