Uma heurística ILS para o Problema da Mochila com Penalidades
| dc.creator | Ana Flávia Ciríaco Moura | |
| dc.creator | Eduardo Theodoro Bogue | |
| dc.creator | Thiago Ferreira de Noronha | |
| dc.date.accessioned | 2024-08-14T20:55:53Z | |
| dc.date.accessioned | 2025-09-08T23:16:53Z | |
| dc.date.available | 2024-08-14T20:55:53Z | |
| dc.date.issued | 2021 | |
| dc.description.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. | |
| dc.format.mimetype | ||
| dc.identifier.issn | 29651476 | |
| dc.identifier.uri | https://hdl.handle.net/1843/74107 | |
| dc.language | por | |
| dc.publisher | Universidade Federal de Minas Gerais | |
| dc.relation.ispartof | Simpósio Brasileiro de Pesquisa Operacional | |
| dc.rights | Acesso Aberto | |
| dc.subject | Heurística | |
| dc.subject | Programação (Computadores) | |
| dc.subject.other | Heurística | |
| dc.subject.other | Programação (Computadores) | |
| dc.title | Uma heurística ILS para o Problema da Mochila com Penalidades | |
| dc.title.alternative | An ILS heuristic for the Backpack Problem with Penalties | |
| dc.type | Artigo de evento | |
| local.citation.issue | 53 | |
| local.citation.spage | 139627 | |
| local.description.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. | |
| local.publisher.country | Brasil | |
| local.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
| local.publisher.initials | UFMG | |
| local.url.externa | https://proceedings.science/sbpo/sbpo-2021/trabalhos/uma-heuristica-ils-para-o-problema-da-mochila-com-penalidades?lang=pt-br |