Defesa de Dissertação de Mestrado: André Willik Valenti
Document Actions
Defesa de Dissertação de Mestrado: Pedro Henrique Del Bianco Hokama
O Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional.
| What | Defesa de Mestrado |
|---|---|
| When |
14/10/2011 from 14:00 to 16:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
Nesta dissertação de mestrado propomos um método exato para o Problema
do Caixeiro Viajante com Restrições de Empacotamento Tridimensional,
que combina outros dois problemas bem conhecidos: o Problema do
Caixeiro Viajante e o Problema de Empacotamento Tridimensional com
Restrição de Ordem. Neste problema, um veículo deve partir carregado
de um depósito e entregar caixas em pontos pré-definidos para seus
clientes. Cada cliente tem um conjunto de caixas que deve receber e o
objetivo é minimizar o custo de deslocamento do veículo. As caixas
devem ser retiradas a partir da porta do contêiner do veículo e a
remoção das caixas de um cliente não pode ser obstruída pelas caixas a
serem descarregadas posteriormente.
Apresentamos uma nova formulação em Programação por Restrições para
encontrar um empacotamento que obedece a restrição de ordem. Também
adaptamos da literatura alguns algoritmos exatos e heurísticas rápidas
que tratam do mesmo problema. O Problema de Empacotamento
Tridimensional com Restrição de Ordem é resolvido em uma sub-rotina na
abordagem branch-and-cut, que busca uma rota de custo mínimo. A
solução obtida pode ser exata ou heurística, de acordo com o algoritmo
de empacotamento escolhido. Para comparar o desempenho dos métodos
propostos, realizamos testes computacionais em instâncias geradas
aleatoriamente. Os resultados foram bastante satisfatórios,
encontrando soluções ótimas para diversas instâncias.
Concurso Público para Professor Doutor - MS-3
