Uma heurística ILS para o Problema da Mochila com Penalidades
Carregando...
Data
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Artigo de evento
Título alternativo
An ILS heuristic for the Backpack Problem with Penalties
Primeiro orientador
Membros da banca
Resumo
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.
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.
Assunto
Heurística, Programação (Computadores)
Palavras-chave
Heurística, Programação (Computadores)
Citação
Departamento
Curso
Endereço externo
https://proceedings.science/sbpo/sbpo-2021/trabalhos/uma-heuristica-ils-para-o-problema-da-mochila-com-penalidades?lang=pt-br