Network-optimized road pricing: Part II: Algorithms and examples

The conclusion of a two-part series, this paper devises an algorithm that finds a system of optimal tolls in a road network whose trips have a stochastic value of time. As formulated in Part I, the model is a variational inequality, equivalent to a specialized bicriterion equilibrium traffic assignment whose solution reflects a traffic flow simultaneously user- and system-optimal. To compute these optimal tolls, our algorithm uses restricted simplicial decomposition. It solves the subproblem (direction step) with a novel multipath traffic assignment that obviates path enumeration. It solves the master problem (averaging step) using nonlinear complementarity. For real-world applications, where the algorithm’s precondition that every congested arc may have a toll is impractical, this paper enhances the model to include link-specific upper and lower bounds on tolls. This more realistic model is solved with an heuristic using the optimization algorithm to its advantage. As our performance statistics show, the algorithm's speed makes it a practical planning tool. Experiments with the heuristic support the welcome hypothesis that a few well placed and properly priced tolls can reduce traffic congestion dramatically.