Premium
A genetic algorithm for the uncapacitated facility location problem
Author(s) -
Tohyama Hiroaki,
Ida Kenichi,
Matsueda Jun
Publication year - 2011
Publication title -
electronics and communications in japan
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.131
H-Index - 13
eISSN - 1942-9541
pISSN - 1942-9533
DOI - 10.1002/ecj.10180
Subject(s) - facility location problem , genetic algorithm , mathematical optimization , computer science , space (punctuation) , algorithm , selection (genetic algorithm) , series (stratigraphy) , 1 center problem , service (business) , mathematics , artificial intelligence , paleontology , economy , economics , biology , operating system
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