Algoritmos para problemas de empacotamento e roteamento

Autor(es)

Jefferson Luiz Moisés da Silveira

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2013-02-10

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
• Modalidade de apoio: Bolsas no Brasil - Doutorado