To access the full text documents, please follow this link: http://hdl.handle.net/2117/16393

Iterated greedy algorithms for the maximal covering location problem
Rodríguez, Francisco J.; Blum, Christian; Lozano, Manuel; García Martínez, Carlos
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
The problem of allocating a set of facilities in order to maximisethe sum of the demands of the covered clients is known as themaximal covering location problem. In this work we tackle this problemby means of iterated greedy algorithms. These algorithms iteratively refinea solution by partial destruction and reconstruction, using a greedyconstructive procedure. Iterated greedy algorithms have been appliedsuccessfully to solve a considerable number of problems. With the aim ofproviding additional results and insights along this line of research, thispaper proposes two new iterated greedy algorithms that incorporate twoinnovative components: a population of solutions optimised in parallelby the iterated greedy algorithm, and an improvement procedure thatexplores a large neighbourhood by means of an exact solver. The benefitsof the proposal in comparison to a recently proposed decompositionheuristic and a standalone exact solver are experimentally shown.
2012-08-28
Àrees temàtiques de la UPC::Informàtica::Intel·ligència artificial::Sistemes experts
Iterated greedy algorithm
Large neighbourhood search
Maximal covering location problem
Algorismes -- Informàtica
Restricted access - publisher's policy
Article
         

Show full item record

 

Coordination

 

Supporters