Busca avançada
Ano de início
Entree


Algoritmos para problemas de empacotamento e roteamento

Texto completo
Autor(es):
Jefferson Luiz Moisés da Silveira
Número total de Autores: 1
Tipo de documento: Tese de Doutorado
Imprenta: Campinas, SP.
Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
Data de defesa:
Membros da banca:
Eduardo Candido Xavier; Cid Carvalho de Souza; Victor Fernandes Cavalcante; Reinaldo Morabito; Horacio Hideki Yanasse
Orientador: Eduardo Candido Xavier
Resumo

Neste trabalho estamos interessados em problemas de empacotamento e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Além de algoritmos exatos, duas das abordagens para resolver tais problemas são Algoritmos Aproximados e Heurísticas. Nesta tese mostramos algoritmos baseados nestas três abordagens para ambos os problemas, de empacotamento e roteamento. Os dois primeiros problemas atacados foram generalizações de problemas clássicos de empacotamento: O problema da mochila bidimensional e o problema de empacotamento em faixas. Estes foram generalizados adicionando restrições na forma de carregamento e descarregamento dos itens no recipiente (restrições estas, que aparecem no contexto de problemas de roteamento). O terceiro problema é uma combinação de problemas de empacotamento e roteamento. Neste caso, atacamos uma generalização do clássico Pickup and Delivery Problem. Propomos os primeiros resultados de aproximação para algumas versões dos problemas de empacotamento supracitados. Além disto, apresentamos algumas abordagens práticas para o terceiro problema. As heurísticas foram avaliadas através de experimentos computacionais comparando os seus resultados com algoritmos exatos (AU)

Processo FAPESP: 11/08563-9 - Algoritmos para Problemas de Empacotamento com Restrições de Descarregamento
Beneficiário:Jefferson Luiz Moisés da Silveira
Linha de fomento: Bolsas no Brasil - Doutorado