A Branch-and-Bound Method for the Fixed Charge Transportation Problem

Udatta S. Palekar, Mark H. Karwan and Stanley Zionts
Additional contact information
Udatta S. Palekar: Department of Mechanical and Industrial Engineering, University of Illinois at Urbana Champaign, 1206 West Green Street, Urbana, Illinois 61801
Mark H. Karwan: Department of Industrial Engineering, State University of New York at Buffalo, Buffalo, New York 14260
Stanley Zionts: School of Management, State University of New York at Buffalo, Buffalo, New York 14260

Management Science, 1990, vol. 36, issue 9, 1092-1105

Abstract: In this paper we develop a new conditional penalty for the fixed charge transportation problem. This penalty is stronger than both the Driebeek penalties and the Lagrangean penalties of Cabot and Erenguc. Computational testing shows that the use of these penalties leads to significant reductions in enumeration and solution times for difficult problems in the size range tested. We also study the effect of problem parameters on the difficulty of the problem. The ratio of fixed charges to variable costs, the shape of the problem, arc density in the underlying network and fixed charge arc density are shown to have a significant effect on problem difficulty for problems involving up to 40 origins and 40 destinations.

Keywords: combinatorial optimization; branch-and-bound (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.36.9.1092 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:36:y:1990:i:9:p:1092-1105

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().