An Approximation Algorithm for a Large-Scale Facility Location Problem |
| |
Authors: | Kazuyoshi Hidaka Hiroyuki Okano |
| |
Affiliation: | Tokyo Research Laboratory, IBM Japan Ltd., 1623-14 Shimotsuruma, Yamato-shi, Kanagawa-ken 242, khidaka@jp.ibm.com, okanoh@jp.ibm.com, Japan
|
| |
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%. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|