A genetic algorithm for the uncapacitated facility location problem

• Published in: Electronics and communications in Japan 2011-05, Vol.94 (5), p.47-54
• Main Authors: Tohyama, Hiroaki, Ida, Kenichi, Matsueda, Jun
• Format: Article
• Language: English
• Subjects: classification index; facility location problem; genetic algorithm; Genetic algorithms; Mathematical models; On-line systems; Online; Optimization; Position (location); Searching; Solution space
• ISSN: 1942-9533; 1942-9541; 1942-9541
• DOI: 10.1002/ecj.10180

The Uncapacitated Facility Location Problem (UFLP) is a fundamental optimization problem involving the selection of locations at which facilities supplying the same service are to be placed. Since it has been shown that the UFLP is NP‐hard, it has generally been thought that there is no hope of finding a polynomial time algorithm by which an optimal solution is always obtained. In this paper, we propose a genetic algorithm for solving the UFLP. In the UFLP, according to the ratio of the cost of facility placement and the cost to users of the facility, the number of facility locations can be roughly estimated. Therefore, partial solution spaces that are likely to contain a good solution can be predicted to some extent on the basis of the classification index. By using mutation with the operation that searches the solution space that is likely to contain a good solution, the proposed method can search the whole space of solutions efficiently. Its effectiveness is shown by a numerical experiment in which our method is compared with existing methods. © 2011 Wiley Periodicals, Inc. Electron Comm Jpn, 94(5): 47–54, 2011; Published online in Wiley Online Library (wileyonlinelibrary.com). DOI 10.1002/ecj.10180