Solving the Pareto-improving toll problem via manifold suboptimization

Congestion tolls are considered to be Pareto-improving if they reduce travel delay or improve social benefit and ensure that, when compared to the situation without any tolling intervention, no user is worse off in terms of travel cost measured, e.g., in units of time. The problem of finding Pareto-improving tolls can be formulated as a mathematical program with complementarity constraints, a class of optimization problems difficult to solve. Using concepts from manifold suboptimization, we propose a new algorithm that converges to a strongly stationary solution in a finite number of iterations. The algorithm is also applicable to the problem of finding approximate Pareto-improving tolls and can address the cases where demands are either fixed or elastic. Numerical results using networks from the literature are also given.