A Dual-Based Algorithm for Multiproduct Uncapacitated Facility Location

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 handl...

Full description

Saved in:
Bibliographic Details
Published in:Transportation science 1987-08, Vol.21 (3), p.198-206
Main Authors: Klincewicz, John G, Luss, Hanan
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Capital costs
Cost allocation
Exact sciences and technology
Fixed costs
Ground, air and sea transportation, marine construction
Heuristics
Linear programming
Marketing strategies
Minimization of cost
Optimal solutions
Warehouses
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0041-1655
1526-5447
DOI:10.1287/trsc.21.3.198