A Memetic Algorithm for Solving Two Variants of the Two-Stage Uncapacitated Facility Location Problem


  • Stefan Miškovic University of Belgrade
  • Zorica Stanimirovic Assistant Professor at Faculty of Mathematics, University of Belgrade,




Memetic algorithms, Multi-level facility location problem, Combinatorial optimization


This paper deals with a two-stage uncapacitated facility location problem (TSUFLP), which has significant application in telecommunication sector. Given the set of demand points and the sets of possible locations for the first and second level concentrators (switches, multiplexors), the goal of the TSUFLP is to define the structure of two-level concentrator access network, such that the the total costs of establishing such a network are minimized. We consider two variants of the TSUFLP from the literature and propose an efficient memetic algorithm (MA) based on hybridization of the evolutionary approach and two local-search heuristics. A simulated annealing method, which is incorporated in the MA frame, additionally improves the efficiency of the proposed MA. The described MA approach is benchmarked on test instances of medium and large dimensions from the literature, which are adapted for the TSUFLP and involve from 50 to 500 user nodes. In order to test effectiveness of the MA, we further modify some large-scale instances from the literature, which include 1000 and 2000 demand points.
Exhaustive computational experiments show that the proposed MA
method quickly reaches all known optimal solutions, previously
obtained by CPLEX solver or existing exact method from the literature,
and also provides solutions on large-scale data set in short CPU times. Regarding both solution quality and running times, we conclude that the proposed MA represents a powerful metaheuristic method for solving the TSUFLP and other similar network problems.

DOI: http://dx.doi.org/10.5755/j01.itc.42.2.1768

Author Biography

Zorica Stanimirovic, Assistant Professor at Faculty of Mathematics, University of Belgrade,

Assistant Professor at the Department for Numerical Mathematics and Optimization, Faculty of Mathematics, University of Belgrade

Vice-Dean for Science and Research