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