This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Bai, L. Articles by Rubin, P. A.

Combinatorial Benders Cuts for the Minimum Tollbooth Problem

College of Business Administration, Valparaiso University, Valparaiso, Indiana 46383
The Eli Broad Graduate School of Management, Michigan State University, East Lansing, Michigan 48824
lihui.bai{at}valpo.edu
rubin{at}msu.edu

We address a toll pricing problem in which the objective is to minimize the number of required toll facilities in a transportation network while inducing drivers to make the most efficient collective use of the network. We formulate the problem as a mixed-integer programming model and propose a solution method using combinatorial Benders cuts. Computational study of real networks as well as randomly generated networks indicates that our proposed method is efficient in obtaining provably optimal solutions for networks with small to medium sizes.

Subject classifications: congestion pricing; traffic equilibrium; Benders decomposition; branch and cut; mixed-integer program.
History: Received December 2007; revision received July 2008; accepted September 2008.