Memetic Algorithm for Solving the Multilevel Uncapacitated Facility Location Problem

Article type: Research Article

Authors: Marić, Miroslav | Stanimirović, Zorica^; | Djenić, Aleksandar | Stanojević, Predrag

Affiliations: Faculty of Mathematics, University of Belgrade, Studentski trg 16/IV, 11 000 Belgrade, Serbia, e-mail: maricm@matf.bg.ac.rs, zoricast@matf.bg.ac.rs, djenic@matf.bg.ac.rs, djapedjape@gmail.com

Note: [] Corresponding author.

Abstract: We consider the Multilevel Uncapacitated Facility Location Problem (MLUFLP) and propose a new efficient integer programming formulation of the problem that provides optimal solutions for the MLUFLP test instances unsolved to optimality up to now. Further, we design a parallel Memetic Algorithm (MA) with a new strategy for applying the local search improvement within the MA frame. The conducted computational experiments show that the proposed MA quickly reaches all known optimal and best known solutions from the literature and additionally improves several solutions for large-scale MLUFLP test problems.

Keywords: facility location, network design, hierarchical problems, memetic algorithm, parallelization

Journal: Informatica, vol. 25, no. 3, pp. 439-466, 2014