Problemas de Empacotamento com Restrições de Ordem de Entrega

• Processo: 08/03973-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2008
• Data de Término da vigência: 31 de janeiro de 2009
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Eduardo Candido Xavier
• Beneficiário: Felipe Andrade Holanda
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos Problemas de roteamento de veículos Análise de algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos | Empacotamento | roteamento de veículos | Análise de Algoritmos

Resumo

Neste projeto estamos interessados em investigar problemas de Empacotamento com restrições que surgem de problemas de Roteamento de Veículos. No problema de Roteamento de Veículos consideramos que um conjunto de clientes possuem demandas por itens bidimensionais que devem ser fornecidos por uma central. Um determinado número de caminhões deverá atender toda a demanda gerada por clientes. Temos um problema de construção de rotas que saiam da central e passem pelos clientes atendendo a demanda destes, onde o objetivo é minimizar os custos das rotas utilizadas. Na resolução deste problema, para cada rota, deve-se gerar um empacotamento dos itens demandados pelos clientes da rota, satisfazendo a restrição de que na retirada de itens de um cliente da rota não pode haver itens de um outro cliente (que está adiante na rota) obstruindo a porta de saída do caminhão. A geração de bons empacotamentos considerando esta restrição é uma parte fundamental de algoritmos que buscam minimizar os custos das rotas geradas. O nosso objetivo é o estudo e implementação de algoritmos para o problema de empacotamento bidimensional com restrições de ordem de entrega na rota.