The Facility Location Problem seeks to decide how many and which facilities to open in order to serve the demands of a set of clients. It is a very relevant problem due to its theoretical interest, being an NP-hard problem widely studied, and for which numerous approximation algorithms and metaheuristics are proposed. It is also relevant for being motivated by practical applications, modeling problems such as plant positioning, construction of computer networks and information clustering.
In this work we present a memetic algorithm (MA) and a late acceptance algorithm for the uncapacitated facility location problem (UFLP). The computational experiments show that the MA achieves better solutions when compared with approximation algorithms and other metaheuristics.