Uma Heurística GRASP com Path-Relinking para o Problema da Mochila com Penalidades

Neste trabalho, exploramos uma variante do tradicional Problema da Mochila, denominada Problema da Mochila com Penalidades. Nessa versão, é adicionado um conjunto composto por pares de itens distintos, conhecidos como pares de penalidades. Cada par consiste em itens cuja seleção simultânea na solução resulta em um acréscimo de penalidade ao custo total da solução. Apresentamos uma abordagem heurística baseada em GRASP com Path-relinking para resolver este problema. Os resultados obtidos revelam que a heurística supera outras abordagens da literatura, alcançando um gap médio inferior a 1% nas instâncias avaliadas.