Formulações e heurı́sticas para os problemas leasing k-median e leasing k-center

• Jorge dos Santos PUC-GÓIAS
• Guilherme Londe PUC-GÓIAS
• Alexandre Ribeiro PUC-GÓIAS
• Welverton da Silva UNICAMP

DOI: https://doi.org/10.5753/etc.2019.6397

Resumo

Neste artigo, consideramos as generalizações dos problemas k-median e k-center, conhecidas, respectivamente, por leasing k-median (LKM) e leasing k-center (LKC). Apresentamos formulações de programação linear inteira e uma heurı́stica baseada na meta-heurı́stica BRKGA. Comparamos as soluções geradas pela heurı́stica com as soluções geradas pelo resolvedor GUROBI aplicado às formulações em programação linear, estabelecendo um prazo de 10 minutos de execução para ambos. Para as instâncias pequenas testadas, os custos das soluções heurı́sticas foram próximos aos custos ótimos (GAP médio ≤ 8%). Para instâncias maiores testadas a heurı́stica gerou soluções superiores às do resolvedor, em pelo menos metade dos testes.

Palavras-chave: Facility location problems, BRKGA, heuristics

Referências

Ahn, S., Cooper, C., Cornu´ejols, G., and Frieze, A. (1988). Probabilistic Analysis of a Relaxation for the k-Median Problem. Mathematics ofOperations Research.

Daskin, M. S. (1995). Network and Discrete Locations: Models, algorithms, and appli- cations. John Wiley & Sons.
Gonc¸alves, J. F. and Resende, M. G. C. (2010). Biased random-key genetic algorithms for combinatorial optimization. Journal ofHeuristics.

Kariv, O. and Hakimi, S. L. (1979a). An Algorithmic Approach to Network Location Problems. I: The p-Centers. SIAM Journal on Applied Mathematics.

Kariv, O. and Hakimi, S. L. (1979b). An Algorithmic Approach to Network Location Problems. II: The p-Medians. SIAM Journal on Applied Mathematics.

Lintzmayer, C. N. and Mota, G. O. (2017). Caderno de problemas. In 1o Workshop Paulista em Otimizac¸ ˜ao, Combinat´oria e Algoritmos.

Toso, R. and Resende, M. (2015). A C++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software.