Premium
Decomposition techniques for the minimum toll revenue problem
Author(s) -
Bai Lihui,
Hearn Donald W.,
Lawphongpanich Siriphong
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20024
Subject(s) - toll , decomposition , revenue , mathematical optimization , computer science , linear programming , flow network , decomposition method (queueing theory) , operations research , software , network planning and design , mathematics , economics , computer network , finance , ecology , genetics , discrete mathematics , biology , programming language
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. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 142–150 2004