Metaheurística Iterated Local Search Aplicada ao Problema de Localização com Cobertura Parcial
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.
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
Como Citar
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.
