Decomposition techniques for the minimum toll revenue problem

The objective of the minimum toll revenue (MINREV) problem is to find tolls that simultaneously cause users to use the transportation network efficiently and minimize the total toll revenues that must be collected. This article investigates the Dantzig–Wolfe (DW) decomposition as an approach for solving the MINREV problem and establishes its relationships with a cutting plane algorithm and other proposed approaches. The article also identifies the variant of DW decomposition most suitable for implementation. Numerical experiments with real transportation networks suggest that DW decomposition is robust and should be used when the problems are too large for standard linear programming software. Although transportation planning is the application emphasized in this article, it should be noted that the MINREV problem also has applications in telecommunication network design and control.