An Improved Genetic Algorithm for the Multi Level Uncapacitated Facility Location Problem
Keywords:
evolutionary approach, metaheuristics, discrete location, combinatorial op- timization.Abstract
In this paper, an improved genetic algorithm (GA) for solving the multi-level uncapacitated facility location problem (MLUFLP) is presented. First improvement is achieved by better implementation of dynamic programming, which speeds up the running time of the overall GA implementation. Second improvement is hybridization of the genetic algorithm with the fast local search procedure designed specially for MLUFLP. The experiments were carried out on instances proposed in the literature which are modied standard single level facility location problem instances. Improved genetic algorithm reaches all known optimal and the best solutions from literature, but in much shorter time. Hybridization with local search improves several best-known solutions for large-scale MLUFLP instances, in cases when the optimal is not known. Overall running time of both proposed GA methods is signicantly shorter compared to previous GA approach.References
K. Aardal, F. Chudak, D.B. Shmoys, A 3-approximation algorithm for the k-level uncapacitated facility location problem, Information Processing Letters, 72:161-167, 1999. http://dx.doi.org/10.1016/S0020-0190(99)00144-1
A. Ageev, Improved approximation algorithms for multilevel facility location problems, Operations Research Letters, 30: 327-332, 2002. http://dx.doi.org/10.1016/S0167-6377(02)00162-1
A. Ageev, Y. Ye, J. Zhang, Improved combinatorial approximation algorithms for the k-level facility location problem, SIAM Journal on Discrete Mathematics, 18: 207-217, 2005. http://dx.doi.org/10.1137/S0895480102417215
A.F. Bumb, W. Kern, A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, 55-62, August 18-20, 2001.
N.J. Edwards, Approximation algorithms for the multi-level facility location problem. Ph.D. Thesis, Cornell University, 2001.
V. Filipović, J. Kratica, D. Tošić, D. I. Ljubić, Fine Grained Tournament Selection for the Simple Plant Location Problem. it Proceedings of the 5th Online World Conference on Soft Computing Methods in Industrial Applications - WSC5, 152-158, September 2000.
J. Krarup, P. M. Pruzan, The simple plant location problem: Survey and synthesis, European Journal of Operational Research, 12: 36-81, 1983. http://dx.doi.org/10.1016/0377-2217(83)90181-9
M. Marić, An efficient genetic algorithm for solving the multi-level uncapacitated facility location problem, Computing and Informatics, 29(2): 183-201, 2010.
J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach. Mathematical Programming, 108: 159-176, 2006.
Additional Files
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
