Leasing K-Center, nova restrição e abordagem heurística
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.
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
Como Citar
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.
