A Dual-Based Algorithm for Multiproduct Uncapacitated Facility Location

John G. Klincewicz and Hanan Luss
Additional contact information
John G. Klincewicz: AT&T Bell Laboratories, Holmdel, New Jersey
Hanan Luss: AT&T Bell Laboratories, Holmdel, New Jersey

Transportation Science, 1987, vol. 21, issue 3, 198-206

Abstract: The multiproduct uncapacitated facility location problem (MUFLP) is a generalization of the classic uncapacitated facility location problem (UFLP). In MUFLP, different products are required by the customers. In addition to the fixed cost for opening a facility, there is an added fixed cost for handling a particular product. Assignment costs are incurred for satisfying a customer's requirement for each of the separate products. The objective is to minimize the total fixed costs plus assignment costs subject to satisfying all customer requirements. We propose a new dual-based algorithm for MUFLP that extends previous work for UFLP that has proved so successful. Dual ascent and dual adjustment procedures generate a good feasible solution to the dual of the linear programming relaxation of MUFLP. A feasible primal solution to MUFLP can then be constructed based on this dual solution. Like the analogous procedures for UFLP, these procedures can be used either as a stand-alone heuristic or, else, they can be incorporated into a branch-and-bound algorithm. Computational experience is given for both randomly generated and nonrandom problems with quite favorable results.

Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.21.3.198 (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:ortrsc:v:21:y:1987:i:3:p:198-206

Access Statistics for this article

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