Defesa de Doutorado de Pedro Henrique Del Bianco Hokama

Título do Trabalho
Algoritmos para Problemas com Restrição de Empacotamento
Candidato(a)
Pedro Henrique Del Bianco Hokama
Nível
Doutorado
Data
Add to Calender 2016-03-04 00:00:00 2016-03-04 00:00:00 Defesa de Doutorado de Pedro Henrique Del Bianco Hokama Algoritmos para Problemas com Restrição de Empacotamento Auditório do IC 2 - Sala 85 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00 h
Local
Auditório do IC 2 - Sala 85
Orientador(a)
Flávio Keidi Miyazawa
Banca Examinadora

Titulares:
Flávio Keidi Miyazawa (IC/UNICAMP)
Horacio Hideki Yanasse (ICT/UFSP)
Reinaldo Morabito Neto (DEP/UFSCAR)
Kelly Cristina Poldi (IMECC/UNICAMP)
Luis Augusto Angelotti Meira (FT/UNICAMP)
Suplentes:
Eduardo Candido Xavier (IC/UNICAMP)
Rafael Crivellari Saliba Schouery (IC/UNICAMP)
Débora Pretti Ronconi (DEP/Poli-USP)

Resumo

Neste projeto investigamos classes de problemas com restrições de empacotamento. Três diferentes problemas foram investigados, e algoritmos foram propostos para cada um deles. O primeiro é o problema de roteamento de veículos com empacotamento bidimensional e tridimensional, onde um conjunto de veículos parte de um depósito e deve entregar a demanda de itens de seus clientes. Cada veículo possui um contêiner retangular, e cada cliente deseja receber uma diversidade de itens também retangulares. Em cada rota realizada por um veículo é preciso encontrar uma forma de empacotar os itens de todos os clientes dentro do contêiner, de modo que a cada visita, a retirada dos itens daquele cliente possa ser realizada sem que os outros itens precisem ser movidos. O objetivo geral do problema é minimizar o deslocamento total dos veículos. O segundo é o problema online de empacotamento de círculos em contêineres. Nesse problema devemos empacotar círculos em recipientes retangular. Os círculos chegam de forma online, ou seja, cada círculo que chega deve ser empacotado, e não se sabe a priori quais os tamanhos dos círculos que virão. O objetivo é minimizar o número de contêineres utilizados. O terceiro é problema da mochila bidimensional com conflitos. Nesse problema é dado um conjunto de itens e um recipiente bidimensionais e retangulares, sendo que cada item possui um valor associado e alguns pares de itens são conflitantes, ou  seja, não podem estar simultaneamente dentro do recipiente. O objetivo do problema é escolher um subconjunto dos itens de valor máximo, mas que seja possível empacotar esses itens dentro do recipiente. A tese é composta por três artigos, cada um dedicado a um dos problemas. Em todos eles, diferentes técnicas de design de algoritmos foram utilizadas de forma integrada, dentre as principais estão: programação linear inteira, programação por restrições, heurísticas, meta-heurísticas e algoritmos aproximados. Além das contribuições de cada um dos artigos, o conjunto da obra evidência a eficiência da integração das técnicas citadas, abrindo o caminho para que as metodologias estudadas possam ser aplicadas a outros problemas.