Metaheurística Iterated Local Search Aplicada ao Problema de Localização com Cobertura Parcial

  • Leonardo Correa Cardoso CEFET-MG
  • Fábio Pires Mourão CEFET-MG / IFMG
  • Elisangela Martins de Sá CEFET-MG
  • Sérgio Ricardo de Souza CEFET-MG

Resumo


O problema de localização de cobertura de conjunto parcial consiste em localizar um conjunto de instalações de forma a minimizar o custo total de localização e garantir que uma quantidade predeterminada de demanda de clientes seja coberta por estas instalações. Este artigo apresenta um algoritmo baseado na metaheurística Iterated Local Search para a resolução deste problema. Além disso, um conjunto de experimentos computacionais foram realizados e resultados demonstram que boas soluções podem ser encontradas para instâncias moderadamente grandes.

Referências

Bilal, N., Galinier, P., and Guibault, F. (2014). An iterated-tabu-search heuristic for a variant of the partial set covering problem. Journal of Heuristics, 20(2):143-164.

Church, R. and ReVelle, C. (1974). The maximal covering location problem. In Papers of the regional science association, volume 32, pages 101-118. Springer-Verlag.

Coco, A. A., Santos, A. C., and Noronha, T. F. (2018). Formulation and algorithms for the robust maximal covering location problem. Electronic Notes in Discrete Mathematics, 64:145-154.

Cordeau, J.-F., Furini, F., and Ljubić, I. (2019). Benders decomposition for very large scale partial set covering and maximal covering location problems. European Journal of Operational Research, 275(3):882-896.

Daskin, M. S. and Owen, S. H. (1999). Two new location covering problems: The partial p-center problem and the partial set covering problem. Geographical Analysis, 31(3):217-235.

Galvão, R. D. and ReVelle, C. (1996). A lagrangean heuristic for the maximal covering location problem. European Journal of Operational Research, 88(1):114-123.

Lourenço, H. R., Martin, O. C., and Stützle, T. (2003). Iterated Local Search, pages 320-353. Springer US, Boston, MA.

Mišković, S. (2017). A VNS-LP algorithm for the robust dynamic maximal covering location problem. OR Spectrum, 39(4):1011-1033.

Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11):1097-1100.
Publicado
28/11/2022
CARDOSO, Leonardo Correa; MOURÃO, Fábio Pires; SÁ, Elisangela Martins de; SOUZA, Sérgio Ricardo de. Metaheurística Iterated Local Search Aplicada ao Problema de Localização com Cobertura Parcial. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 19. , 2022, Campinas/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 142-151. ISSN 2763-9061. DOI: https://doi.org/10.5753/eniac.2022.227629.