容量なし施設配置問題のための遺伝的アルゴリズムの提案 A Proposal of a Genetic Algorithm for Uncapacitated Facility Location Problem
Uncapacitated Facility Location Problem (UFLP) is a fundamental optimization problem about the selection of locations where some facilities in which the same service is supplied are placed. Since it is shown that UFLP is NP-hard, it is thought that there exists no hope in finding a polynomial time algorithm through which an optimal solution is always obtained. In this paper, we propose a genetic algorithm for solving UFLP. In UFLP, according to the ratio for the cost for facilities placement and the cost for which the users use the facility, the number of facility placement locations can be expected, roughly. Therefore, the partial solution space that seems there is a good solution can be expected to some extent based on the classification index. By using the mutation with the operation which searches the partial solution space where it can be expected that there is a good solution, the proposed method can search the whole space of solutions efficiently. The effectiveness is shown by a numerical experiment where our method is compared with existing methods.
- 電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and System Society
電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and System Society 128(4), 628-635, 2008-04-01
The Institute of Electrical Engineers of Japan