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

Vanja Miomir Korac, Jozef Kratica, Aleksandar Savić

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.

Keywords


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

Full Text:

PDF

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.

http://dx.doi.org/10.1007/s10107-006-0704-x




DOI: https://doi.org/10.15837/ijccc.2013.6.134



Copyright (c) 2017 Vanja Miomir Korac, Jozef Kratica, Aleksandar Savić

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2);

SCImago Journal & Country Rank

Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.