Uma heurística ILS para o Problema da Mochila com Penalidades

Neste trabalho, estudamos uma variante do Problema da Mochila, denominada de o Problema da Mochila com Penalidades. Nesta variante, acrescenta-se um conjunto de pares distintos de itens, chamados de pares de penalidades, de modo que um par de penalidade é composto por itens que, quando selecionados juntos para a solução, implicam no pagamento de uma penalidade ao custo da solução. Neste artigo, uma heurística baseada em Busca Local Iterada é proposta para o problema. Os resultados obtidos mostraram que a heurística desenvolvida obteve melhores soluções que o presente estado da arte da literatura para as instâncias conhecidas.