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: iaor20117030
Volume: 35
Issue: 3
Start Page Number: 216
End Page Number: 224
Publication Date: Mar 2003
Journal: Algorithmica
Authors: ,
Keywords: combinatorial optimization, facilities
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.