Penalty Decomposition Methods for Second-Best Congestion Pricing Problems on Large-Scale Networks.

This article focuses on the second-best congestion pricing (SBCP) problem in transportation, a challenging bilevel optimization problem involving toll setting on a subset of network links to minimize total travel time or maximize social welfare. The authors reveal that the marginal value function reformulation of SBCP is continuously differentiable and exhibits a convexity-convexity structure with respect to upper- and lower-level variables. Leveraging these structural properties, they propose two penalty decomposition methods—the penalty decomposition (PD) and relaxation penalty decomposition (RPD) methods—that avoid linearizing nonconvex functions and come with convergence guarantees. Extensive computational experiments on real-world medium- and large-scale road networks demonstrate that these methods outperform existing popular algorithms in both scalability and computational efficiency, successfully solving SBCP on networks with thousands of links and tens of thousands of origin-destination pairs.