An Improved Genetic Algorithm for the Multi Level Uncapacitated Facility Location Problem

  • Vanja Miomir Korac
  • Jozef Kratica Mathematical Institute, Serbian Academy of Sciences and Arts
  • Aleksandar Savić University of Belgrade, Faculty of Mathematics Studentski trg 16, 11000 Belgrade, Serbia

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

[1] 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

[2] 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

[3] 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

[4] 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.

[5] N.J. Edwards, Approximation algorithms for the multi-level facility location problem. Ph.D. Thesis, Cornell University, 2001.

[6] 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.

[7] 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

[8] M. Marić, An efficient genetic algorithm for solving the multi-level uncapacitated facility location problem, Computing and Informatics, 29(2): 183–201, 2010.

[9] J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach. Mathematical Programming, 108: 159–176, 2006.
http://dx.doi.org/10.1007/s10107-006-0704-x
Published
2013-11-11
How to Cite
KORAC, Vanja Miomir; KRATICA, Jozef; SAVIĆ, Aleksandar. An Improved Genetic Algorithm for the Multi Level Uncapacitated Facility Location Problem. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 8, n. 6, p. 845-853, nov. 2013. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/134>. Date accessed: 07 july 2020. doi: https://doi.org/10.15837/ijccc.2013.6.134.

Keywords

evolutionary approach, metaheuristics, discrete location, combinatorial op- timization.