An approximation algorithm for a large-scale facility location problem

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