Banca de DEFESA: MATHEUS MACHADO VIEIRA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : MATHEUS MACHADO VIEIRA
DATA : 31/01/2024
HORA: 15:00
LOCAL: Google meet: meet.google.com/zoz-bcuy-myj
TÍTULO:

Uma meta-heurística para o Problema da Mochila com Penalidades

PALAVRAS-CHAVES:

Otimização Combinatória, Problema da Mochila, Meta-heurísticas, Iterated Local Search, Variable Neighborhood Descent.

PÁGINAS: 49
RESUMO:

O problema da mochila está entre um dos problemas combinatórios mais conhecidos.
Seu potencial de aplicação e as inúmeras variações que existem fazem dele um bom modelo
para diversos problemas práticos da vida real. Mais especificamente, este trabalho aborda
uma variante do problema, o Problema da Mochila com Penalidades (PMP, ou, em inglês,
KPF). Nesta variante, é fornecido um conjunto de itens e um grafo de conflitos, e o
objetivo é identificar uma coleção de itens que respeite a capacidade da mochila enquanto
maximiza o valor total dos itens menos as penalidades pelos itens conflitantes. O PMP
tem tido algum engajamento tanto por sua proximidade com outros problemas famosos,
como o do conjunto independente de peso máximo, e suas aplicações. Alguns exemplos
compreendem desde a organização da força de trabalho em chão de fábrica até problemas
de decisão em investimentos. Este trabalho apresenta um novo método para o problema
utilizando-se de ferramentas já bem estabelecidas, baseado na hibridização de Iterated
Local Search (ILS), Variable Neighborhood Descent (VND), e elementos de Tabu Search.
Nosso método leva em consideração quatro estruturas de vizinhança, introduzidas com
estruturas de dados eficientes para explorá-las. Resultados experimentais demonstram
que a abordagem proposta supera os algoritmos de ponta na literatura. Em particular, o
método proposto fornece soluções superiores em tempos de computação significativamente
mais curtos em todas as instâncias de referência. Também foi incluída uma análise de como
as estruturas de dados propostas influenciaram tanto a qualidade das soluções quanto o
tempo de execução do método.

MEMBROS DA BANCA:
Presidente - 1114959 - RIAN GABRIEL SANTOS PINHEIRO
Interno(a) - 1803490 - BRUNO COSTA E SILVA NOGUEIRA
Interno(a) - 2343385 - ERICK DE ANDRADE BARBOZA
Externo(a) à Instituição - Dimas Cassimiro do Nascimento Filho