Leasing K-Center, nova restrição e abordagem heurística

  • Valdomiro R. D. Neto PUC-Goiás
  • A. Ribeiro PUC-Goiás
  • G. P. P. Londe UNICAMP
  • W. R. da Silva UNICAMP

Resumo


Este trabalho aborda o problema Leasing K-Center, com uma nova restrição na sua formulação, para melhor refletir sua proposta original. Como solução é apresentada a metaheurística VNS, com resultados que superam outros métodos propostos (BRKGA, LS-LUBC e resolvedor Gurobi) e com velocidade superior para a maioria das instâncias.

Palavras-chave: Otimização Combinatória, Programação matemática, Teoria dos Grafos e Combinatória

Referências

dos Santos, J., Londe, G., Ribeiro, A., and da Silva,W. (2019). Formulações e heuristicas para os problemas leasing k-median e leasing k-center. In Anais do IV Encontro de Teoria da Computação, Porto Alegre, RS, Brasil. SBC.

dos Santos, J. M. (2019). Heurísticas para o problema Leasing K-Median. https://repositorio.pucgoias.edu.br/jspui/handle/123456789/3736. Monografia (Bacharel em Ciência da computação), Pontifícia Universidade Católica de Goiás, Brazil.

Garcia-Diaz, J., Menchaca-Mendez, R., Menchaca-Mendez, R., Pomares Hernández, S., Pérez-Sansalvador, J. C., and Lakouari, N. (2019). Approximation algorithms for the vertex k-center problem: Survey and experimental evaluation. IEEE Access, 7:109228–109245.

Hansen, P. and Mladenovic, N. (2003). A tutorial on variable neighborhood search. Technical report, Les Cahiers Du GERAD, Hec Montreal and GERAD.

Kariv, O. and Hakimi, S. L. (1979). An algorithmic approach to network location problems. i: The p-centers. SIAM Journal on Applied Mathematics, 37(3):513–538.

Lintzmayer, C. N. and Mota, G. O. (2017). Caderno de problemas. In 1º Workshop Paulista em Otimização, Combinatória e Algoritmos. Não publicado.

Londe, G. (2019). Heurísticas para o problema Leasing K-Center. https://repositorio.pucgoias.edu.br/jspui/handle/123456789/3742. Monografia (Bacharel em Ciência da computação), Pontifícia Universidade Católica de Goiás, Brazil.
Publicado
31/07/2022
D. NETO, Valdomiro R.; RIBEIRO, A.; LONDE, G. P. P.; SILVA, W. R. da. Leasing K-Center, nova restrição e abordagem heurística. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 57-60. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222816.