METAHEURÍSTICA ILS APLICADA AO PROBLEMA DE p-MEDIANAS CAPACITADO

Este trabalho propõe um algoritmo baseado na meta-heurística Iterated Local Search (ILS) para a solução do problema de p-medianas capacitado. A construção da solução inicial é baseada na fase construtiva da meta-heurística Greedy Randomized Adaptive Search Procedure (GRASP). Foram realizados experimentos computacionais utilizando 35 instâncias da literatura. Os resultados, obtidos em 30 execuções da heurística, mostram gaps médios inferiores a 0,60\% para os melhores valores da função objetivo, em todas as instâncias, comparados com os valores obtidos pelo solver CPLEX e por \citet{Stefanello}, e valores médios para a função objetivo com gap médio inferior a 2,00\%. Além disso, em comparação aos resultados de \citet{Vasconcelos}, obteve-se gap médio negativo para os melhores valores de função objetivo e tempos médios de execução menores em aproximadamente 50\% das instâncias.