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

Abstract

This article tackles a variant of the Knapsack Problem, called the Knapsack Problem with Forfeits. In this variant, a set of distinct pairs of items is added, called forfeit pairs, so that a forfeit pair is composed of items that, when included together in the solution, imply the payment of a penalty at the cost of the solution. In this article, a heuristic based on Iterated Local Search is developed for the problem. The results obtained showed that the developed heuristic obtained better solutions than the best heuristic proposed in the literature for known instances.