An approximation algorithm for a large-scale facility location problem

An approximation algorithm for a large-scale facility location problem

0.00 Avg rating0 Votes
Article ID: iaor200573
Country: United States
Volume: 35
Issue: 3
Start Page Number: 216
End Page Number: 224
Publication Date: Mar 2003
Journal: Algorithmica
Authors: ,
Keywords: greedy algorithms
Abstract:

We developed a new practical optimization method that gives approximate solutions for large-scale real instances of the Uncapacitated Facility Location Problem. The optimization consists of two steps: application of the Greedy-Interchange heuristic using a small subset of warehouse candidates, and application of the newly developed heuristic named Balloon Search that takes account of all warehouse candidates, and runs in O(3n + 2n log (n)) expected time (n is the number of nodes of the underlying graph). Our experiments on the spare parts logistics of a Japanese manufacturing company with 6000 customers and 380,000 warehouse candidates led us to conclude that the Greedy heuristic improved the total cost by 9–11%, that the Interchange heuristic improved the total cost by an additional 0.5–1.5%, and that Balloon Search improved it by a further 0.5–1.5%

Reviews

Required fields are marked *. Your email address will not be published.