Open AccessFormulações e heurı́sticas para os problemas leasing k-median e leasing k-center
Author(s) -
J. dos Santos,
Guilherme Londe,
Alexandre Ribeiro,
Welverton R. Silva
Publication year - 2019
Language(s) - Portuguese
Resource type - Conference proceedings
DOI - 10.5753/etc.2019.6397
Subject(s) - computer science , center (category theory) , physics , combinatorics , chemistry , mathematics , crystallography
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.