Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/74107
Tipo: | Artigo de Evento |
Título: | Uma heurística ILS para o Problema da Mochila com Penalidades |
Título(s) alternativo(s): | An ILS heuristic for the Backpack Problem with Penalties |
Autor(es): | Ana Flávia Ciríaco Moura Eduardo Theodoro Bogue Thiago Ferreira de Noronha |
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) |
Idioma: | por |
País: | Brasil |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/74107 |
Data do documento: | 2021 |
metadata.dc.url.externa: | https://proceedings.science/sbpo/sbpo-2021/trabalhos/uma-heuristica-ils-para-o-problema-da-mochila-com-penalidades?lang=pt-br |
metadata.dc.relation.ispartof: | Simpósio Brasileiro de Pesquisa Operacional |
Aparece nas coleções: | Artigo de Evento |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Uma heur´ıstica ILS.pdfA.pdf | 362.98 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.